Why don't F# lists have a tail pointer

Question

Or phrased another way, what kind of benefits do you get from having a basic, singly linked list with only a head pointer? The benefits of a tail pointer that I can see are:

O(1) list concatenation
O(1) Appending stuff to the right side of the list

Both of which are rather convenient things to have, as opposed to O(n) list concatenation (where n is the length of the left-side list?). What advantages does dropping the tail pointer have?

check this http://stackoverflow.com/questions/1175056/value-of-the-last-element-of-a-list — Karel Frajták, Oct 10 '11 at 07:26
I know I can reverse the list everytime I want to do something useful, but that turns EVERY operation into an `O(n)` operation. I was wondering why they didn't pick this low hanging fruit and make accessing the tail `O(1)` =) — Li Haoyi, Oct 10 '11 at 07:34
F# lists are immutable, so whatever you do, any list modification is at least `O(n)`. — Ramon Snir, Oct 10 '11 at 07:37
@KarelFrajtak: Mainly because sometimes (not sure how often) I find myself appending stuff to *both* sides of a list (e.g. attaching `
` `
` around some html) and then I'll have to reverse my head multiple times in one expression =D — Li Haoyi, Oct 10 '11 at 07:48
@RamonSnir: I thought the point of immutable lists is you could reuse part of it so you could get "modified copies" of the list in less than `O(n)` — Li Haoyi, Oct 10 '11 at 07:49
@LiHaoyi But the operations you suggested mutate the list, thus cannot be done "efficiently" with immutable lists. Only operation you can do without mutating the list is to prepend items, and that is the `(::)` operator. — Ramon Snir, Oct 10 '11 at 07:52
@RamonSnir: I guess my question then is why concatenating lists or sticking stuff on the right mutates a list, but sticking stuff on the left doesn't. Why is the only operation you can do without mutating the list "Prepend"? I'm sure you're right, it just isn't immediately obvious or intuitive to me. I mean, `listA = listB @ listC` doesn't mutate either `listB` or `listC`, unless there is something I am completely missing. Neither does `listA = listB :: newItem`. — Li Haoyi, Oct 10 '11 at 07:57
@LiHaoyi A cons item is a value and then either another cons item or null. When prepending (i.e. ``h::t``), you create a new cons item whose value is ``h`` and its other part (either another cons item or a null) is ``t``. This operation created a new cons item, but did not affect ``t`` (because each cons item only point "forward", nor "backward"). But when you do ``t @ [h]``, there is no easy way to create the list you want, because the end of ``t`` is a null, and that can't be changed (immutability). In order to create the list you want, we need to copy ``t`` and append at the end ``h``. — Ramon Snir, Oct 10 '11 at 08:01
The list type is very simple in F#, basically equivalent to `type 'a List = | Nil | Cons of 'a * 'a List`. How would you implement an immutable list with head and tail "pointers"? It might seem easy, but I suspect that if you try to implement it you'll see that it's not straightforward (as a spoiler you can take a look at http://blogs.msdn.com/b/ericlippert/archive/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue.aspx for a C# implementation of a similar concept). — kvb, Oct 12 '11 at 20:45

score 13 · Accepted Answer · edited Aug 07 '17 at 01:58

F#, like many other functional[-ish] languages, has a cons-list (the terminology originally comes from LISP, but the concept is the same). In F# the :: operator (or List.Cons) is used for cons'ing: note the signature is ‘a –> ‘a list –> ‘a list (see Mastering F# Lists).

Do not confuse a cons-list with an opaque Linked List implementation which contains a discrete first[/last] node - every cell in a cons-list is the start of a [different] list! That is, a "list" is simply the chain of cells that starts at a given cons-cell.

This offers some advantages when used in a functional-like manner: one is that all the "tail" cells are shared and since each cons-cell is immutable (the "data" might be mutable, but that's a different issue) there is no way to make a change to a "tail" cell and flub up all the other lists which contain said cell.

Because of this property, [new] lists can be efficiently built - that is, they do not require a copy - simply by cons'ing to the front. In addition, it is also very efficient to deconstruct a list to head :: tail - once again, no copy - which is often very useful in recursive functions.

This immutable property generally does not exist in a [standard mutable] Double Linked List implementation in that appending would add side-effects: the internal 'last' node (the type is now opaque) and one of the "tail" cells are changed. (There are immutable sequence types that allow an "effectively constant time" append/update such as immutable.Vector in Scala -- however, these are heavy-weight objects compared to a cons-list that is nothing more than a series of cells cons'ed together.)

As mentioned, there are also disadvantages a cons-list is not appropriate for all tasks - in particular, creating a new list except by cons'ing to the head is an O(n) operation, fsvo n, and for better (or worse) the list is immutable.

I would recommend creating your own version of concat to see how this operation is really done. (The article Why I love F#: Lists - The Basics covers this.)

Happy coding.

Also see related post: Why can you only prepend to lists in functional languages?

I have never heard that name before. Do you have any links I could go follow up? Searching "cons list" just gets me a whole bunch of pages with "pros and cons list". Presumably they allow some optimizations tail pointered/doubly linked lists don't, and I want to find out what — Li Haoyi, Oct 10 '11 at 07:52

Brian · Answer 2 · 2011-10-10T08:00:55.087

6

F# lists are immutable, there's no such thing as "append/concat", rather there's just creating new lists (that may reuse some suffixes of old lists). Immutability has many advantages, outside the scope of this question. (All pure languages, and most functional languages have this data structure, it is not an F#-ism.)

See also

http://diditwith.net/2008/03/03/WhyILoveFListsTheBasics.aspx

which has good picture diagrams to explain things (e.g. why consing on the front is cheaper than at the end for an immutable list).

edited Oct 10 '11 at 08:00

answered Oct 10 '11 at 07:45

Brian

117,631
17
236
300

I mean append concat as expressions not as statements. Isn't that a pretty normal way to use it? I don't know how else I would name "listA = listB + listC" other than a concat. Immutable Lists can have tail pointers too, and concat faster! – Li Haoyi Oct 10 '11 at 07:51
3

Regardless of whether it's an expression or a statement, if the lists are immutable, you need to allocate a new list object for the concatenated result, and a tail-pointer will not help the performance (unless you are talking about very advanced data structures that provide fast catenation for immutable lists). – Brian Oct 10 '11 at 07:57

score 4 · Answer 3 · answered Oct 10 '11 at 08:47

In addition to what the others said: if you need efficient, but yet immutable data structures (which should be an idiomatic F# way), you have to consider reading Chris Okasaki, Purely Functional Data Structures. There is also a thesis available (on which the book is based).

score 3 · Answer 4 · edited May 23 '17 at 11:45

In addition to what has been already said, the Introducing Functional Programming section on MSDN has an article about Working with Functional Lists that explains how lists work and also implements them in C#, so it may be a good way to understand how they work (and why adding reference to the last element would not allow efficient implementation of append).

If you need to append things to the end of the list, as well as to the front, then you need a different data structure. For example, Norman Ramsey posted source code for DList which has these properties here (The implementation is not idiomatic F#, but it should be easy to fix).

score 2 · Answer 5 · 2011-10-10T19:19:31.047

If you find you want a list with better performance for append operations, have a look at the QueueList in the F# PowerPack and the JoinList in the FSharpx extension libraries.

QueueList encapsulates two lists. When you prepend using the cons, it prepends an element to the first list, just as a cons-list. However, if you want to append a single element, it can be pushed to the top of the second list. When the first list runs out of elements, List.rev is run on the second list, and the two are swapped putting your list back in order and freeing the second list to append new elements.

JoinList uses a discriminated union to more efficiently append whole lists and is a bit more involved.

Both are obviously less performant for standard cons-list operations but offer better performance for other scenarios.

You can read more about these structures in the article Refactoring Pattern Matching.

Looks like `JoinList` is more or less the same as `DList` referenced by Tomas above which, as noted by Norman Ramsey in the linked question, originated with John Hughes. — , Oct 10 '11 at 19:21

score 1 · Answer 6 · answered Oct 10 '11 at 17:28

As others have pointed out, an F# list could be represented by a data structure:

List<T> { T Value; List<T> Tail; }

From here, the convention is that a list goes from the List you have a reference to until Tail is null. Based on that definition, the benefits/features/limitations in the other answers come naturally.

However, your original question seems to be why the list is not defined more like:

List<T> { Node<T> Head; Node<T> Tail; }
Node<T> { T Value; Node<T> Next; }

Such a structure would allow both appending and prepending to the list without any visible effects to the a reference to the original list, since it still only sees a "window" of the now expanded list. Although this would (sometimes) allow O(1) concatenation, there are several issues such a feature would face:

The concatenation only works once. This can lead to unexpected performance behavior where one concatenation is O(1), but the next is O(n). Say for example:
```
 listA = makeList1 ()
 listB = makeList2 ()
 listC = makeList3 ()
 listD = listA + listB //modified Node at tail of A for O(1)
 listE = listA + listC //must now make copy of A to concat with C
```
You could argue that the time savings for the cases where possible are worth it, but the surprise of not knowing when it will be O(1) and when O(n) are strong arguments against the feature.
All lists now take up twice as much space, even if you never plan to concatenate them.
You now have a separate List and Node type. In the current implementation, I believe F# only uses a single type like the beginning of my answer. There may be a way to do what you are suggesting with only one type, but it is not obvious to me.
The concatenation requires mutating the original "tail" node instance. While this shouldn't affect programs, it is a point of mutation, which most functional languages tend to avoid.

score 1 · Answer 7 · edited Jun 20 '20 at 09:12

Or phrased another way, what kind of benefits do you get from having a basic, singly linked list with only a head pointer? The benefits of a tail pointer that I can see are:

O(1) list concatenation

O(1) Appending stuff to the right side of the list

Both of which are rather convenient things to have, as opposed to O(n) list concatenation (where n is the length of the left-side list?).

If by "tail pointer" you mean a pointer from every list to the last element in the list, that alone cannot be used to provide either of the benefits you cite. Although you could then get at the last element in the list quickly, you cannot do anything with it because it is immutable.

You could write a mutable doubly-linked list as you say but the mutability would make programs using it significantly harder to reason about because every function you call with one might change it.

As Brian said, there are purely functional catenable lists. However, they are many times slower at common operations than the simple singly-linked list that F# uses.

What advantages does dropping the tail pointer have?

30% less space usage and better performance on virtually all list operations.

Why don't F# lists have a tail pointer

7 Answers7

Linked