I made a tree structure (Tree) that represents an algebraic expression that contains two binary opperators the "question mark" Q/"?" and the "exclamation mark" E/"!".

Both are associative (that means a!(b!c)=(a!b)!c, and the same for the questionmark; this means the order of evaluation doesn't matter and we can omit the parenthesis if we have a chain of the same operator), we do however have no precedence rules, that means we have to use parenthesis if we have a mix of operators: a?b!c would be invalid, it must be (a?b)!c or a?(b!c).

So now I wanted to make it a Show instance that prints out this expression in one line according to the rules outlined above. For that I wrote some helper functions surroundX that add parenthesis where needed.

So my question is: Is there a way to reduce the duplicated code, especially in the surroundX functions?

I thought that it would be nice to be able to pass E or Q as an additional parameter, but I didn't find a way to make that work. But maybe there are other ways to simplify this.

data Tree = Unit | E Tree Tree | Q Tree Tree

surroundE a@(E _ _) = "(" ++ show a ++ ")"
surroundE x = show x
surroundQ a@(Q _ _) = "(" ++ show a ++ ")"
surroundQ x = show x

instance Show Tree where
 show Unit = "1"
 show (E a b) = surroundQ a ++ "!" ++ surroundQ b
 show (Q a b) = surroundE a ++ "?" ++ surroundE b

--example output
main = do
 print $ E (E Unit Unit) (E Unit (Q Unit Unit))
 print $ Q (E Unit Unit) (Q Unit (Q Unit Unit))

Try it online!

  • 3
    \$\begingroup\$ Your code is very concise so there's little room for improvement. That being said I would consider changing the constructors so something like data Tree = Unit | Subtree Kind Tree Tree. Kind could be the argument for surround and produce connecting symbol in show. \$\endgroup\$ – bdecaf Jan 4 at 9:07
  • \$\begingroup\$ @bdecaf Thanks for your comment! This change change in the definition of the Tree makes it a lot easier to handle, also for other applications one might have. I think your suggestion covers exactly what I was asking for. So please consider adding it as an anwer! \$\endgroup\$ – flawr Jan 4 at 9:36
  • \$\begingroup\$ you are most welcome. I don't bother about the points, and as your question is already solved I don't want to put in more research. I'd suggest you post your simplified code and self answer. \$\endgroup\$ – bdecaf Jan 6 at 8:06

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

Type parameters

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 Functor, Applicative, Monad and Traversable instances.

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 op:

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

Associativity Hint

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 philosophy

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.

Associativity Solution

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

But toAssocTree cannot collect your associative operators. That needs equality on op:

collectAssoc :: (Eq op) => AssocTree op a -> AssocTree op a

This way, you divide your computation into little steps.

Why turn Operator into a type parameter op

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.

  • \$\begingroup\$ Thanks a lot for your insights! I now do think converting the binary tree to an associative one does make a lot of sense, especially in light of the paragraph you wrote about the data-centricity of Haskell. \$\endgroup\$ – flawr Jan 12 at 9:06

Placing the recursion in show and adding the operator character as an extra parameter simplifies the helper function.

data Tree = Unit | E Tree Tree | Q Tree Tree

instance Show Tree where
  show Unit = "1"
  show (E a@(Q _ _) b) = showExp "!" (surround (show a)) (show b)
  show (E a b@(Q _ _)) = showExp "!" (show a) (surround (show b))
  show (E a b) = showExp "!" (show a) (show b)
  show (Q a@(E _ _) b) = showExp "?" (surround (show a)) (show b)
  show (Q a b@(E _ _)) = showExp "?" (show a) (surround (show b))
  show (Q a b) = showExp "?" (show a) (show b)

showExp op a b = a ++ op ++ b

surround t = "(" ++ t ++ ")"

Try it online!

Edit: Taking into account associativity by pattern matching in show.

  • 1
    \$\begingroup\$ Thanks for the suggestion. Please do note though that your snippet does not the actually preseve the behaviour of the original one: Yours parenthesizes ALL operators, so for the first example we get ((1!1)!(1!(1?1))) instead of 1!1!1!(1?1). \$\endgroup\$ – flawr Jan 11 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.