Understanding pattern matching with cons operator

Question

In "Programming F#" I came across a pattern-matching like this one (I simplified a bit):

let rec len list = 
  match list with
  | [] -> 0
  | [_] -> 1
  | head :: tail -> 1 + len tail;;

Practically, I understand that the last match recognizes the head and tail of the list. Conceptually, I don't get why it works. As far as I understand, :: is the cons operator, which appends a value in head position of a list, but it doesn't look to me like it is being used as an operator here. Should I understand this as a "special syntax" for lists, where :: is interpreted as an operator or a "match pattern" depending on context? Or can the same idea be extended for types other than lists, with other operators?

Answer 1

It is special syntax for lists. You can think of the list type as a discriminated union thusly:

type list<'T> =         // '
    | Nil
    | Cons of 'T * list<'T>

except that there's special syntax that makes Nil be [] and Cons(h,t) be h::t. Then it's just normal pattern matching on a discriminated union. Does that help?

(Possibly see also this blog entry.)

Answer 2

It is used as a formatter or formally pattern, `list' is matched to the three patterns:

[] means the list is empty

[_] means the list has one element, since you don't care about what the element is, so simply put _ there, you can also use [a].

head::tail means that the list does have two parts: a head and a tail.

You can view F# pattern matching as a powerful if then else structure.

Answer 3

In addition to Brian's answer, there are a few points that are worth noting. The h::t syntax can be used both as an operator and as a pattern:

let l = 1::2::[]                    // As an operator
match l with x::xs -> 1 | [] -> 0   // As a pattern

This means that it is a bit special construct, because other operators (for example +) cannot be used as patterns (for decomposing the result back to the arguments of the operator) - obviously, for +, this would be ambiguous.

Also, the pattern [_] is interesting, because it is an example of nested pattern. It composes:

• _ - Underscore pattern, which matches any value and doesn't bind any symbols
• [ <pattern> ] - Single-element list pattern, which matches a lists with single elements and matches the element of the list with the nested <pattern>.

You could also write match 1::[] with | [x] -> x which would return the value of the single element (in this case 1).