Ocaml: Match expression inside another one?

Question

Hello, I'm currently working on a small project with Ocaml; a simple mathematical expression simplifier. I'm supposed to find certain patterns inside an expression, and simplify them so the number of parenthesis inside the expression decreases. So far I've been able to implement most rules except two, for which I've decided to create a recursive, pattern-matching "filter" function. The two rules I need to implement are:

-Turn all expressions of the form a - (b + c) or similar into a - b - c

-Turn all expressions of the form a / (b * c) or similar into a / b / c

...which I suspect would be fairly simple, and once I've managed to implement one, I can implement the other easily. However, I'm having trouble with the recursive pattern-matching function. My type expression is this:

type expr =
 | Var of string      (* variable *)
 | Sum of expr * expr    (* sum  *)
 | Diff of expr * expr   (* difference *)
 | Prod of expr * expr   (* product *)
 | Quot of expr * expr   (* quotient *)
;;

And what I'm mainly having trouble on, is in the match expression. For example, I'm trying something like this:

let rec filter exp =   
    match exp with       
    | Var v -> Var v                       
    | Sum(e1, e2) -> Sum(e1, e2)     
    | Prod(e1, e2) -> Prod(e1, e2)
    | Diff(e1, e2) ->
     match e2 with
     | Sum(e3, e4) -> filter (diffRule e2)
     | Diff(e3, e4) -> filter (diffRule e2)      
     | _ -> filter e2         
    | Quot(e1, e2) ->                                 ***this line***
     match e2 with  
     | Quot(e3, e4) -> filter (quotRule e2)        
     | Prod(e3, e4) -> filter (quotRule e2)        
     | _ -> filter e2
;;

However, it seems that the match expression on the marked line is being recognized as being part of the previous "inner match" instead of the "principal match", so all "Quot(...)" expressions are never recognized. Is it even possible to have match expressions inside other match expressions like this? And what would be the correct way to end the inner match so I can continue matching the other possibilities?

Ignore the logic, since it's pretty much what I came up with first, it's just that I haven't been able to try it since I have to deal with this "match" error first, although any recommendation on how to handle the recursiveness or the logic would be welcome.

Answer 1

You just need to add parentheses (or begin/end) around the inner match:

let rec filter exp =
    match exp with
    | Var v -> Var v
    | Sum(e1, e2) -> Sum(e1, e2)
    | Prod(e1, e2) -> Prod(e1, e2)
    | Diff(e1, e2) ->
            (match e2 with
             | Sum(e3, e4) -> filter (diffRule e2)
             | Diff(e3, e4) -> filter (diffRule e2)
             | _ -> filter e2)
    | Quot(e1, e2) ->
            (match e2 with
             | Quot(e3, e4) -> filter (quotRule e2)
             | Prod(e3, e4) -> filter (quotRule e2)
             | _ -> filter e2)
;;

BTW, in your particular case there is no need for a nested match. You can just use bigger patterns. You can also eliminate the duplication in the nested rules using "or" patterns:

let rec filter exp =
    match exp with
    | Var v        -> Var v
    | Sum(e1, e2)  -> Sum(e1, e2)
    | Prod(e1, e2) -> Prod(e1, e2)
    | Diff(e1, Sum(e3, e4) as e2)
    | Diff(e1, Diff(e3, e4) as e2) -> filter (diffRule e2)
    | Diff(e1, e2)                 -> filter e2
    | Quot(e1, Quot(e3, e4) as e2)
    | Quot(e1, Prod(e3, e4) as e2) -> filter (quotRule e2)
    | Quot(e1, e2)                 -> filter e2
;;

OCaml's pattern syntax is nice, isn't it?

Answer 2

You can make this terser (and I would argue clearer) by judicious use of underscores, as's and or-patterns. The resulting code is also more efficient, because it allocates less (in the Var, Sum and Prod cases)

let rec filter = function
| Var _ | Sum _ | Prod _ as e -> e
| Diff (_, (Sum _ | Diff _) as e) -> filter (diffRule e)
| Diff (_,e) -> e
| Quot (_, (Quot _| Prod _) as e) -> filter (quoteRule e)
| Quot (_,e) -> filter e
;;