You are previewing Programming F#.

Programming F#

Cover of Programming F# by Chris Smith Published by O'Reilly Media, Inc.
O'Reilly logo

Mastering Lists

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 array).

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).

Structure of an FSharpList type

Figure 7-1. Structure of an FSharpList type

List Operations

Perhaps the greatest benefit of the FSharpList type is how simple it is to use. While the List 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 append.


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 ...

The best content for your career. Discover unlimited learning on demand for around $1/day.