17

I have only used 3 functional languages -- scala, erlang, and haskell, but in all 3 of these, the correct way to build lists is to prepend the new data to the front and then reversing it instead of just appending to the end. Of course, you could append to the lists, but that results in an entirely new list being constructed.

Why is this? I could imagine it's because lists are implemented internally as linked lists, but why couldn't they just be implemented as doubly linked lists so you could append to the end with no penalty? Is there some reason all functional languages have this limitation?

ryeguy
  • 65,519
  • 58
  • 198
  • 260

5 Answers5

21

Lists in functional languages are immutable / persistant.

Appending to the front of an immutable list is cheap because you only have to allocate a single node with the next pointer pointing to the head of the previous list. There is no need to change the original list since it's only a singly linked list and pointers to the previous head cannot see the update.

Adding a node to the end of the list necessitates modifying the last node to point to the newly created node. Only this is not possible because the node is immutable. The only option is to create a new node which has the same value as the last node and points to the newly created tail. This process must repeat itself all the way up to the front of the list resulting in a brand new list which is a copy of the first list with the exception of thetail node. Hence more expensive.

JaredPar
  • 733,204
  • 149
  • 1,241
  • 1,454
  • 1
    Couldn't the list data structure have a pointer to the tail node, and then modify the tail node's "next" variable to point to the new node? – ryeguy Sep 16 '09 at 20:50
  • @ryeguy, just added an explanation for why that's not possible – JaredPar Sep 16 '09 at 20:52
  • 2
    Jep. But *changing* something is actually mutually exclusive with *immutability*, which means, that you *cannot* change anything. – Dirk Sep 16 '09 at 20:53
  • not necessarily. You can just carry around an additional parameter - the list's size (or/and another one - its tail pointer) - in the representation. Then it is OK to surgically append new cell in O(1) time, and use the same list with the updated, incremented size (and moved tail pointer). The old variable will not access the newly grown list past its old tail. – Will Ness Feb 20 '13 at 18:00
  • @WillNess How would that work if you append to the same list twice (e.g. `xs = [1,2,3]; ys = cons(23, xs); zs = cons(42, xs)`)? – sepp2k Feb 20 '13 at 18:31
  • @sepp2k was thinking more of the situation where one list gets progressively fleshed out, getting longer and longer. – Will Ness Feb 20 '13 at 20:22
  • @sepp2k What if the new list that represents xs being appended contains 2 pointers, 1 to xs which isn't mutated, and another to the new list containing the append (such as List(23))? Then when that list is accessed it can read both lists and combine them still in O(1) time, since it has pointers to both? – user4779 Mar 11 '23 at 03:46
  • 1
    @user4779 What you're describing is basically a tree. You can use trees this way, but then accessing the first element (and thus pattern matching) isn't going to be O(1) anymore. Without balancing the tree, it would become O(n) in the worst case (i.e. accessing the first element of a list where every element was added to the end). If you balance the tree (which of course adds extra complexity), it becomes O(log n). That's actually feasible, but still a trade off compared to lists. – sepp2k Mar 11 '23 at 15:09
5

Because there is no way to append to a list in O(1) without modifying the original (which you don't do in functional languages)

Community
  • 1
  • 1
sepp2k
  • 363,768
  • 54
  • 674
  • 675
2

Because it's faster

They certainly could support appending, but it's so much faster to prepend that they limit the API. It's also kind of non-functional to append, as you must then modify the last element or create a whole new list. Prepend works in an immutable, functional, style by its nature.

DigitalRoss
  • 143,651
  • 25
  • 248
  • 329
2

That is the way in which lists are defined. A list is defined as a linked list terminated by a nil, this is not just an implementation detail. This, coupled with that these languages have immutable data, at least erlang and haskell do, means that you cannot implement them as doubly linked lists. Adding an element would them modify the list, which is illegal.

rvirding
  • 20,848
  • 2
  • 37
  • 56
1

By restricting list construction to prepending, it means that anybody else that is holding a reference to some part of the list further down, will not see it unexpectedly change behind their back. This allows for efficient list construction while retaining the property of immutable data.

Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285