Parametrize by type constructor?

Question

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!

Answer 1

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.

Answer 2

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.