Search code examples
f#pattern-matchingcons

Understanding pattern matching with cons operator


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?


Solution

  • 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).