[Haskell-beginners] Generalised symbolic expressions

Dmitrij Szamozvancev dima.samoz at gmail.com
Sun Aug 7 12:38:05 UTC 2016

Hello all,

I'm learning about data types and type classes and tried implementing a
simple symbolic expression evaluator, but generalised for non-numeric data

data GenExpr a = Atom a | Sum (GenExpr a) (GenExpr a) | Prod (GenExpr a)
(GenExpr a) | Neg (GenExpr a)

What I am hoping to do is write a general evaluation function which can
some GenExp expression and evaluate it. For example, giving it a GenExp
Integer would evaluate it according to normal arighmetic, GenExp Bool would
be evaluated using Boolean algebra etc. I've declared explicit type classes
for types that can be summed, multiplied and negated:

class HasSum a where (.+.) :: a -> a -> a
class HasProd a where (.*.) :: a -> a -> a
class HasNeg a where (.-) :: a -> a

instance HasSum Integer where (.+.) = (+)
instance HasProd Integer where (.*.) = (*)
instance HasNeg Integer where (.-) = negate

instance HasSum Bool where (.+.) = (||)
instance HasProd Bool where (.*.) = (&&)
instance HasNeg Bool where (.-) = not

-- Evaluate generalised expression
genEval :: (HasSum a, HasProd a, HasNeg a) => GenExpr a -> a
genEval (Atom a) = a
genEval (Sum ge1 ge2) = genEval ge1 .+. genEval ge2
genEval (Prod ge1 ge2) = genEval ge1 .*. genEval ge2
genEval (Neg ge) = (.-) $ genEval ge

However, I would like it to work with types that don't support all three
operations, e.g. natural numbers which don't have a negation operation or
strings that only have concatenation as addition:

instance HasSum Nat where (.+.) = (+)
instance HasProd Nat where (.*.) = (*)

instance HasSum String where (.+.) = (++)

But these wouldn't be suitable inputs for genEval because they don't fulfil
all three type constraints. The only solution I can think of is writing
separate genEvalNat and genEvalString functions, which kind of defeats the
purpose of the generalisation.
Is there a more elegant way to solve this problem?
Thank you in advance!

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160807/71a59512/attachment.html>

More information about the Beginners mailing list