How does the implementation of list in F# work?

Question

I'm curious as to how the list module/type works in F#, specifically does it optimise this?

let xs = ["1"; "2"; "3"]

let ys = "0"::xs

let zs = ["hello"; "world"]@xs

I've looked over some of the source https://github.com/fsharp/fsharp/blob/68e37d03dfc15f8105aeb0ac70b846f82b364901/src/fsharp/FSharp.Core/prim-types.fs#L3493 seems to be the relevant area.

I would like to know if xs is copied when making ys.

I would have thought it's easy to just point to the existing list if you just cons element.

If you are concatenating I imagine it might be impossible as it would require mutating the last element of the list to point to the next one?

If someone could annotate/paste snippets of code from FSharp.Core that would be ideal.

Answer 1

So the implementation of List is a little odd. It is actually implemented as a discriminated union. From the spec:

type 'T list =
| ([])  
| (::)  of 'T * 'T list 

So you can think of :: as a function that takes two arguments and creates a tuple (which is fast as it is independent of the list size).

@ is much more complicated. Here is the implementation:

    let (@) l1 l2 = 
        match l1 with
        | [] -> l2
        | (h::t) -> 
        match l2 with
        | [] -> l1
        | _ -> 
          let res = [h] 
          let lastCons = PrivateListHelpers.appendToFreshConsTail res t 
          PrivateListHelpers.setFreshConsTail lastCons l2;
          res

The two weird functions basically mutate the list in place. appendToFreshConsTail copies the list and returns the last element. setFreshConsTail then changes the last element so that its next element is set to l2 rather than [] joining the lists.