## Functional-Style Linked Lists

### October 8, 2013

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

How about using functions directly to represent the list? Can’t get much more functional than that. :)

Each ‘list’ is actually a function which in turn takes a function of three arguments: the head, the tail, and if the list is empty. From there, you can build everything pretty quickly. Better yet, the rest of the functions don’t even need to know about the implementation–they can just use the four functions given above.

GitHub gist: jpverkamp/6896457

Blog post: Functions as lists

What do you mean by “you should include at least nil and a predicate to recognize it”?

nil is the empty list. In Scheme for example,

`nil`

would be the empty list`'()`

and the predicate would be`null?`

. In my above example, these are`empty`

and`empty?`

.It’s a special case because it’s still a list but unlike all other lists it doesn’t have a head and a tail, so functions that return those work differently.