I read both of them and they seem to both construct a single list, what's their difference?
Asked
Active
Viewed 1.8k times
8
-
Look at (cons '(a b) '(c d)) versus (append '(a b) '(c d)). – Joshua Taylor Apr 08 '16 at 11:37
-
1Possible duplicate of [Cons element to list vs cons list to element in Scheme](http://stackoverflow.com/questions/19213072/cons-element-to-list-vs-cons-list-to-element-in-scheme) – Joshua Taylor Apr 08 '16 at 11:39
1 Answers
12
cons
is the constructor for all pairs.
A proper list is ()
(the empty list, aka nil
) or a pair where the cdr
is a proper list. Any chain of pairs where the last one has ()
as it's cdr
is a proper list (in addition to the empty list itself).
A dotted list is a pair that does not have a proper list as it's cdr
. Thus a chain of pairs where the last cdr
is not ()
matches this.
;; dotted lists
(cons 1 2) ; ==> (1 . 2)
(cons 1 (cons 2 3)) ; ==> (1 2 . 3) or (1 . (2 . 3))
;; proper lists
(cons 1 '()) ; ==> (1) or (1 . ())
(cons 1 (cons 2 '())) ; ==> (1 2) or (1 . (2 . ()))
append
is a procedure that uses cons
to make a list with all the elements of the argument lists left to right. A common implementation of append
for just two lists would be:
(define (append lst tail)
(if (null? lst)
tail
(cons (car lst)
(append (cdr lst)
tail))))
append
will fail if one of the arguments except the last is not a proper list. Tail and can be any value:
(append '(1 2 3) '(4 5)) ; ==> (1 2 3 4 5) or (1 . (2 . (3 . (4 . (5 . ())))))
(append '(1 2 3) '(4 5 . 6)) ; ==> (1 2 3 4 5 . 6) or (1 . (2 . (3 . (4 . (5 . 6)))))
(append '(1 2 3) #f) ; ==> (1 2 3 . #f) or (1 . (2 . (3 . #f)))
(append '(1 2 . 3) '(4 5 . 6)) ; ==> error `car` of number not allowed

Sylwester
- 47,942
- 4
- 47
- 79
-
Also, cons is generally more efficient as it does not have to go through the whole list. In terms of big O notation, cons usages are generally O(1) while append is O(n) where n is the length of the list you are dealing with. While (append (list first_elem) existing_list) technically has the same big O with (cons first_elem existing_list), the latter is more concise and faster. – martian17 Apr 09 '19 at 22:35