Understanding pattern matching with cons operator
-
27-09-2019 - |
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?
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).
OTHER TIPS
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.)
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.