CODEWITHSUNDEEP
mathhaskellalgebra
user41000
user41000

Reputation: 285

How can I simplify a basic arithmetic expression?

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

Upvotes: 6

Views: 3882

Answers (4)

Michael Steele
Michael Steele

Reputation: 15772

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

Upvotes: 1

bugmagnet
bugmagnet

Reputation: 7769

Are we talking rationals here, like GMP's rationals? If so, then one could simplify a division by making the second argument into its reciprocal and then multiplying.

Apart from that, multiplication is addition done more than once, and division is subtraction done more than once.

As Mitch has said in the comments, we could do with some more information about what you're trying to simplify.

Upvotes: 0

Edward Kmett
Edward Kmett

Reputation: 29982

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

Upvotes: 11

Ferruccio
Ferruccio

Reputation: 100708

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.

Upvotes: 1

Related Questions