talkingCode

More Haskell fun

“Define a tree type that has only one constructor, like our Java example. Instead of the Empty constructor, use the Maybe type to refer to a node’s children.”

Fair enough. How bout this?

data MaybeTree a = MaybeNode (Maybe (a (MaybeTree a) (MaybeTree a)))

It’s a real type. I can even make real values in the type:

maybeTree = MaybeNode (Just ("fish",
             (MaybeNode (Just ("left", 
                               (MaybeNode Nothing),
                               (MaybeNode Nothing)))),
             (MaybeNode (Just ("right",
                               (MaybeNode Nothing),
                               (MaybeNode Nothing))))))

Buuut I can’t print them. Because I don’t derive Show. If I try to derive Show:

    No instance for (Show (a (MaybeTree a) (MaybeTree a)))
      arising from the 'deriving' clause of a data type declaration
                   at working.hs:(51,0)-(52,30)
    Possible fix:
      add an instance declaration for
      (Show (a (MaybeTree a) (MaybeTree a)))
    When deriving the instance for (Show (MaybeTree a))

That’s fair enough. And GHC’s even provided me with a hint. So I just… err… instance Show something, right? Wrong

Let’s write the show function for my tree type:

showTree (MaybeNode Nothing) = "empty"
showTree (MaybeNode (Just (a, b, c))) = "Node: " ++ (show a) ++ 
              ", Left: " ++ (showTree b) ++ 
              ", Right: " ++ (showTree c)

s’all good. But the type of that function?

showTree :: (Show t) => MaybeTree ((,,) t) -> [Char]

See that ((,,) t)? That’s the badness.

*Main> :kind (,,)
(,,) :: * -> * -> * -> *

Yeah. So it’s a tuple that has three type variables. Fun. Now I’m pretty sure that I ought to be able to define an instance of Show for my type, but I can’t for the life of me work out what the syntax is going to be

instance (Show a) => Show (MaybeTree ((,,) a)) where
       show t = showTree t

working.hs:58:0:
    Illegal instance declaration for `Show (MaybeTree ((,,) a))'
        (All instance types must be of the form (T a1 ... an)
         where a1 ... an are distinct type *variables*
         Use -XFlexibleInstances if you want to disable this.)
    In the instance declaration for `Show (MaybeTree ((,,) a))'

??? How about

instance (Show a) => Show (a, MaybeTree a, MaybeTree a) where
        show t = showTree t

working.hs:61:40:
    Kind mis-match
    Expected kind `* -> * -> *', but `a' has kind `*'
    In the type `MaybeTree a'
    In the type `(a, MaybeTree a, MaybeTree a)'
    In the type `(Show a) => Show (a, MaybeTree a, MaybeTree a)'

Any answers much appreciated, glorious lazyweb. I’m adding this to the list of exercises in the book that you can’t answer at the point you’ve reached in the book (this is chapter 4). Even after reading around about types and kinds and other peoples’ use of instance, I’m clueless.

And changing my type to be something sane doesn’t count. If it’s not possible to Show my type, I’d like to know why

Update:
After much discussion with sffubs and sos, it seems the only reasonable thing to do is to

{-# LANGUAGE FlexibleInstances #-}
instance (Show t) => Show (MaybeTree ((,,) t)) where
  show = showTree

We’re not quite sure what Flexible Instances are, but it seems that’s what’s needed to make this datatype work. The real answer is obviously not to use a crazy datatype:

data FooTree a = Maybe a ((FooTree a), (FooTree a)) deriving (Show)

Thanks both.