Symbolic simplification in Haskell (using recursion?)

Question

How can I give a general rule that includes all the expressions below? E.g one expression, another one for sub and one for mult. I need to use recursion but i got confused...

simplify :: Expr->Expr

simplify (Mult (Const 0)(Var"x"))
 = Const 0 
simplify (Mult (Var "x") (Const 0))
 = Const 0
simplify (Plus (Const 0) (Var "x")) 
= Var "x"
simplify (Plus (Var "x") (Const 0))
 = Var "x" 
simplify (Mult (Const 1) (Var"x")) 
= Var "x"
simplify (Mult(Var"x") (Const 1))
 = Var "x" 
simplify (Minus (Var"x") (Const 0))
 = Var "x"
simplify (Plus (Const x) (Const y)) 
= Const (x + y)
simplify (Minus (Const x) (Const y))
= Const (x - y)
simplify (Mult (Const x) (Const y))
 = Const (x * y)
simplify x = x

Answer 1

The recursion comes in when you need to deal with nested expressions. For instance, how do you simply (Plus (Plus 2 3) (Plus 4 5))?

One approach is to break it into two functions. Move the one level logic (which you show above) into its own function. The main simplify function might have a rule similar to the following for Plus:

simplify (Plus x y) = simplify_one_level (Plus (simplify x) (simplify y))

Answer 2

First up: I know reasonably little about Haskell, and my total time spent programming the language is no more than 8 hours spread over 5 years or so, though I have read plenty about the language. Thus, forgive my no doubt horrible style.

I tackled this problem since it looked like an easy way to get into a little bit of Haskell programming. First up, I made a data type inspired by the sample:

data Expr = Const Int | Mult Expr Expr | Plus Expr Expr | Var String

I made it a little simpler than the original, and left out Minus, but otherwise it's the same.

I quickly found out that values constructed using e.g. "Const 4" were not printable with the above, as there was no show function applicable. I made Expr an instance of the Show type class, and provided a simple definition of show, taking operator precedence into account:

instance Show Expr where
    show (Const n) = show n
    show (Var n) = show n
    show (Plus a b) = (show a) ++ "+" ++ (show b)
    show (Mult a b) = "(" ++ (show a) ++ ") * (" ++ (show b) ++ ")"

Next up was the simplification task itself. As Glomek hints, there's an issue with trying to evaluate everything just using pattern matching in one function.

Specifically, for any given operation (all operations in the example are binary) you'd like to first simplify the left tree, then the right tree, and then simplify the current Expr based on what those subtrees evaluated to; e.g. if both simplified to Const, then you can replace the entire subtree with the evaluated operation. However, pattern matching forces you to choose what to do based on the immediate node's children, rather than what the subtrees return after being simplified themselves.

Thus, to get pattern-matching to do the job of deciding whether to evaluate the current node or not as a constant subexpression, it's important to simplify the subtrees, then dispatch based on the simplified whole.

I did this using a separate function I called eval, whose purpose is to pattern-match on things that can be reduced, assuming that subtrees have already been reduced. It also handles multiplication by 0 and 1, and addition of 0:

-- Tries to evaluate any constant expressions.
eval :: Expr -> Expr
eval (Mult (Const a) (Const b)) = Const (a * b)
eval (Mult (Const a) b)
    | a == 0 = Const 0
    | a == 1 = b
    | otherwise = (Mult (Const a) b)
eval (Mult a (Const b))
    | b == 0 = Const 0
    | b == 1 = a
    | otherwise = (Mult a (Const b))
eval (Plus (Const a) (Const b)) = Const (a + b)
eval (Plus (Const a) b)
    | a == 0 = b
    | otherwise = (Plus (Const a) b)
eval (Plus a (Const b))
    | b == 0 = a
    | otherwise = (Plus a (Const b))
eval e = e

Now that I have eval, and I know it's safe to call at the top level of an expression tree (i.e. it won't infinitely recurse), I can call it from simplify after I've simplified the subtrees:

-- Tries to match evaluation rules after simplifying subtrees.
simplify :: Expr -> Expr
simplify (Plus a b) = eval (Plus (simplify a) (simplify b))
simplify (Mult a b) = eval (Mult (simplify a) (simplify b))
simplify e = e

This version of simplify has many limitations: it won't distribute a multiplication over a non-Const subtree, it won't reorder the expression to bring constant expressions together (so the equivalent of 1+a+2 won't get simplified to a+3), etc. However, it gets the basic jobs done.