Incomplete pattern match when two patterns share a `when` clause

Question

A common surprise for beginning F# programmers is the fact that the following is an incomplete match:

let x, y = 5, 10
match something with
| _ when x < y -> "Less than"
| _ when x = y -> "Equal"
| _ when x > y -> "Greater than"

But I just encountered a situation that surprised me. Here's a small bit of sample code to demonstrate it:

type Tree =
| Leaf of int
| Branch of Tree list

let sapling = Branch [Leaf 1]  // Small tree with one leaf
let twoLeafTree = Branch [Leaf 1; Leaf 2]

let describe saplingsGetSpecialTreatment tree =
    match tree with
    | Leaf n
    | Branch [Leaf n] when saplingsGetSpecialTreatment ->
        sprintf "Either a leaf or a sapling containing %d" n
    | Branch subTree ->
        sprintf "Normal tree with sub-tree %A" subTree

describe true sapling // Result: "Either a leaf or a sapling containing 1"
describe false sapling // Result: "Normal tree with sub-tree [Leaf 1]"
describe true twoLeafTree // Result: "Normal tree with sub-tree [Leaf 1; Leaf 2]"
describe false twoLeafTree // Result: "Normal tree with sub-tree [Leaf 1; Leaf 2]"

This version of the describe function produced the "Incomplete pattern matches on this expression" warning, even though the pattern match is, in fact, complete. There are no possible trees that will not be matched by that pattern match, as can be seen by removing the specific branch of the match that had a when expression in it:

let describe tree =
    match tree with
    | Leaf n -> sprintf "Leaf containing %d" n
    | Branch subTree ->
        sprintf "Normal tree with sub-tree %A" subTree

This version of describe returns the "Normal tree" string for both the sapling and twoLeafTree trees.

In the case where the match expression contains nothing but when expressions (like the first example where x and y are being compared), it is reasonable that the F# compiler might not be able to tell whether the match will be complete. After all, x and y might be types with a "weird" implementation of comparison and equality where none of those three branches are true.*

But in cases like my describe function, why doesn't the F# compiler look at the pattern, say "If all the when expressions evaluated to false, there would still be a complete match" and skip the "incomplete pattern matches" warning? Is there some specific reason for this warning showing up here, or is it just a case of the F# compiler being just a little bit simplistic here and giving a false-positive warning because its code wasn't sophisticated enough?

* In fact, it is possible to set x and y to values such that x < y, x = y, and x > y are all false, without ever stepping outside the "normal" bounds of the standard .Net type system. As a special bonus question/puzzle, what are these values of x and y? No custom types needed to answer this puzzle; all you need is types provided in standard .Net.

Crowbar

Answer 1

In F# match syntax, the when guards apply to all cases enumerated just before it, not just to the last one.

In your specific scenario, the guard when saplingsGetSpecialTreatment applies to both Leaf n and Branch [Leaf n] cases. So this match will fail for the case when tree = Leaf 42 && saplingsGetSpecialTreatment = false

The following would be complete, since the Leaf case now has its own branch:

let describe saplingsGetSpecialTreatment tree =
    match tree with
    | Leaf n ->
        sprintf "Either a leaf or a sapling containing %d" n
    | Branch [Leaf n] when saplingsGetSpecialTreatment ->
        sprintf "Either a leaf or a sapling containing %d" n
    | Branch subTree ->
        sprintf "Normal tree with sub-tree %A" subTree

Distributary

To clarify, by "enumerated just before it", you mean without an intervening -> – Caban

Yes, that is what I mean. – Distributary

My original code actually had the Branch case with special treatment first and the Leaf n case second. The Branch case had a when condition, but omitted a -> since I wanted to also match the Leaf case. And what I got was the error "Unexpected symbol '|' in pattern matching. Expected '->' or other token." At the time I didn't understand why that failed, but putting the Leaf case worked; now that I know that when clauses apply to all the patterns in that particular "group" (all the patterns that share a ->), I understand the syntax error. Thanks! – Crowbar

Answer 2

Just clarifying Fyodor's post with an extra example. Think of it as a when y = 3 section, an otherwise section, and then, for everything else

let f y x = 
  match x with
  | 0 
  | 1 
  | 2 when y = 3 -> "a"
  | 0
  | 1
  | 2            -> "b"
  | _            -> "c"

[0 .. 3] |> List.map (f 3)
[0 .. 3] |> List.map (f 2)

FSI

val f : y:int -> x:int -> string

> val it : string list = ["a"; "a"; "a"; "c"]

> val it : string list = ["b"; "b"; "b"; "c"]

So, is this a sensible default? I think so.

Here's a more explicit version:

let f2 y x =
  match x,y with
  | 0,3
  | 0,3
  | 0,3 -> "a"
  | 0,_
  | 1,_
  | 2,_ -> "b"
  | _ -> "c"

[0 .. 3] |> List.map (f2 3)
[0 .. 3] |> List.map (f2 2)

... and a more compact version:

let f3 y x = x |> function | 0 | 1 | 2 when y = 3 -> "a"
                           | 0 | 1 | 2 -> "b"
                           | _ -> "c"

Lightless