Skip to content

Pairs and Lists

Pairs are the fundamental building block of Scheme data structures. A list is either the empty list '() or a pair whose cdr is a list. These procedures are available from (scheme base).

Performance characteristics

Lists are linked chains of pairs. This makes some operations fast and others slow:

Operation Complexity Notes
cons, car, cdr O(1) Constant time
length O(n) Traverses the entire list
list-ref O(n) Walks n pairs from the head
append O(n) Copies the first list
map, for-each O(n) One pass
assoc O(n) Linear scan
member O(n) Linear scan

When to use lists vs. other types:

  • Use lists for sequential processing, building up data with cons, and recursive decomposition with car/cdr
  • Use vectors when you need random access by index (vector-ref is O(1), list-ref is O(n))
  • Use hash tables when you need fast key-value lookup (hash-table-ref is O(1), assoc is O(n))

Core Pairs

cons

Syntax: (cons obj1 obj2)

Returns a newly allocated mutable pair whose car is obj1 and whose cdr is obj2. If obj2 is a proper list the result is a proper list; otherwise the result is a dotted pair.

O(1). Allocates one pair on the heap.

kaappi> (cons 1 2)
;=> (1 . 2)
kaappi> (cons 'a '(b c))
;=> (a b c)
kaappi> (cons 1 '())
;=> (1)

Common pattern — building a list from back to front:

(define (iota n)
  (let loop ((i (- n 1)) (acc '()))
    (if (< i 0) acc
        (loop (- i 1) (cons i acc)))))
(iota 5) ;=> (0 1 2 3 4)

See also: car, cdr

car

Syntax: (car pair)

Returns the contents of the car field of pair. O(1). JIT-inlined.

Errors: Raises TypeError if the argument is not a pair. (car '()) is an error — the empty list is not a pair.

kaappi> (car '(a b c))
;=> a
kaappi> (car (cons 1 2))
;=> 1
kaappi> (car '((1 2) 3))
;=> (1 2)

See also: cdr, caar, cadr

cdr

Syntax: (cdr pair)

Returns the contents of the cdr field of pair. O(1). JIT-inlined.

Errors: Raises TypeError if the argument is not a pair.

kaappi> (cdr '(a b c))
;=> (b c)
kaappi> (cdr (cons 1 2))
;=> 2
kaappi> (cdr '(a))
;=> ()

See also: car, cdar, cddr

set-car!

Syntax: (set-car! pair obj)

Stores obj in the car field of pair. The return value is unspecified. Raises a type error if the first argument is not a pair.

kaappi> (define p (cons 1 2))
kaappi> (set-car! p 99)
kaappi> p
;=> (99 . 2)

See also: set-cdr!, car

set-cdr!

Syntax: (set-cdr! pair obj)

Stores obj in the cdr field of pair. The return value is unspecified. Raises a type error if the first argument is not a pair.

kaappi> (define p (cons 1 2))
kaappi> (set-cdr! p 99)
kaappi> p
;=> (1 . 99)

See also: set-car!, cdr

List Construction

list

Syntax: (list obj ...)

Returns a newly allocated proper list whose elements are the arguments. Called with no arguments it returns the empty list. O(n) where n is the number of arguments.

kaappi> (list 1 2 3)
;=> (1 2 3)
kaappi> (list 'a 'b)
;=> (a b)
kaappi> (list)
;=> ()
kaappi> (list (+ 1 2) (* 3 4))
;=> (3 12)

See also: make-list, cons

make-list

Syntax: (make-list k) | (make-list k fill)

Returns a newly allocated list of k elements. If fill is given, each element is initialized to fill; otherwise the elements are unspecified. Raises a type error if k is not a non-negative integer.

kaappi> (make-list 3 0)
;=> (0 0 0)
kaappi> (make-list 0)
;=> ()

See also: list, list-copy

list-copy

Syntax: (list-copy obj)

Returns a newly allocated shallow copy of obj. If obj is a proper list, the result is a new list with the same elements. If obj is not a pair, it is returned unchanged. Improper lists are copied faithfully, preserving the dotted tail.

kaappi> (define original (list 1 2 3))
kaappi> (define copy (list-copy original))
kaappi> (list-set! copy 0 99)
kaappi> original
;=> (1 2 3)
kaappi> copy
;=> (99 2 3)

See also: list, make-list

append

Syntax: (append list ...)

Returns a list consisting of the elements of the first list followed by the elements of the other lists. The last argument may be any object and is used directly as the tail of the result. All preceding arguments must be proper lists. Called with no arguments it returns the empty list.

O(n) where n is the total length of all lists except the last (the last list is shared, not copied).

kaappi> (append '(a b) '(c d))
;=> (a b c d)
kaappi> (append '(1) '(2) '(3))
;=> (1 2 3)
kaappi> (append '(a b) 'c)
;=> (a b . c)
kaappi> (append '() '(1 2))
;=> (1 2)
kaappi> (append)
;=> ()

append copies all but the last list

(append list1 list2) copies list1 and points its tail at list2. Mutating list2 later will affect the result. If you need an independent copy, use list-copy on the result.

See also: reverse, concatenate

reverse

Syntax: (reverse list)

Returns a newly allocated list consisting of the elements of list in reverse order. Raises a type error if the argument is an improper list.

kaappi> (reverse '(a b c))
;=> (c b a)
kaappi> (reverse '())
;=> ()

See also: append, append-reverse

length

Syntax: (length list)

Returns the number of elements in list. O(n) — traverses the entire list.

Errors: Raises TypeError if the argument is an improper or circular list. Uses Floyd's cycle-detection algorithm internally so circular lists are caught rather than causing an infinite loop.

kaappi> (length '(a b c))
;=> 3
kaappi> (length '())
;=> 0

Avoid repeated length calls

Since length is O(n), avoid calling it in a loop condition. Instead, use recursion with null? to check for the end of a list.

See also: list?, length+

Two-Level CXR

These four compositions of car and cdr are part of (scheme base). Each takes exactly one pair argument and applies two accessor operations from right to left (innermost first).

caar

Syntax: (caar pair)

Equivalent to (car (car pair)). Returns the car of the car of pair.

kaappi> (caar '((1 2) 3))
;=> 1

cadr

Syntax: (cadr pair)

Equivalent to (car (cdr pair)). Returns the second element of a list.

kaappi> (cadr '(1 2 3))
;=> 2

cdar

Syntax: (cdar pair)

Equivalent to (cdr (car pair)). Returns the cdr of the car of pair.

kaappi> (cdar '((1 2) 3))
;=> (2)

cddr

Syntax: (cddr pair)

Equivalent to (cdr (cdr pair)). Returns the list after dropping the first two elements.

kaappi> (cddr '(1 2 3))
;=> (3)

List Access

list-ref

Syntax: (list-ref list k)

Returns the kth element of list (zero-indexed). O(k) — walks k pairs from the head.

Errors: Raises IndexOutOfBounds if k is out of range. Raises TypeError if k is not a non-negative integer or list is not a proper list.

kaappi> (list-ref '(a b c d) 0)
;=> a
kaappi> (list-ref '(a b c d) 2)
;=> c
kaappi> (list-ref '(a b c d) 3)
;=> d

Use vectors for indexed access

list-ref is O(k) because it walks the list. If you need frequent random access by index, use a vector instead — vector-ref is O(1).

See also: list-tail, list-set!

list-tail

Syntax: (list-tail list k)

Returns the sublist of list obtained by omitting the first k elements. Equivalent to applying cdr k times. Raises IndexOutOfBounds if k is out of range.

kaappi> (list-tail '(a b c d) 0)
;=> (a b c d)
kaappi> (list-tail '(a b c d) 2)
;=> (c d)
kaappi> (list-tail '(a b c d) 4)
;=> ()

See also: list-ref, drop

list-set!

Syntax: (list-set! list k obj)

Stores obj in element k of list (zero-indexed), mutating the pair in place. The return value is unspecified. Raises IndexOutOfBounds if k is out of range and TypeError if k is not a non-negative integer.

kaappi> (define ls (list 1 2 3))
kaappi> (list-set! ls 1 99)
kaappi> ls
;=> (1 99 3)

See also: list-ref, set-car!

member

Syntax: (member obj list) | (member obj list compare)

Returns the first sublist of list whose car is equal to obj, or #f if obj does not appear. By default elements are compared with equal?. An optional third argument compare specifies a two-argument predicate to use instead.

kaappi> (member 3 '(1 2 3 4 5))
;=> (3 4 5)
kaappi> (member 6 '(1 2 3 4 5))
;=> #f
kaappi> (member '(b) '((a) (b) (c)))
;=> ((b) (c))
kaappi> (member 2 '(1 2 3) =)
;=> (2 3)

See also: memq, memv, find

memq

Syntax: (memq obj list)

Like member, but compares elements using eq? (pointer identity). Returns the first sublist whose car is eq? to obj, or #f.

kaappi> (memq 'b '(a b c))
;=> (b c)
kaappi> (memq 'd '(a b c))
;=> #f

See also: member, memv

memv

Syntax: (memv obj list)

Like member, but compares elements using eqv? (value equivalence for numbers and characters). Returns the first sublist whose car is eqv? to obj, or #f. For flonums, comparison is bitwise so +0.0 and -0.0 are distinguished.

kaappi> (memv 2 '(1 2 3))
;=> (2 3)
kaappi> (memv 4 '(1 2 3))
;=> #f

See also: member, memq

assoc

Syntax: (assoc obj alist) | (assoc obj alist compare)

Searches the association list alist (a list of pairs) for the first pair whose car is equal to obj using equal?. Returns the matching pair, or #f if not found. An optional third argument compare specifies a two-argument predicate to use instead of equal?. O(n) linear scan.

kaappi> (assoc 'b '((a 1) (b 2) (c 3)))
;=> (b 2)
kaappi> (assoc 'd '((a 1) (b 2) (c 3)))
;=> #f
kaappi> (assoc "name" '(("name" . "Alice") ("age" . 30)))
;=> ("name" . "Alice")
kaappi> (assoc 2.0 '((1 a) (2 b) (3 c)) =)
;=> (2 b)

Common pattern — safe value extraction:

(let ((pair (assoc "key" alist)))
  (if pair (cdr pair) default-value))

Use hash tables for large alists

assoc is O(n). For more than ~10 key-value pairs, use a hash table — hash-table-ref is O(1).

See also: assq, assv, alist-cons

assq

Syntax: (assq obj alist)

Like assoc, but compares keys using eq? (pointer identity). Returns the first pair whose car is eq? to obj, or #f.

kaappi> (assq 'b '((a 1) (b 2) (c 3)))
;=> (b 2)
kaappi> (assq 'd '((a 1) (b 2) (c 3)))
;=> #f

See also: assoc, assv

assv

Syntax: (assv obj alist)

Like assoc, but compares keys using eqv? (value equivalence for numbers and characters). Returns the first pair whose car is eqv? to obj, or #f. For flonums, comparison is bitwise.

kaappi> (assv 2 '((1 a) (2 b) (3 c)))
;=> (2 b)
kaappi> (assv 4 '((1 a) (2 b) (3 c)))
;=> #f

See also: assoc, assq

Iteration

map

Syntax: (map proc list1 list2 ...)

Applies proc element-wise to the elements of the given lists and returns a list of the results. When multiple lists are given, proc receives one argument from each list and iteration stops at the shortest list. The order of application is unspecified by R7RS but Kaappi processes elements left to right. O(n).

kaappi> (map car '((1 2) (3 4) (5 6)))
;=> (1 3 5)
kaappi> (map (lambda (x) (* x x)) '(1 2 3))
;=> (1 4 9)
kaappi> (map + '(1 2 3) '(10 20 30))
;=> (11 22 33)
kaappi> (map car '())
;=> ()
kaappi> (map + '(1 2 3) '(10 20))
;=> (11 22)

map vs for-each

map allocates a new list for the results. If you only need the side effects (printing, mutation), use for-each instead — it doesn't allocate.

See also: for-each, filter-map

for-each

Syntax: (for-each proc list1 list2 ...)

Like map, but calls proc for its side effects rather than collecting results. The return value is unspecified. When multiple lists are given, iteration stops at the shortest. Elements are guaranteed to be processed left to right. O(n), no allocation.

kaappi> (for-each display '(1 2 3))
123
kaappi> (let ((sum 0))
         (for-each (lambda (a b) (set! sum (+ sum a b)))
                   '(1 2 3) '(10 20 30))
         sum)
;=> 66

See also: map, pair-for-each

apply

Syntax: (apply proc arg1 ... args)

Calls proc with the given arguments. The last argument must be a list; its elements are spread as individual arguments. Any arguments before the final list are prepended as individual arguments.

kaappi> (apply + '(1 2 3))
;=> 6
kaappi> (apply + 1 2 '(3 4))
;=> 10
kaappi> (apply list 'a 'b '(c d))
;=> (a b c d)

Note

apply requires at least two arguments: the procedure and the trailing list. The trailing list is always spread, so (apply + '(1 2 3)) is equivalent to (+ 1 2 3).

See also: map, call-with-values

CXR Compositions

The (scheme cxr) library provides all 24 compositions of car and cdr at three and four levels deep. Each procedure takes exactly one argument and applies the accessor operations from right to left (innermost first). For example, (caddar x) is equivalent to (car (cdr (cdr (car x)))).

The naming convention encodes the operation sequence between c and r: each a stands for car and each d stands for cdr, read right to left.

Three-Level Compositions

Procedure Expansion Example
caaar (car (car (car x))) (caaar '(((1 2) 3) 4)) => 1
caadr (car (car (cdr x))) (caadr '(1 (2 3) 4)) => 2
cadar (car (cdr (car x))) (cadar '((1 2 3) 4)) => 2
caddr (car (cdr (cdr x))) (caddr '(1 2 3 4)) => 3
cdaar (cdr (car (car x))) (cdaar '(((1 2) 3) 4)) => (2)
cdadr (cdr (car (cdr x))) (cdadr '(1 (2 3) 4)) => (3)
cddar (cdr (cdr (car x))) (cddar '((1 2 3) 4)) => (3)
cdddr (cdr (cdr (cdr x))) (cdddr '(1 2 3 4)) => (4)

Four-Level Compositions

Procedure Expansion
caaaar (car (car (car (car x))))
caaadr (car (car (car (cdr x))))
caadar (car (car (cdr (car x))))
caaddr (car (car (cdr (cdr x))))
cadaar (car (cdr (car (car x))))
cadadr (car (cdr (car (cdr x))))
caddar (car (cdr (cdr (car x))))
cadddr (car (cdr (cdr (cdr x))))
cdaaar (cdr (car (car (car x))))
cdaadr (cdr (car (car (cdr x))))
cdadar (cdr (car (cdr (car x))))
cdaddr (cdr (car (cdr (cdr x))))
cddaar (cdr (cdr (car (car x))))
cddadr (cdr (cdr (car (cdr x))))
cdddar (cdr (cdr (cdr (car x))))
cddddr (cdr (cdr (cdr (cdr x))))

All 24 compositions raise a TypeError if any intermediate value along the access path is not a pair.

kaappi> (caddr '(a b c d))
;=> c
kaappi> (cadddr '(a b c d e))
;=> d