how do i append (1 2 3) to the end of () to make ((1 2 3))
how do i append (4 5 6) to the end of that to make ((1 2 3) (4 5 6))
how do i append "|" to the end of that to make ((1 2 3) (4 5 6) "|")
with NO dotted pairs.
I'm working with Chicken Scheme but I'll take an answer from any scheme at this point. Note that any of these lists could also be nested lists of who knows what... i'm just writing a trivial example.
note: @sjamaan shows a solution using append that involves wrapping everything in another list to compensate for append doing things OTHER than what the name says.
(append (list 1 2 3) "|" ) ;=> (1 2 3 . "|")
;^^ didn't actually append, created a dotted pair
(append '(1 2 3) (list 4 5 6)) ;=> (1 2 3 4 5 6) ; don't want unwrapped list
;^^ didn't actually append the list i gave it but appended the contents of the list.
Basically I'm hoping for an append method that actually appends what you give it, not appends the contents of it, or takes it and makes a dotted pair. Maybe i'm just a dreamer... I can write a "no really append" method that just takes whatever params you give it and wraps them in an outer list to compensate but that's just silly... Surely scheme has some way to append without this crazyness.
Here is how append is made:
(define (append2 lst1 lst2)
(if (null? lst1)
lst2 ; the second list is unaltered
(cons (car lst1)
(append2 (cdr lst1) lst2))))
makes a pair chain consisting of all the elements in lst1 and lst2. It does not make a pair where there is nont in lst2 so:
(append2 '(1 2 3) '(4 5)) ; ==> (1 2 3 4 5)
(append2 '(1 2 3) '()) ; ==> (1 2 3) and not (1 2 3 ())
(append2 '(1 2 3) '5) ; ==> (1 2 3 . 5)
Note that every list like (1 2 3) actually is (1 2 3 . ()) or even more correctly (1 . (2 . (3 . ())))
how do i append
(1 2 3)to the end of()to make((1 2 3))
(define (insert-last e lst)
(let helper ((lst lst))
(if (pair? lst)
(cons (car lst)
(helper (cdr lst)))
(cons e '()))))
(insert-last '(1 2 3) '())
; ==> ((1 2 3))
how do i append
(4 5 6)to the end of that to make((1 2 3) (4 5 6))
(insert-last '(4 5 6) '((1 2 3)))
; ==> ((1 2 3) (4 5 6))
how do i append
"|"to the end of that to make((1 2 3) (4 5 6) "|")
(insert-last "|" '((1 2 3) (4 5 6)))
; ==> ((1 2 3) (4 5 6) "|")
Know that this is very much like append. These are the worst way to make that list since you are making a new list every time. It's O(n) for each insert and O(n^2) for n elements. If you could do this in reverse order you get something that do this O(1) instead of O(n) for each insert. Instead of insert-last you use cons:
(cons '"|" '()) ; ==> ("|")
(cons '(4 5 6) '("|")) ; ==> ((4 5 6) "|")
(cons '(1 2 3) '((4 5 6) "|") ; ==> ((1 2 3) (4 5 6) "|")
This is O(1), O(n) for n elements processed. If you need to do it in the original order you can accumulate, then reverse..
(cons '(1 2 3) '()) ; ==> ((1 2 3))
(cons '(4 5 6) '((1 2 3))) ; ==> ((4 5 6) (1 2 3))
(cons '"|" '((4 5 6) (1 2 3))) ; ==> ("|" (4 5 6) (1 2 3))
(reverse '("|" (4 5 6) (1 2 3)) ; ==> ((1 2 3) (4 5 6) "|")
This is O(1), then O(n) for the reverse but it still is O(1) amortized. O(n) for n elements you process.