Functional-Style Linked Lists

October 8, 2013

We frequently use linked lists in our programs, but Scheme makes that easy because it provides linked lists as a native data type, along with a rich set of operations on them. In today’s exercise we will implement lists in the functional style that Scheme provides natively.

In Scheme, a list is really nothing more than an array with two slots, known as the car and cdr of a pair; a list with no elements is called the null list. We frequently think of lists as a sequence of elements, but in fact a list is no more than a chain of pairs, of which the cdr of each pair is another list, the chain terminating in a null list. Depending on the version of Scheme that you use, the car and cdr of the pair may or may not be mutable; traditionally, they have been mutable, but the most recent approved standard R6RS makes pairs immutable (that is controversial, and many implementations of Scheme ignore it and leave pairs mutable). Still, immutable pairs are more closely aligned with the spirit of functional languages, and your implementation today should provide immutable pairs.

Your task is to implement a small library of list operators; you should include at least nil and a predicate to recognize it, a procedure to build pairs and two procedures to extract the pieces of a pair, functions to extract the nth item of a list and to determine its length, and functions to reverse the elements of a list and append two lists; you are welcome to provide more operators if you wish. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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 615 other followers

%d bloggers like this: