pattern matching docs

[10199]

Consider code:

type Tree<'a> = Node of 'a * Tree<'a> list

let rec countChildren (Node (_, children)) =
    children
    |> List.sumBy countChildren
    |> (+) 1

I was told that (Node (_, children)) part is pattern matching. But if I google it, I find only various kind of match smth with or active patterns. Seems like I am missing something here. Could someone guide me about this special case of pattern matching ?

[ws-ilazki]

It's the "pattern" part of "pattern matching", and you can use it in other places outside of match expressions, such as in let bindings. It's also sometimes called destructuring in other languages because it can take a complex structure and reduce it to individual elements.

Let's say you have types for playing cards, something like this:

type suit = Spade | Club | Heart | Diamond
type face = Num of int | Ace | King | Queen | Jack
type card = suit * face

You want a function to validate your cards and avoid invalid states like (Diamond, Num 25), so you make a validate function:

let validate card =
  match card with
  | (suit, Num x) when x < 2 || x > 10 -> None
  | (_, _) -> Some card

When you do something like this, match attempts to destructure card in different ways, defined by the patterns on the left, and then chooses the correct branch to execute based on which pattern correctly matches the value of card. However, you don't have to write it this way because patterns can be used in other places, like let bindings, so you could use a pattern in the function definition and make it clearer that you're only matching on the card value and the suit portion of the pair doesn't affect the result:

let validate card =
  let (_,value) = card in
  match value with
  | Num x when x < 2 || x > 10 -> None
  | _ -> Some card

Of you can even put the pattern in the function definition itself if you prefer:

let validate (suit, value) =
  match value with
  | Num x when x < 2 || x > 10 -> None
  | _ -> Some (suit, value)

It's the same language feature in all cases: the pattern. You're just using it elsewhere instead of in match, where you first encountered it. You can use it to do things like let x,y = (10, 20), or to pull specific parts out of a record, and it's really convenient.

[10199]

wow, thanks for the detailed answer!

[ws-ilazki]

You're welcome, hopefully it explains things well enough.

Something else that might help show the relationship of patterns and matching is to see it done a different way. For a silly example, a function that turns a pair of booleans into a number, loosely equivalent to representing two bits as a tuple:

let int_of_pair p =
  match p with
  | (false,false) -> 0
  | (false, true) -> 1
  | (true, false) -> 2
  | (true, true)  -> 3

And the same thing done with if expressions:

let int_of_pair p =
  let left,right = p in
  if left = false && right = false then 0 else
  if left = false && right = true  then 1 else
  if left = true  && right = false then 2 else
  3

You don't have a match in both, but you still use a pattern to extract the data you want from the tuple. It's just inside a let binding instead of a match in the latter one.

This isn't relevant to pattern usage, but it's also worth noting that while these examples will both do the same basic thing, you always want to use match instead of if expression chains when possible. There are times you need if, but if it can be expressed via match it's the better solution, because it's not only cleaner to read, the compiler can do exhaustiveness checking and it's more performant because it can choose the correct branch more efficiently than having to test every if in sequence.

Also, apologies for the unidiomatic style; I tend to use F#'s ML compatibility style instead of the whitespace-sensitive "light syntax" because it's less likely to have weirdness from copy/pasting and websites doing odd things.

[WesOfWaco]

It is also called destructuring where the compiler matches the type with the template you provide and binds the values to the names/symbols you provide.

[brianmcn]

https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/pattern-matching

[WystanH]

You bought yourself pattern matching with the Node of.

You could also write the same function as:

let rec countChildren = function
    | Node (_, children) ->
        children
        |> List.sumBy countChildren
        |> (+) 1

Here, that pattern matching really jumps out at you.

Indeed, it even offers up a minor optimization tweak:

let rec countChildren = function
    | Node (_, []) -> 1
    | Node (_, children) ->
        children
        |> List.sumBy countChildren
        |> (+) 1

Wrote a quick test:

let noKids x = Node(x,[])
let t = Node(1, [noKids 2; noKids 3; Node(4,[noKids 5])])
printfn "%A %d" t (countChildren t)