Structure and Interpretation of Computer Programs

List Operations

The use of pairs to represent sequences of elements as lists is accompanied by conventional programming techniques for manipulating lists by successively "cdring down" the lists. For example, the function list-ref/2 takes as arguments a list and a number \(n\) and returns the \(n\)th item of the list. In Erlang, and thus LFE, is customary to number the elements of the list beginning with 1. The method for computing list-ref/2 is the following: ¹

• For \(n = 1\), list-ref/2 should return the car of the list.
• Otherwise, list-ref/2 should return the \(n\)th item of the cdr of the list.

(defun list-ref
  ((items 1)
   (car items))
  ((items n)
   (list-ref (cdr items) (- n 1))))

> (set squares (list 1 4 9 16 25))
(1 4 9 16 25)
> (list-ref squares 4)
16

Note, though, that with LFE we can simplify this process: when we use pattern matching on the function arguments, we don't need to explicitly call car and cdr -- we get those for free. The previous function can be rewritten to take advantage of this: ²:

(defun list-ref
  (((cons head _) 1)
   head)
  (((cons _ tail) n)
   (list-ref tail (- n 1))))

Often we "cdr down" the whole list. The function len/1,³ which returns the number of items in a list, illustrates this typical pattern of use:

(defun len
  (('())
   0)
  ((items)
   (+ 1 (len (cdr items)))))

> (set odds (list 1 3 5 7))
(1 3 5 7)
> (len odds)
4

Again, we can rewrite that using LFE consing in the function arguments:

(defun len
  (('())
   0)
  (((cons _ tail))
   (+ 1 (len tail))))

The len/1 function implements a simple recursive plan. The reduction step is:

• The length of any list is 1 plus the length of the cdr of the list.

This is applied successively until we reach the base case:

• The passed list matches the pattern of the empty list.

We could also compute length in an iterative style:

(defun len (items)
  (len items 0))

(defun len
  (('() count)
   count)
  (((cons _ tail) count)
   (len tail (+ 1 count))))

Another conventional programming technique is to "cons up" an answer list while cdring down a list, as in the function append/2,⁴ which takes two lists as arguments and combines their elements to make a new list:

> (append squares odds)
(1 4 9 16 25 1 3 5 7)
> (append odds squares)
(1 3 5 7 1 4 9 16 25)

append/2 is also implemented using a recursive plan. To append lists list1 and list2, do the following:

• If list1 is the empty list, then the result is just list2.
• Otherwise, append the cdr of list1 and list2, and cons the car of list1 onto the result.

We will first show without cons pattern-matching:

(defun append
  (('() list2)
   list2)
  ((list1 list2)
   (cons (car list1) (append (cdr list1) list2))))

With cons pattern-matching, we have this as

(defun append
  (('() list2)
   list2)
  (((cons head tail) list2)
   (cons head (append tail list2))))