Food for thought:
From my (now deleted) comment:
Your operators are associative, but your data structure is not. Is there a different data representation which is associative?
I think you want to do more with this tree than just printing it, right?
The problem is you want
Q Unit (Q Unit Unit) to be equal to
Q (Q Unit Unit) Unit. Find a 'canonical' representation!
Think about an answer or scroll down to find mine. The next steps just set it up.
Pulling out the operator?
You've already seen this in the comment:
data Operator = ExclamationMark | QuestionMark
data Tree = Unit | BinaryNode Operator Tree Tree
Your example seems to be a minimal working example, but you certainly want your
Unit to contain some identifier, e.g.
data BinTree a = Leaf a | BinaryNode Operator BinTree BinTree. Do the same with
Operator and you've got:
data BinTree op a = Leaf a | BinaryNode op (BinTree op a) (BinTree op a)
Based on your haskell experience, you might want to write your
The type parameter
op can be instantiated with
Operator, but maybe also
String in the context of (pretty-)printing. Or go further and have a function in place of
evalBinTree :: BinTree (a -> a -> a) a -> a
evalBinTree (Leaf x) = x
evalBinTree (BinaryNode f left right) = f (eval left) (eval right)
of course get yourself a function to make these tasks easier:
mapOp :: (op -> op') -> BinTree op a -> BinTree op' a
data Binary a = Binary a a is isomorphic to a pair
(a,a), which always contains two
as. What data structure allows you to have an arbitrary number of
as? Next section is some sort of filler to hide the solution.
Haskell is a functional language. While "functional" puts the emphasis on functions, it is actually data-centric. Defining new data structures and converting between them is easier and more concise than in, say, Java. What I am trying to say here: You can keep the
BinTree and the
AssocTree of the following section and write functions that transforms one representation to the other.
First a non-parametric data type that allows an arbitrary number of children:
data AssocTree = Unit | Node [AssocTree]
but I will continue with:
data AssocTree op a = ALeaf a | ANode op [AssocTree op a]
And left as an exercise, you want a function:
toAssocTree :: BinTree op a -> AssocTree op a
toAssocTree cannot collect your associative operators. That needs equality on
collectAssoc :: (Eq op) => AssocTree op a -> AssocTree op a
This way, you divide your computation into little steps.
Operator into a type parameter
Here is the reason why I supposed to make the operation a type parameter: With an abstract type, the type system prevents this error:
data BTree = Unit | E Tree Tree | Q Tree Tree
data ATree = AUnit | AE [Tree] | AQ [Tree]
toATree (E left right) = AE [left,right]
toATree (Q left right) = AE [left,right] -- c&p error: should be AQ, not AE
Yes, abstracting out the type prevents errors.