Incomplete match with AND patterns

Question

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?

Answer 1

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.

Answer 2

I think you can make operator a normal function rather than an active pattern. Because operator is just a function which gives you an operator string for an expr, where as unary, binary and terminal are expression types and hence it make sense to pattern match on them.

let operator expr =
    match expr with
    | Add(_) -> "+"
    | Sub(_) | Neg(_) -> "-"
    | Mult(_) -> "*"
    | Div(_) -> "/"
    | Pow(_) -> "**"
    | Var(_) | Con(_) -> ""


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

Answer 3

I find the best solution is to restructure your original type defintion:

type UnOp = Neg
type BinOp = Add | Sub | Mul | Div | Pow
type Expr =
  | Int of int
  | UnOp of UnOp * Expr
  | BinOp of BinOp * Expr * Expr

All sorts of functions can then be written over the UnOp and BinOp types including selecting operators. You may even want to split BinOp into arithmetic and comparison operators in the future.

For example, I used this approach in the (non-free) article "Language-oriented programming: The Term-level Interpreter " (2008) in the F# Journal.