How can I simplify a basic arithmetic expression?

Question

How can I simplify a basic arithmetic expression?

e.g.

module ExprOps where 

simplify :: Expr -> Expr
simplify (Plus(Var"x") (Const 0)) = Var "x"

What do I have to do?

---

module Expr where

-- Variables are named by strings, assumed to be identifiers.
type Variable = String

-- Representation of expressions.
data Expr = Const Integer
          | Var Variable
          | Plus Expr Expr
          | Minus Expr Expr
          | Mult Expr Expr
          deriving (Eq, Show)

The simplifications I have in mind are:

0*e = e*0 = 0
1*e = e*1 = 0+e = e+0 = e-0 = e

and simplifying constant subexpressions, e.g. Plus (Const 1) (Const 2) would become Const 3. I would not expect variables (or variables and constants) to be concatenated: Var "st" is a distinct variable from Var "s".

What I want to achieve is to create a module like the one above that uses a function called simplify :: Expr->Expr

Answer 1

Well, you have the right general model. You just need more rules and to recursively apply the simplification process.

simplify :: Expr -> Expr 
simplify (Mult (Const 0) x) = Const 0 
simplify (Mult x (Const 0)) = Const 0
simplify (Plus (Const 0) x) = simplify x
simplify (Plus x (Const 0)) = simplify x 
simplify (Mult (Const 1) x) = simplify x 
simplify (Mult x (Const 1)) = simplify x 
simplify (Minus x (Const 0)) = simpify 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 2

I did something like this as a project for an AI class decades ago. The class used LISP, so the first thing I did was to convert the expression from infix notation to an S-Expression.

Then it was a matter of traversing the "tree" recursively and applying a set of rules at each node. e.g. if this node contains an operation whose operands are both constants, perform the operation now and replace the node with the result.

Once the basic functionality was in place, it was a matter of adding new new simplification rules to the system.

Finally, the S-Expression was converted back to infix notation for display.