What is the purpose of dividing lists in head and tail?

Question

I'm new to functional programming and I've just came across the pattern of dividing lists in head and tail.

I have a background in Javascript and Python, languages where this division is not adopted (as far as I know), therefore it seems to be a design related to the functional programming paradigm, since languages such as Haskell adopts this division. In F#, for example (according to Understanding pattern matching with cons operator), a list is a discriminated union of type

type list<'T> =         // '
    | Nil
    | Cons of 'T * list<'T>

where we have an union of [] and a tuple ‘a*list<‘a>. Therefore, lists are "divided" by design.

How does dividing lists in head and tail relates to the functional paradigm? What problems does it help to solve? I would appreciate examples where this division is useful and/or needed.

Peruke

What JavaScript and Python have is called "array" in F# and Haskell. F# and Haskell have both arrays and lists (and more), but JavaScript and Python only have arrays. That's it. – Azucenaazure

Composite data structures in FP are often based on trees, because trees are an algebraic data structure, i.e. you can describe them algebraically. A list is just a tree in its most unbalanced form. Loosely speaking if you follow math, you are going to wind up with lists to collect any number of homogeneous elements or to encode non-determinism. – Laudable

Answer 1

Before asking what problems does it help to solve?, it may be helpful to ask where does it come from?

But to answer the question, what problems does it help to solve?, the answer is: The problem of handling zero or more items as a collection of things.

If you now say: But we already have collections (or, in .NET, IEnumerable<T>) for that!, that's only because you're already in a context where such abstractions exist.

Imagine, however, a world where none of that exists.

Lists, in the sense of a 'cons list', is a way to solve the problem of 'a multitude' from first principles.

If all you have is something close to lambda calculus, you need to figure out how to work with many objects in a consistent way. A cons list is a data type you can define from an F-algebra. As such, it's a fundamental data type - a bit like logic gates (like NAND gates) are fundamental to computer circuitry.

Particularly in Haskell, it also turns out to be so useful as a fundamental collection type that it fits more than 80 percent of normal use. In Haskell, you can often solve your problems with the built-in linked list ([]) data type.

That it's so useful in Haskell, however, also stems from the fact that Haskell is lazily evaluated. Thus, in Haskell, all linked lists are lazy, which means that if you evaluate the head, the tail may remain 'unevaluated'.

In F# terms, that's actually closer to seq 'a (IEnumerable<T>), which is also (potentially) lazily evaluated.

Even so, F# still comes with a built in cons list - the list type. Even though it's not lazily evaluated in F#, it remains quite useful.

In many ways, in F#, list, array, and seq are fairly interchangeable, with seq as the odd man out (because it can be lazy and/or infinite).

In practice, in F#, list and array are usually interchangeable, in that they come with the same affordances. What you can do with a list, you can do with an array, and vice versa.

They do, however, have slightly different UX and performance characteristics. The F# language slightly favours lists over arrays, in that if you want to create or pattern match on lists, you can use the [] syntax, whereas arrays require that you use [||].

Lists can also be more efficient in some algorithms. Many functional algorithms build lists via recursion. Cons'ing an element unto an existing list is a cheap operation, because you don't have to change the tail. You just update the list pointer to point at the new head.

For arrays, on the other hand, every time you want to append an element, you have to allocate an entirely new array and copy the old values over.

That's not to say that you can't use arrays efficiently. You certainly can - particularly if you can calculate the size of the array up front.

In F#, sometimes arrays are fine, and sometimes lists are better. Personally, when I code in F#, I find lists easier to wield than arrays or seqs.

Antimicrobial

Answer 2

How does dividing lists in head and tail relates to the functional paradigm?

It makes lists immutable, which is crucial for functional programming. For example, in FP, we can add an element to the front of a list without modifying the original list:

let myList = [1; 2; 3]
let yourList = 0 :: myList
printfn "%A" myList     // [1; 2; 3]
printfn "%A" yourList   // [0; 1; 2; 3]

What problems does it help to solve? I would appreciate examples where this division is useful and/or needed.

It's particularly helpful for recursive solutions, which are quite common in FP. The [] (or Nil) constructor handles the base case, and the :: (or Cons) constructor handles the inductive case. For example, here's a simple function for computing the sum of a list:

let rec sum list =
    match list with
        | [] -> 0
        | x :: xs -> x + sum xs

printfn "%A" (sum [1; 2; 3])   // 6

Clanton

Answer 3

Singly linked lists are made up of nodes, such that each node has a pointer to the next node in the list, or a null pointer indicating that there isn't one. So, the immediate reason why lists are divided in this way is that the language is using a singly linked list, and that property reflects the datastructure itself.

Singly linked lists show up in many languages, but they are particularly important in functional languages. Of course, Lisp is famously based entirely on singly linked lists, but they are also important in modern functional languages.

The functional style of programming emphasizes "persistent" datastructures where an update creates a new version without destroying the original one. Sharing most of the original structure, for efficiency, is typical for persistent datastructures.

Singly linked lists are the simplest possible datastructure of this kind: adding a new head node to the beginning, or skipping the current head by following the "next" link to the tail, both give you a modified list without altering the original. Note that, in each case, a tail is shared: dropping the head shares the tail of the original, while adding a new head shares the original as the tail of the new list.

Snead

Answer 4

Much of it is historical in origin, actually. When John McCarthy designed the original m-expression Lisp, he was following the structure of λ-calculus (while initially intending to use a FORTRAN-like syntax). In the λ-calculus, function application is represented by the form

(<named-expression> <application>)

Where the named-expression is an abstracted λ-expression in the form

(<λ-expression>.<name>)

For example, the λ-expression representing constructing a list of two values

(λxy.(x y).CONS)

Which defines a λ-expression λxy which takes two arguments, x and y and returns a pair x y), then gives this λ-expression the name CONS. This can then be applies as

(CONS a b)

(Technically, λ-calculus expressions and their applications always have an arity of 1, but I am using a slightly expanded version to avoid a lot of currying).

What you get from reducing this would be the expression λab.(a b), or in short, a representation of the pair (a b), which we could name like so:

((CONS a b).A-LIST)

We could further apply CONS to itself, which could be used to create a list by chaining pairs together:

((CONS a (CONS b c)).B-LIST)

Which yields (a (b c)). You could then define two more functions, which we might call FIRST and REST (or HEAD and TAIL, if you prefer), to retrieve the component members of these pairs.

((λxy.x).FIRST)
((λxy.y).REST)

For historical reasons, these are also often referred to a CAR and CDR, especially in Lisp circles. When applied to B-LIST, these yield

(FIRST B-LIST)  -> a
(REST B-LIST) -> (b c)

Getting back to McCarthy, he realized that he could use the list structures to represent λ-applications, what he referred to as s-expressions. This would allow him to define the original Lisp itself in terms of the lambda calculus by way of defining a universal function for evaluating Lisp lists, which (among other things) gave him an easy means to demonstrate in his initial paper on the language that Lisp was Turing-complete. However, he saw this as mainly a theoretical curiosity.

It was his grad student Steve Russell who, when working on the compiler for m-expression Lisp, decided to experiment with the idea of implementing the Lisp universal function directly in assembly language, in effect creating an s-expression interpreter. Because the definition of the universal Lisp function required cons, car, and cdr, these were part of the standard forms built into the original interpreted Lisp. This led McCarthy, who was expecting the development of the first m-expression Lisp compiler to take several years, to drop m-expr Lisp entirely in favor of s-exprs.

When later pure-FP languages were developed, they too took inspiration from the λ-calculus, and while there was no question regarding their Turing-completeness by this time, using the established list manipulation functions was a simple and direct means of leveraging known operations in what could be easily shown to be a purely functional manner.

Calcaneus