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.
Programming Praxis 
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,
nilwould be the empty list'()and the predicate would benull?. In my above example, these areemptyandempty?.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.