Incomplete match with AND patterns

active-pattern, f#, pattern-matching

Solution

If you code the destinction between ground terms and complex terms into the type system, you can avoid the runtime check and make them be complete pattern matches.

type Num = int
type Name = string

type GroundTerm = 
    | Con of Num
    | Var of Name
type ComplexTerm =
    | Add of Term * Term
    | Sub of Term * Term
    | Mult of Term * Term
    | Div of Term * Term
    | Pow of Term * Term
    | Neg of Term
and Term =
    | GroundTerm of GroundTerm
    | ComplexTerm of ComplexTerm


let (|Operator|) ct =
    match ct with
    | Add(_) -> "+"
    | Sub(_) | Neg(_) -> "-"
    | Mult(_) -> "*"
    | Div(_) -> "/"
    | Pow(_) -> "**"

let (|Unary|Binary|) ct = 
    match ct with
    | Add(x, y) -> Binary(x, y)
    | Sub(x, y) -> Binary(x, y)
    | Mult(x, y) -> Binary(x, y)
    | Div(x, y) -> Binary(x, y)
    | Pow(x, y) -> Binary(x, y)
    | Neg(x) -> Unary(x)

let (|Terminal|) gt =
    match gt with
    | Con x -> Terminal(string x)
    | Var x -> Terminal(string x)

let rec format expr =
    match expr with
    | ComplexTerm ct ->
        match ct with
        | Unary(x) & Operator(op) -> sprintf "%s(%s)" op (format x)
        | Binary(x, y) & Operator(op) -> sprintf "(%s %s %s)" (format x) op (format y)
    | GroundTerm gt ->
        match gt with
        | Terminal(x) -> x

also, imo, you should avoid boxing if you want to be type-safe. If you really want both cases, make two pattern. Or, as done here, just make a projection to the type you need later on. This way you avoid the boxing and instead you return what you need for printing.

Problem

I've defined an expression tree structure in F# as follows: ``` type Num = int type Name = string type Expr = | Con of Num | Var of Name | Add of Expr * Expr | Sub of Expr * Expr | Mult of Expr * Expr | Div of Expr * Expr | Pow of Expr * Expr | Neg of Expr ``` I wanted to be able to pretty-print the expression tree so I did the following: ``` let (|Unary|Binary|Terminal|) expr = match expr with | Add(x, y) -> Binary(x, y) | Sub(x, y) -> Binary(x, y) | Mult(x, y) -> Binary(x, y) | Div(x, y) -> Binary(x, y) | Pow(x, y) -> Binary(x, y) | Neg(x) -> Unary(x) | Con(x) -> Terminal(box x) | Var(x) -> Terminal(box x) let operator expr = match expr with | Add(_) -> "+" | Sub(_) | Neg(_) -> "-" | Mult(_) -> "*" | Div(_) -> "/" | Pow(_) -> "**" | _ -> failwith "There is no operator for the given expression." let rec format expr = match expr with | Unary(x) -> sprintf "%s(%s)" (operator expr) (format x) | Binary(x, y) -> sprintf "(%s %s %s)" (format x) (operator expr) (format y) | Terminal(x) -> string x ``` However, I don't really like the `failwith` approach for the `operator` function since it's not compile-time safe. So I rewrote it as an active pattern: ``` let (|Operator|_|) expr = match expr with | Add(_) -> Some "+" | Sub(_) | Neg(_) -> Some "-" | Mult(_) -> Some "*" | Div(_) -> Some "/" | Pow(_) -> Some "**" | _ -> None ``` Now I can rewrite my `format` function beautifully as follows: ``` let rec format expr = match expr with | Unary(x) & Operator(op) -> sprintf "%s(%s)" op (format x) | Binary(x, y) & Operator(op) -> sprintf "(%s %s %s)" (format x) op (format y) | Terminal(x) -> string x ``` I assumed, since F# is magic, that this would just work. Unfortunately, the compiler then warns me about incomplete pattern matches, because it can't see that anything that matches `Unary(x)` will also match `Operator(op)` and anything that matches `Binary(x, y)` will also match `Operator(op)`. And I consider warnings like that to be as bad as compiler errors. So my questions are: Is there a specific reason why this doesn't work (like have I left some magical annotation off somewhere or is there something that I'm just not seeing)? Is there a simple workaround I could use to get the type of safety I want? And is there an inherent problem with this type of compile-time checking, or is it something that F# might add in some future release?

Original source