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