Lists & cons

Lisp's name comes from "LISt Processor". Lists are the core data structure.

(define lst (list 1 2 3 4 5))
(car lst)     ; 1
(cdr lst)     ; (2 3 4 5)
(cons 0 lst)  ; (0 1 2 3 4 5)

Lists are built from PAIRS:

(cons 1 (cons 2 (cons 3 nil)))    ; (1 2 3)

Each cons is a pair (head, tail). The empty list is nil (or ()).

Functions:

• (car p) — first element of a pair (head)
• (cdr p) — rest (tail)
• (cons a b) — make a new pair
• (list ...) — sugar for nested cons
• (null? x) — true if empty list

Recursive list processing is the canonical Lisp pattern:

(define (length lst)
   (if (null? lst)
       0
       (+ 1 (length (cdr lst)))))

(define (map fn lst)
   (if (null? lst)
       '()
       (cons (fn (car lst)) (map fn (cdr lst)))))

map, filter, reduce (all built from cons/car/cdr) are the bedrock of Lisp programming. Modern languages stole them.