Menu
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?
943
There are many other persistent data structures, Binary Trees are often used to make immutable Sets and Dictionaries. Finger Trees can be the basis of structures like Deques and Priority queues. So, in short, lists are widely used in functional languages because they are a simple, efficient, persistent data structure.
List is the most versatile data type available in functional programming languages used to store a collection of similar data items. The concept is similar to arrays in object-oriented programming. List items can be written in a square bracket separated by commas.
The cons list is perhaps the most basic immutable data structure: a singly linked list built out of 'cons cells,' which are cells containing two values, the left hand value being the head of the list and the right hand value being a reference to the rest of the list, or a Nil value denoting the end of the list.
If you think of a list like a caterpillar, the function head will return the first item in the list (its head). The function tail will return all of the other items (as a new list). Figure 1: Head and tail of a list.
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.
118
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)
21
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
