Take the 2-minute tour ×

I've defined a nested data type Bush:

data Bush a = BEmpty | BCons a (Bush(Bush a))

Now I`ve tried to define an equal function on Bushes:

eqB :: Eq a => Bush a -> Bush a -> Bool
eqB BEmpty BEmpty = True
eqB BEmpty _ = False
eqB _ BEmpty = False
eqB (BCons x bbush1) (BCons y bbush2) = x == y -- && ....

The problem is the recursive call on Bush(Bush) I could define a function eqB' over Bush(Bush), but than I have to handle eq on Bush(Bush(Bush)), and so on.

Is there a way to solve this problem?

share|improve this question
For example sum –  jeans Dec 4 '12 at 11:33

2 Answers 2

Bush is a "non-regular" or "non-uniform" data type, which means that in the recursive case it doesn't use the same type argument as the one it was given. These can sometimes be tricky to reason about, but in this case the answer is simpler than you might think:


instance Eq a => Eq (Bush a) where
    BEmpty == BEmpty = True
    BCons x xs == BCons y ys = x == y && xs == ys
    _ == _ = False

That's it! (==) can just call itself recursively, and we're done.

But wait, we've pulled a bit of a dirty trick here: We're using Eq and the type class mechanism, which is doing the hard work for us.

How would we do it if we didn't have type classes at all? Well, if we didn't have type classes, we couldn't use the Eq a => constraint in the first place. Instead we might pass an explicit comparison function :: a -> a -> Bool. So with that in mind, we can write very similar code:

eqBush :: (a -> a -> Bool) -> Bush a -> Bush a -> Bool
eqBush _ BEmpty BEmpty = True
eqBush eqA (BCons x xs) (BCons y ys) = eqA x y && eqBush (eqBush eqA) xs ys
eqBush _ _ _ = False

In each recursive call, we're not passing along the same comparison function that we got -- we're passing a comparison function to compare Bush as instead of as! This is really the same thing that happens with the type class, except more explicit. Notice how the structure of our recursive call is the same as the structure of our data type definition -- we have Bush (Bush a) so we recurse with eqBush (eqBush eqA).

The same thing happens with any other recursive definition over this type. Here's a useful one (this is just fmap for Bush, really):

mapBush :: (a -> b) -> Bush a -> Bush b
mapBush _ BEmpty = BEmpty
mapBush f (BCons x xs) = BCons (f x) (mapBush (mapBush f) xs)

With this, writing functions like sumBush is easy:

sumBush :: Bush Int -> Int
sumBush BEmpty = 0
sumBush (BCons x xs) = x + sumBush (mapBush sumBush xs)

This kind of recursion is called polymorphic recursion, because a polymorphic function calls itself at a different type from the type it was called at. Polymorphic recursion can be tricky figure out -- in fact, type inference for it is undecidable (in general), so you'll have to write your own type signatures (in general) -- but with a bit of practice it can seem much more natural. Try writing some other functions on Bush to get a feel for it.

Here are a couple of other non-regular data types to try writing some code for:

  • data Tree a = Leaf a | Branch (Tree (a,a)) -- perfect binary trees.

  • dataFunLista b = Done b | More a (FunList a (a -> b)) -- a list of as together with a function that takes exactly that many as and returns a b (this is related to Traversals).

share|improve this answer
That's the solution. Thanks a lot! –  jeans Dec 4 '12 at 14:26

For example sum of all Int occurences in Bush Int

sum:: Bush Int -> Int
sum BEmpty = 0
sum (BCons i BEmpty) = i
sum (BCons i bbush) = i + sum' bbush 

I could write a function sum' that handles bbush:

sum':: Bush (Bush Int) -> Int
sum' BEmpty = 0
sum' (BCons bush bbbush) = sum bush -- + sum'' bbbush

There is no ending...

share|improve this answer

Your Answer


