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.

About these ads

Pages: 1 2

3 Responses to “Functional-Style Linked Lists”

  1. JP said

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

    ; Empty list
    (define empty   (λ (l)   (l 'error 'error #t)))
    (define empty?  (λ (l)   (l (λ (a d e) e))))
     
    ; Build and take apart lists
    (define pair    (λ (a d) (λ (l) (l a d #f))))
    (define first   (λ (l)   (l (λ (a d e) a))))
    (define rest    (λ (l)   (l (λ (a d e) d))))
    

    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

  2. Ji said

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

  3. JP said

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 616 other followers

%d bloggers like this: