cons operator (::) performance in F#

Question

In official documentation it is stated that :: is faster than @.

Once all lists are immutable in F#, why is there a difference? In any case the original list should be copied. but in case with :: we will prepend, while in case with @ we will append. it should be the same complexity.

What is the difference?

Answer 1

Your assumption is incorrect.

When you prepend with ::, the original list is not, in fact, copied. The original list remains in place, in memory, exactly where it was, and the new list now consists of the new element and a pointer to the original list, which is its tail.

Consider this:

let x = [1;2;3]
let y = 4 :: x

This program will produce the following memory layout:

 y -> 4
       \
        v
        1 -> 2 -> 3 -> (END)
        ^
       /
      x

This is only possible because lists are immutable: since we know that the original list will never change, we can just conscript it to be the tail of our new list.

This sort of arrangement is generally called "persistent data structure". Singly-linked list is only the simplest one of such structures.

---

When appending with @, on the other hand, you do indeed have to copy the whole original list. You cannot reuse any part of it.

This is why prepending is faster.