F# list

List data structure and common operations

F# list is a linked list, where each node has a link to the next node. It is also immutable. See mastering F# lists. Available operations:

• Cons - add an element to the beginning of a list. 'a –> 'a list –> 'a list, constant time O(1). Example 1::[2..4].
• Concat - join two lists together. 'a list * 'a list -> 'a list, O(n) where n is the length of the first list. Example: [2; 3; 4] @ [5 .. 7]

Avoid @

Avoid list concatenation with @, from SO:

In F# the list type is implemented as a singly linked list. Because of this you get different performance for x @ y and y @ x if x and y are of different length. That’s why your seeing a difference in performance. (x @ y) has running time of X.length.

The append operator (@) creates a new list by concatenating two lists, so appending a shorter list to a longer list is slower than appending a longer list to a shorter list, since it needs to copy the first list (lists are immutable, duh…).

Correct way to build a list

To build a list prepend the new data to the front and then reverse (if e.g. using List.foldBack).

See SO Why can you only prepend to lists in functional languages?.

And why not just use doubly-linked list on SO, spoiler alert - requires mutability.