F#: why to have both '::' and '@'

Question

I started to read about F# recently, and obviously I got one novice-level question very soon. It is about lists (collections).

According to F# manuals, there are two operations to construct lists, they are cons (aka ::) and @. Given the fact @ is more versatile (can merge sublists, not single elements, and can append to the tail as well, unlike the cons operation), my question is: at which situation we must use exactly :: instead of @ to avoid ambiguity, or non-wanted side-effects and so on?

In other words: is :: theoretically redundant or not?

Answer 1

The list type has two constructors: [] and ::. If :: were removed, only the [] constructor would be left, making it impossible to create non-empty lists.

Note that something like [1;2;3] is syntactic sugar for 1::2::3::[], so it relies on the existence of ::.

Similarly, @ is a function that's defined using ::, so if :: didn't exist, neither could @.

Note that @ isn't suitable as a replacement for :: in list's definition as, if you don't already have a way to construct non-empty lists, @ can't be used to create them ([] @ [] is still an empty list).

And even if you added a constructor for single-item lists, @ would lead to an ambiguous representation because [1;2;3] could be represented either as ([1] @ [2]) @ [3] or as [1] @ ([2] @ [3]) (plus, you could just add @ [] anywhere you want). So you'd end up with several different representations for semantically equivalent lists.

Answer 2

It's the other way around, @ is for all intents and purposes redundant, and I believe the reasons for it to exist as an operator in the core library are purely historical.

I would argue that it would have been better if it was retired and the usage of List.append recommended in its place.

The way things stand today is that @ is defined in prim-types.fs as an equivalent of the following function:

let rec (@) x y = 
    match x with 
    | [] -> y 
    | (h::t) -> h :: (t @ y)

and is later reexposed as List.append:

let append list1 list2 = list1 @ list2

There's very little reason why it should be exposed as an operator in the first place, other than "OCaml is doing it".

In practice, it's fairly rare to have a valid case for appending lists and much of collection processing in F# happens using sequences or other collection types that are better suited to concatenation, yet do not offer a dedicated operator for it. Singly-linked lists are very much the textbook example of a structure you do not want to append to.

In that way, @ is purely educational - it seems like it only exists to trip up newcomers to the language (or remind them to be mindful of performance characteristics of data structures they happen to be using).