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?

Not really a duplicate of https://stackoverflow.com/questions/1320139/why-is-appending-to-a-list-bad since that's a Scala question, and the F# list implementation is not guaranteed to match the Scala implementation (even though in this instance it does). Besides, someone searching for F# questions probably won't include the `[scala]` tag in their search. — rmunn, Jul 04 '19 at 02:52
@munn It's tagged with [scala], but is not fundamentally Scala-specific. The question itself contains no Scala code, and the question and answers could all easily be rephrased to reference Scala only by example, which is probably what should be done if SO is to live up to its goal of being a knowledge base. Unfortunately that goal isn't very well communicated, and such a change would probably be resisted and create more of a mess than anything. — glennsl, Jul 04 '19 at 12:10

score 11 · Accepted Answer · answered Jul 03 '19 at 19:21

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.

that was my assumption, but I did not find it anywhere in documentation. thank you — dr11, Jul 03 '19 at 20:14
To be more specific: with `@`, you copy the whole left list; the right list, as with `::`, is reused. — Tarmil, Jul 04 '19 at 08:10

cons operator (::) performance in F#

1 Answers1