June 03, 2020
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
Concat- join two lists together.
'a list * 'a list -> 'a list,
nis the length of the first list. Example:
[2; 3; 4] @ [5 .. 7]
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…).
To build a list prepend the new data to the front and then reverse (if e.g. using
And why not just use doubly-linked list on SO, spoiler alert - requires mutability.