Primitive recursion

Question

how will i define the function 'simplify' using primitive recursion?

simplify :: Expr -> Expr
...

simplify Simplify an expression using basic arithmetic, e.g. simplify (Plus (Var "x") (Const 0)) = Var "x"

Answer 1

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.

Answer 2

Just to give you an example, here's a function that would simplify the expression you gave. The idea is that each definition of simplify is tried from top to bottom until one of the patterns on the left hand side of the equal sign matches. The purpose of the last definition is to break out of recursion if there is no known way to simplify any further.

simplify :: Expr -> Expr
simplify (Plus l         (Const 0)) = simplify l
simplify (Plus (Const 0) r        ) = simplify r
simplify x                          = x