Lists in

About Lists

A list in F# is an immutable collection of zero or more values. The values in a list must all have the same type. As lists are immutable, once a list has been constructed, its value can never change. F# list have a head (the first element) and a tail (everything after the first element). The tail of a list is itself a list.

Lists can be defined as follows:

let empty = []
let emptyAlternative = List.empty

let singleValue = [5]
let singleValueAlternative = List.singleton 5

let threeValues = ["a"; "b"; "c"]

The most common way to add an element to a list is through the :: (cons) operator:

let twoToFour = [2; 3; 4]
let oneToFour = 1 :: twoToFour
// => [1; 2; 3; 4]

List can be appended using the @ operator or List.append:

[6; 7] @ [8; 9]           // => [6; 7; 8; 9]
List.append [6; 7] [8; 9] // => [6; 7; 8; 9]

Lists are manipulated by functions and operators defined in the List module. Some of these functions are also available as properties of a list instance:

List.length [7; 8] // => 2
[7; 8].Length      // => 2

There is no right or wrong option here. In general, the functions in the List module play better with type inference, whereas the properties allow for more concise code.

Any functions/operators that appear to modify a list (such as adding an element), will actually return a new list. Performance is usually not an issue though, as the implementation of lists prevents unnecessary allocations/copies.

As lists are implemented as singly linked lists, prepending an element (using the :: operator) is very fast, while accessing an element by index is potentially relatively slow.

List can also be processed using pattern matching through the list and cons patterns:

let describe list =
    match list with
    | [] -> "Empty list"
    | [ 1 ] -> "Singleton list with 1"
    | head::tail -> sprintf "Non-empty list with head: %d" head

describe []        // => "Empty list"
describe [1]       // => "Singleton list with 1"
describe [5; 7; 9] // => "Non-empty with head: 5"

You can also discard a value when pattern matching; when you do not care about a value in a specific case (i.e. you aren't going to use a value) you can use an underscore ('_') to signify this:

let describe list =
    match list with
    | [] -> "Empty list"
    | [x] -> "List with one item"
    | [_; y] -> "List with two items (first item ignored)"
    | _ -> "List with many items (all items ignored)"

describe []        // => "Empty list"
describe [1]       // => "List with one item"
describe [5; 7]     // => "List with two items (first item ignored)"
describe [5; 7; 9] // => "List with many items (all items ignored)"

The single '_' should always come last when pattern matching, every value that doesn't match any of the other cases will be handled by this case.