Thank you for your comment

Beau­tiful Racket / explainers

Pairs

A pair is a data struc­ture that holds two values. Once the pair is created, it cannot be changed (meaning, it is immutable). A pair is made with cons. A pair is printed like a list, but with a dot between the two values:

(cons 42 43)
(cons "see" "saw")
(cons 'this 'that)
(cons + -)
1
2
3
4
(cons 42 43)
(cons "see" "saw")
(cons 'this 'that)
(cons + -)
copy to clipboard
'(42 . 43)
'("see" . "saw")
'(this . that)
'(#<procedure:+> . #<procedure:->)
1
2
3
4
'(42 . 43)
'("see" . "saw")
'(this . that)
'(#<procedure:+> . #<procedure:->)
copy to clipboard

The first element of the pair can be retrieved with car; the second element with cdr.

(car (cons 42 43)) ; 42
(car (cons "see" "saw")) ; "see"
(car (cons 'this 'that)) ; 'this
(car (cons + -)) ; #<procedure:+>

(cdr (cons 42 43)) ; 43
(cdr (cons "see" "saw")) ; "saw"
(cdr (cons 'this 'that)) ; 'that
(cdr (cons + -)) ; #<procedure:->
1
2
3
4
5
6
7
8
9
(car (cons 42 43)) ; 42
(car (cons "see" "saw")) ; "see"
(car (cons 'this 'that)) ; 'this
(car (cons + -)) ; #<procedure:+>

(cdr (cons 42 43)) ; 43
(cdr (cons "see" "saw")) ; "saw"
(cdr (cons 'this 'that)) ; 'that
(cdr (cons + -)) ; #<procedure:->
copy to clipboard

cons is the inverse of car and cdr, so this iden­tity is true for every pair:

(equal? (cons (car my-pair) (cdr my-pair)) my-pair)
1
(equal? (cons (car my-pair) (cdr my-pair)) my-pair)
copy to clipboard

For instance:

(define (identity my-pair)
  (equal? (cons (car my-pair) (cdr my-pair)) my-pair))

(identity (cons 42 43)) ; #t
(identity (cons "see" "saw")) ; #t
(identity (cons 'this 'that)) ; #t
(identity (cons + -)) ; #t
1
2
3
4
5
6
7
(define (identity my-pair)
  (equal? (cons (car my-pair) (cdr my-pair)) my-pair))

(identity (cons 42 43)) ; #t
(identity (cons "see" "saw")) ; #t
(identity (cons 'this 'that)) ; #t
(identity (cons + -)) ; #t
copy to clipboard

pair? is the pred­i­cate func­tion.

Pairs and lists

Pairs can be combined to make other data struc­tures. For instance, under the hood, lists (other than the empty list) are made from a series of linked pairs, where the final element is null. The list func­tion itself is just short­hand for an equiv­a­lent series of nested cons oper­a­tions:

(list 42 'foo "bar") ; '(42 foo "bar")
(cons 42 (cons 'foo (cons "bar" null))) ; also '(42 foo "bar")
1
2
(list 42 'foo "bar") ; '(42 foo "bar")
(cons 42 (cons 'foo (cons "bar" null))) ; also '(42 foo "bar")
copy to clipboard

Because every non-empty list is a pair,  + For this reason, the pair? pred­i­cate can be used to test for a non-empty list. func­tions that work on pairs—including cons, car, and cdr—will also work on non-empty lists:

(car (list 'foo "bar")) ; 'foo
(cdr (list 'foo "bar")) ; '("bar")
(cons 42 (list 'foo "bar")) ; '(42 foo "bar")
(car (cons 'foo (cons "bar" null))) ; 'foo
(cdr (cons 'foo (cons "bar" null))) ; '("bar")
(cons 42 (cons 'foo (cons "bar" null))) ; '(42 foo "bar")
1
2
3
4
5
6
(car (list 'foo "bar")) ; 'foo
(cdr (list 'foo "bar")) ; '("bar")
(cons 42 (list 'foo "bar")) ; '(42 foo "bar")
(car (cons 'foo (cons "bar" null))) ; 'foo
(cdr (cons 'foo (cons "bar" null))) ; '("bar")
(cons 42 (cons 'foo (cons "bar" null))) ; '(42 foo "bar")
copy to clipboard

If you need to store two values, there’s nothing wrong with using a pair directly instead of a list. This can be worth­while in situ­a­tions that call for pecu­nious use of computing resources, because a two-element list uses two pairs rather than one (and thus twice as much memory and allo­ca­tion time). Keep in mind that because of this extra pair, the cdr of a list always returns a list, whereas in a pair it returns a single value:

(cdr (cons 'this 'that)) ; 'that
(cdr (list 'this 'that)) ; '(that)
1
2
(cdr (cons 'this 'that)) ; 'that
(cdr (list 'this 'that)) ; '(that)
copy to clipboard

About the names

The names of cons, car, and cdr are conven­tional and historic. In the orig­inal Lisp inter­preter of 1958, cons was chosen as an abbre­vi­a­tion for “construct”. car and cdr were abbre­vi­a­tions for “contents of the address part of the register” and “contents of the decre­ment part of the register”, termi­nology specific to the IBM 704 computer that ran the inter­preter. At this point, they’re unlikely to be dislodged.

Further

← prev next →