Programming Praxis

We represent a pair as a vector with two slots. The null pair is represented as a zero-length vector. Head and tail extract the various elements:

(define nil (vector)) ; '()

(define (nil? xs) (zero? (vector-length xs))) ; null?

(define (pair x xs) (vector x xs)) ; cons

(define (head xs) ; car
  (if (nil? xs)
      (error 'head "exhausted")
      (vector-ref xs 0)))

(define (tail xs) ; cdr
  (if (nil? xs)
      (error 'tail "exhausted")
      (vector-ref xs 1))

With that, we can build a list like this:

> (define xs (pair 0 (pair 1 (pair 2 (pair 3 (pair 4 (pair 5 (pair 6 (pair 7 nil)))))))))
> (head xs)
0
> (head (tail (tail (tail xs))))
3

The nth item is found by counting down the elements of a list until the desired item is found; the length of a list is found by counting each element until the last is found. Old-time lispers call the operation of inspecting each element of a list cdr-ing down the list:

(define (nth xs n) ; list-ref
  (if (nil? xs)
        (error 'nth "exhausted")
      (if (zero? n)
          (head xs)
          (nth (tail xs) (- n 1))))

(define (len xs) ; length
  (if (nil? xs)
      0
      (+ (len (tail xs)) 1)))

> (nth xs 5)
5
> (len xs)
8

The append function must cdr down the first list; the second list is untouched:

(define (app x1 x2) ; append
  (if (nil? x1)
      x2
      (pair (head x1)
            (app (tail x1) x2))))

> (nth (app xs (pair 8 (pair 9 nil))) 9)
9
> (nth (app xs (pair 8 (pair 9 nil))) 10)
error: nth: exhausted

A naive reverse calls append for each item in the list; an iterative reverse simply cdrs down the input as it accumulates the output:

(define (rev-recursive xs) ; reverse
  (if (nil? xs)
      nil
      (app (rev-recursive (tail xs))
           (pair (head xs) nil))))

(define (rev-iterative xs) ; reverse
  (let loop ((xs xs) (rs nil))
    (if (nil? xs)
        rs
        (loop (tail xs) (pair (head xs) rs)))))

> (nth (rev-recursive xs) 4)
3
> (nth (rev-iterative xs) 4)
3

We’ll stop there; the Standard Prelude gives many more examples of list operations. You can see the program described above at http://programmingpraxis.codepad.org/FPUIwVp0.

Pages: 1 2