What are the advantages of Cons?

Question

Many functional programming languages support and recommend the data constructor Cons (for lists like (1, (2, (3))), such as Haskell and Scala.

But what are its advantages? Such lists can neither be randomly accessed, nor be appended to in O(1).

Answer 1

Cons (a shorthand for "construct") is not a data structure, it's the name of the operation for creating a cons-cell . And by linking together several cells a data structure can be built, in particular - a linked list. The rest of the discussion assumes that a linked list is being created with cons operations.

Although it's possible to append in O(1) at the head, accessing elements randomly by index is a costly operation, that requires the traversal of all the elements before the one that's being accessed.

The advantages of a linked list? it's a functional data structure, cheap to create or recreate in case of modifications; it allows sharing of nodes between several lists and it allows easy garbage collection. It's very flexible, with correct abstractions it's possible to represent other, more complex data structures such as stacks, queues, trees, graphs. And there are many, many procedures written specifically for manipulating lists - for instance map, filter, fold, etc. that make working with lists a joy. Finally, a list is a recursive data structure, and recursion (specially tail recursion) is the preferred way to solve problems in functional programming languages; so in these languages it's natural to have a recursive data structure as the main data structure.