Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have noticed that most functional languages employ a singly-linked list (a "cons" list) as their most fundamental list types. Examples include CLisp, Haskell and F#. This is different to mainstream languages, where the native list types are arrays.

Why is that?

For CLisp (being dynamically typed) I get the idea that the cons is general enough to also be the base of lists, trees, etc. This might be a tiny reason.

For statically typed languages, though, I can't find a good reasoning, I can even find counter-arguments:

  • Functional style encourages immutability, so the linked list's ease of insertion is less of an advantage,
  • Functional style encourages immutability, so also data sharing; an array is easier to share "partially" than a linked list,
  • You could do pattern matching on a regular array just as well, and even better (you could easily fold from right to left for example),
  • On top of that you get random access for free,
  • And (a practical advantage) if the language is statically typed, you can employ a regular memory layout and get a speed boost from the cache.

So why prefer linked lists?

share|improve this question
2  
Coming from the comments on @sepp2k's answer, I think an array is easier to share "partially" than a linked list needs clarification as to what you mean. Due to their recursive nature, the opposite is true as I understand it - you can partially share a linked list easier by passing along any node in it, while an array would need to spend time making a new copy. Or in terms of data sharing, two linked lists can point to the same suffix, which just plain isn't possible with arrays. –  Izkata Jan 29 '12 at 15:19
    
If an array defines itself as an offset,length,buffer triple, then you could share an array by making a new one with offset+1,length-1,buffer. Or have a special type of array as the subarray. –  Dobes Vandermeer Oct 17 '12 at 7:01

4 Answers 4

up vote 11 down vote accepted

The most important factor is that you can prepend to an immutable singly linked list in O(1) time, which allows you to recursively build up n-element lists in O(n) time like this:

// Build a list containing the numbers 1 to n:
foo(0) = []
foo(n) = cons(n, foo(n-1))

If you did this using immutable arrays, the runtime would be quadratic because each cons operation would need to copy the whole array, leading to a quadratic running time.

Functional style encourages immutability, so also data sharing; an array is easier to share "partially" than a linked list

I assume by "partially" sharing you mean that you can take a subarray from an array in O(1) time, whereas with linked lists you can only take the tail in O(1) time and everything else needs O(n). That is true.

However taking the tail is enough in many cases. And you have to take into account that being able to cheaply create subarrays doesn't help you if you have no way of cheaply creating arrays. And (without clever compiler optimizations) there is no way to cheaply build-up an array step-by-step.

share|improve this answer
    
That's not true at all. You can append to arrays in amortized O(1). –  DeadMG Jan 29 '12 at 2:28
2  
@DeadMG Yes, but not to immutable arrays. –  sepp2k Jan 29 '12 at 2:30
    
"partially sharing" - I think both that two cons lists can point to the same suffix list (dunno why you'd want this), and that you can pass a midpoint instead of the beginning of the list to another function without having to copy it (I've done this many times) –  Izkata Jan 29 '12 at 5:00
    
@Izkata The OP was talking about partially sharing arrays though, not lists. Also I've never heard what you're describing referred to as partial sharing. That's just sharing. –  sepp2k Jan 29 '12 at 5:19
    
@sepp2k The OP is (incorrectly) using Array and List interchangeably, calling a "cons list" a "functional style" array. See his second bullet point, the specific part I was referring to. And it's partial sharing because, for example, the function doesn't even know the rest of the list exists - it only sees a part of the list. –  Izkata Jan 29 '12 at 7:11

I think it comes down to lists being rather easily implemented in functional code.

Scheme:

(define (cons x y)(lambda (m) (m x y)))

Haskell:

data  [a]  =  [] | a : [a]

Arrays are harder and not nearly as pretty to implement. If you want them to be extremely fast then they'll have to be written low-level.

Additionally, recursion works much better on lists than arrays. Consider the number of times you've recursively consumed/generated a list vs indexed an array.

share|improve this answer
    
I wouldn't say it's accurate to call your scheme version an implementation of linked lists. You won't be able to use it to store anything but functions. Also arrays are harder (impossible actually) to implement in any language that doesn't have built-in support for them (or memory chunks), while linked lists only require something like structs, classes, records or algebraic data types to implement. That's not specific to functional programming languages. –  sepp2k Jan 29 '12 at 2:29
    
@sepp2k What do you mean "store anything but functions"? –  Pubby Jan 29 '12 at 2:54
    
What I meant was that lists defined that way can't store anything that's not a function. That's not actually true though. Dunno, why I've thought that. Sorry about that. –  sepp2k Jan 29 '12 at 3:00

You can use Cons nodes easily only if you have a garbage collected language.

Cons Nodes matche a lot with the functional programming style of recursive calls and immutable values. So it fits well into the mental programmer model.

And don't forget historical reasons. Why are they still called Cons Nodes and worse still use car and cdr as accessors? People learn it from text books and courses and then use it.

You are right, in the real world arrays are much easier to use, consume only half the memory space and are much performanter because of cache level misses. There is no reason to use them with imperative languages.

share|improve this answer

Linked lists are important for the following reason:

Once you take a number like 3, and convert it to successor sequence like succ(succ(succ(zero))), and then use substitution to it with {succ=List node with some memory space}, and {zero = end of list}, you'll end up with a linked list (of length 3).

The actual important part is numbers, substitution, and memory space and zero.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.