Why implement an immutable list as a linked-list?

Question

According to F#'s list documentation:

• "A list in F# is an ordered, immutable series of elements of the same type"

• "Lists in F# are implemented as singly linked lists"

Why not implement it contiguously in memory since it immutable and thus has a fixed size? Why ever use an F# list instead of an F# array?

Answer 1

They serve different purposes, for instance:

You use an Array in F# to store big amounts of data that needs to be accessed randomly with relative low overhead.

A List in F# is useful when you need to accumulate something over iterations of a recursive function. Arrays don't play well here, since they have a fixed size.

With a list, you can prepend all elements of ListM (size M) to ListN (size N) in O(M) time. Similarly, you can prepend a single Element to any list in O(1) time.