Cons Cells and List Structure
5.1 Cons Cells
Lists are built from cons cells (pairs). Each cell has two slots: car (head) and cdr (tail).
cons (seqs), conj car / first cdr / rest rest / next null / endp empty? / seq
(1 2 3) is: [1|•]→[2|•]→[3|/] (/ = empty list / nil)(cons 1 '(2 3)) ; (1 2 3)
(cons 1 2) ; (1 . 2): a dotted pair (improper list)
(car '(1 2 3)) ; 1
(cdr '(1 2 3)) ; (2 3)
(cadr '(1 2 3)) ; 2: car of cdr
(caddr '(1 2 3)) ; 3
(list 1 2 3) ; (1 2 3)
(append '(1 2) '(3 4)) ; (1 2 3 4)
(length '(1 2 3)) ; 3
(reverse '(1 2 3)) ; (3 2 1)
(null? '()) ; #t (Common Lisp: (null nil); Clojure: (empty? []))
(pair? '(1)) ; #t (Common Lisp: consp)
(list-ref '(a b c) 1) ; b (Common Lisp: (nth 1 ...))5.2 Trees from Lists
(define tree '(1 (2 (4) (5)) (3 (6))))
(define (count-leaves t)
(cond ((null? t) 0)
((not (pair? t)) 1)
(else (+ (count-leaves (car t))
(count-leaves (cdr t))))))
(count-leaves tree) ; 65.3 Sharing and Mutation
cons shares structure: (define a '(2 3)) (define b (cons 1 a)) means b's tail is a.
Mutating operations (set-car!, set-cdr! in Scheme; setf of car in Common Lisp) affect every list that shares the cells, so use them with care. Clojure's data structures are immutable and persistent.