Implementing custom operators

Question

I have a school project where I need to simplify user generated mathematical expressions. We also need to define our own basic operators (:+: is addition, :*: is multiplication etc.).

For example:

Prelude> Const 9 :+: Const 3 :+: Const 2
Const 14
Prelude> Const 14 :*: Var 'x' :+: Const 10 :*: Var 'x'    
Const 24 :*: Var 'x'

Here is what I have so far:

infixl 4 :+:
infixl 5 :*:, :/:
infixr 6 :^:

data Expr a = Var Char
         | Const a 
         | (Expr a) :+: (Expr a) 
         | (Expr a) :*: (Expr a)
         | (Expr a) :^: (Expr a)
         | (Expr a) :/: (Expr a)
         deriving (Show, Eq)

I have tried something like this for my addition operator without success:

class (Num a) => Expr a where
    (:+:) :: a -> a -> a

instance Expr a where
    x :+: y = x + y

All that I'm looking for is some guidance on how to get this started. I'm comfortable with creating my own functions, and using common functions (map, zip, foldr etc.). We recently started learning type classes, functors, and a brief intro on monads.

Answer 1

I was able to implement this project, I appreciate the help for getting me started in the right direction. I'll post my solution here in case anyone is interested. It may not be pretty but it works!

completeCleanUp with the help of cleanUp simplify an Expr. plugIn takes some Char 'x', and replaces all Var 'x' with a number provided. Finally evalExpr returns a solution to the Expr.

Note that variable simplification did not need to be implemented, thus Const 9 :*: Var 'x' :+: Const 10 :*: Var 'x' would not be further reduced.

cleanUp :: (Eq a, Floating a) => Expr a -> Expr a

cleanUp (Const a) = Const a
cleanUp (Var a) = Var a
cleanUp (Const a :*: (Const b :*: c)) = Const (a * b) :*: cleanUp c
cleanUp (Const a :*: c :*: Const b) = Const (a*b) :*: cleanUp c
cleanUp (c :*: Const a :*: Const b) = Const (a*b) :*: cleanUp c
cleanUp (Const a :*: (b :+: c)) = (Const a :*: cleanUp b) :+: (Const a :*: cleanUp c)
cleanUp (Const 0 :/: a) = Const 0
cleanUp (a :/: Const 0) = error "Error: Division by 0 not allowed."
cleanUp (a :/: b) | a == b = Const 1.0
cleanUp (a :^: Const 1) = cleanUp a
cleanUp (Const 1 :^: a) = cleanUp a
cleanUp (a :^: Const 0) = Const 1.0
cleanUp (Const 0 :^: a) = Const 1.0
cleanUp ((c :^: Const b) :^: Const a) =  cleanUp c :^: Const (a*b)
cleanUp (Const a :^: Const b) = Const (a ** b)
cleanUp (Const a :/: Const b) = Const (a / b)
cleanUp (a :*: Const 1) = cleanUp a
cleanUp (Const 1 :*: a) = cleanUp a
cleanUp (a :*: Const 0) = Const 0
cleanUp (Const 0 :*: a) = Const 0
cleanUp (Const a :*: Const b) = Const (a * b)
cleanUp (a :+: Const 0) = cleanUp a
cleanUp (Const 0 :+: a) = cleanUp a
cleanUp (Const a :+: Const b) = Const (a + b)
cleanUp (Var a :^: b) = Var a :^: cleanUp b
cleanUp (a :^: Var b) = cleanUp a :^: Var b
cleanUp (Var a :+: b) = Var a :+: cleanUp b
cleanUp (a :+: Var b) = cleanUp a :+: Var b
cleanUp (Var a :*: b) = Var a :*: cleanUp b
cleanUp (a :*: Var b) = cleanUp a :*: Var b
cleanUp (Var a :/: b) = Var a :/: cleanUp b
cleanUp (a :/: Var b) = cleanUp a :/: Var b
cleanUp (a :^: b) = cleanUp a :^: cleanUp b
cleanUp (a :/: b) = cleanUp a :/: cleanUp b
cleanUp (a :*: b) = cleanUp a :*: cleanUp b
cleanUp (a :+: b) = cleanUp a :+: cleanUp b

completeCleanUp :: (Eq a, Floating a) => Expr a -> Expr a

completeCleanUp exp 
    | exp == cleanUp exp = exp
    | otherwise = completeCleanUp (cleanUp exp)


plugIn :: Char -> a -> Expr a -> Expr a

plugIn char num (Var c) | char == c = Const num
plugIn char num (a :^: b) = plugIn char num a :^: plugIn char num b
plugIn char num (a :/: b) = plugIn char num a :/: plugIn char num b
plugIn char num (a :*: b) = plugIn char num a :*: plugIn char num b
plugIn char num (a :+: b) = plugIn char num a :+: plugIn char num b
plugIn char num a = a


evalExpr :: (Eq a, Floating a) => Char -> a -> Expr a -> a

evalExpr char num exp = case (completeCleanUp . plugIn char num $ exp) of
    (Const x) -> x
    _ -> error "Cannot further simplify solution."

Answer 2

You are confusing two very different topics (if you pasted the error messages this might have surfaced sooner and gotten you better feedback). Lets look at what was provided to you - the Expr data type and the classes.

A Classy Confusion

You were provided with:

data Expr a = Var Char
         | Const a 
         | (Expr a) :+: (Expr a) 
         | (Expr a) :*: (Expr a)
         | (Expr a) :^: (Expr a)
         | (Expr a) :/: (Expr a)
         deriving (Show, Eq)

Here we can see the constructors are basic arithmetic operations. Stated another way, :+: is a constructor of type Expr a -> Expr a -> Expr a and similarly for the others.

Now you go on to try and define a function, namely :+::

class (Num a) => Expr a where
    (:+:) :: a -> a -> a

instance Expr a where
    x :+: y = x + y

There are a few problems here.

• You class Expr is merely named the same as the above type, it has no relation to the data defined above.
• Your method :+: is not a legal function name. Functions, unlike data constructors, must be valid variables and thus can not start with upper case or colon characters.
• The instance is for all types - a is a variable and can match any type. So you have yet to say the x and y values are of type Expr a.

I think you were trying to make a class for each operator and make an instance for each constructor (:+:, :*:, etc). This is a broken, or at least overly verbose, solution. The only reason to use classes are if there are multiple type that require instances - you only have the oneExpr` type.

Classless

There is no need for type classes to solve this problem, instead you can evaluate an expression with a traditional function, much like in the deleted answer.

The previously deleted answer appears to be deleted with the notion that and an environment of bindings for each variable is necessary. My reading of the problem is different and I would simply evaluate the expression into a simple string.

evaluate :: Show a => Expr a -> String
evaluate (Var c) =  [c]
evaluate (a :+: b) = undefined
evaluate (a :*: b) ... so on and so forth ...

In the above you pattern match your Expr a to determine the operation then, on a case by case basis, evalute the sub-expressions as necessary before combining them in a manner dependent on the constructor (+ with :+: etc).