Pairs

⇒ Data Primitive, a pair of two primitives, constructed by cons, extracted by car and cdr

⇒ Data objects constructed from pairs are called list-structured data.

Constructing your own pairs with procedures

Notice that any three functions cons, car and cdr that work exactly as specified above can form the basis for implementing pairs. That is if there’s a pair z = (cons x y), then (car z) ⇒ x and (cdr z) ⇒ y

(define (cons x y)
	(define (dispatch m)
		(cond ((= m 0) x)
					((= m 1) y)
					(else (error "cons: argument error"))))
	dispatch)

(define (car z) (z 0))
(define (cdr z) (z 1))

(*) This use of procedures corresponds to nothing like our intuitive notion of what data should be. Nevertheless, all we need to do to show that this is a valid way to represent pairs is to verify that these procedures satisfy the condition given above.

Another way to represent pairs with procedures

(define (cons x y)
	(lambda (m) (m x y)))

(define (car z)
	(z (lambda (p q) p)))

(define (cdr z)
	(z (lambda (p q) q)))

Lists

Nested application of cons gives rise to lists, and Scheme provides a primitive procedure to construct a list of multiple elements: list

(define lst (list 1 2 3 4)) ; creates a list of elements 1, 2, 3, 4

=> (cons 1 (cons 2 (cons 3 (cons 4 #nil))) ; but is actually a nested sequence of 'cons'

What about car and cdr ?

List Operations