Whereas arrays and the
List<_> type make up the backbone data
structure for imperative programming, lists are the cornerstone of
functional programming. Lists offer a guarantee of immutability, which
helps support function composition and recursion, as well as free you from
needing to allocate all the memory up front (such as fixed size
Although lists are pervasive when programming in the functional style, I have not yet covered how to use them efficiently. Lists in F# have unique performance characteristics that you should be aware of or else you run the risk of unexpectedly poor performance.
F# lists are represented as a linked list, visualized in Figure 7-1. Every element of the list has a value as well as a reference to the next element in the list (except of course the last element of the list).
Figure 7-1. Structure of an FSharpList type
Perhaps the greatest benefit of the
FSharpList type is how
simple it is to use. While the
module offers plenty of functionality for using existing lists,
when you build up lists dynamically, there are only two
operations to choose from, cons and
The cons operator,
::, adds an element to the front of an existing list. When the cons operator is used, the result is a new list; the input list is unchanged because all the work is done by simply allocating a new list element and setting its next element ...