Why do functional languages make such heavy use of lists?

Question

I mean what advantages does list has on other data structures which make it almost inevitable in functional languages?

Answer 1

"There is no spoon."

What if I told you there is no such thing as strings? There exists only lists of single characters.

Then what if I told you there is no such thing as a list? There exists only pairs.

; construct a pair of a and b
(cons 'a 'b)           ; => ('a 'b)

; get the first element of the pair
(first (cons 'a 'b))   ; => 'a

; get the second element of the pair
(second (cons 'a 'b))  ; => 'b

; create a "list"
(define x (cons 'a (cons 'b (cons 'c (cons 'd (cons 'e null))))))
; => ('a ('b ('c ('d ('e ())))))

; get the third element in the "list", x
(first (second (second x)))
; => 'c

Now what if I told you there is no such thing as pairs? There exists only lambdas.

(define (cons x y)
  (λ (f) (f x y)))

(define (first p)
  (p (λ (x y) x)))

(define (second p)
  (p (λ (x y) y)))

Of course this is just one possible implementation. But it's important to realize that it's all just an illusion.

Data abstraction is truly magical. Good languages allow you to invent any structure you wish to work with and define any constructors/selectors that make it useful to work with your structure. Some languages just offer more syntactic sugar than others.

Lists are common because, as programmers, we often deal with ordered collections of things. Other common types are Sets and Maps. Just don't fool yourself into thinking it's anything super special ^,^

Answer 2

Functional languages prefer immutability so, when it comes to data structures, functional languages prefer persistent data structures. In brief, persistent data structures are data structures where we can continue to access any previous version of the structure as well as the current version. We do not mutate the existing data structure, we simply use the existing data structure as a basis to create a new one.

This can be done for any data structure simply by copying. For instance, consider some pseudo-F#:

let array1 = [| 1, 2, 3, 4, 5 |]
let array2 = append 6 array1 // [| 1, 2, 3, 4, 5, 6 |]

To implement the append function, we'd have to create a new array of n+1 size and populate it with a copy of array1 and the element to be appended.

Note how this isn't very efficient, every append requires both n copies and allocating memory for the entire structure.

Consider instead we define some type:

type List<'a> = 
    |Empty
    |Cons of 'a * List<'a>

Using the Cons case, we can construct new lists from an old list and a single element.

Consider we now have a list of 1 million elements:

let list1 = [1..1000000]
let list2 = Cons (0, list1) // [0..1000000]

In this case, list2 simply refers to list1, no copying is required. Hence, prepending to the start of the list is an O(1) operation and the memory footprint only grows linearly with each element despite the data persistence.

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.