Symbolic simplification in Haskell (using recursion?)

In the beginning: I know quite a bit about Haskell and my total time spent programming the language is no more than 8 hours in 5 years or so, although I read a lot about the language. So, pardon my no doubt awful style.

I solved this problem as it looked like an easy way to dig into a bit of Haskell programming. First, 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 Minus, but otherwise it's the same.

I quickly discovered that the values ​​plotted using eg "Const 4" were not printed with the above as there was no display function. I made Expr an instance of the Show type class and provided a simple definition of show, considering operator precedence:

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) ++ ")"

      

        
        
        
      

    

The next task was simplification. As Glomek hints at, there is a problem with trying to evaluate everything just by using pattern matching in one function.

In particular, for any given operation (all operations in the example are binary), you must first simplify the left tree, then the right tree, and then simplify the current Expr based on what those subtrees evaluated; for example, if both are simplified to Const, then you can replace the entire subtree with the operation being evaluated. However, pattern matching forces you to choose what to do based on the immediate node children, not what the subtrees return when simplified.

Thus, to get a pattern match for the job of determining whether or not the current node should be evaluated as a constant subexpression, it is important to simplify the subtrees and then send based on the simplified integer.

I did this using a separate function, which I called eval, whose purpose is to match patterns to things that can be scaled down, assuming the subtrees have already been scaled down. It also handles multiplying by 0 and 1 and adding 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 is safe to call at the top level of the expression tree (i.e. it will not be infinitely recursive), I can call it simplified after simplifying 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 simplification has many limitations: it will not extend multiplication to a non-Const subtree, it will not reorder the expression to bring constant expressions together (so the equivalent of 1 + a + 2 will not simplify to + 3), etc. etc. However, he does basic tasks.