## 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.

Brent Yorgey says:

June 30th, 2008 at 9:26 pm

Perhaps I can offer some clarification. =)

First of all, I think the source of a lot of your grief is the fact that your data declaration probably isn’t exactly what you intended:

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

You probably intended this to mean that a MaybeTree, indexed by the type of the elements it contains, consists of a MaybeNode which possibly contains an element and two MaybeTrees. That would be perfectly correct, but that isn’t what you’ve written! If you have a type that looks like “a b c …”, it means “the type constructor a applied to the types b, c …”, not “one a, one b, and one c” (for example, “Maybe Int” does not mean “a Maybe and an Int”, that’s not even sensical). So in particular “a (MaybeTree a) (MaybeTree a)” means “some type constructor a applied to the types (MaybeTree a) (MaybeTree a)”, not “an element a, one MaybeTree a, and another MaybeTree a”. You then use it as if the Maybe contains a triple (a, MaybeTree a, MaybeTree a) which is where the (,,) stuff is coming from.

What you probably mean to say instead is

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

which is a MaybeNode possibly containing a triple of an element and two MaybeTrees. You should have no problems deriving Show for this data type.

As for FlexibleInstances, the Haskell 98 language standard is rather conservative in terms of what sorts of things you can declare instances of. In particular, you can only have instance declarations like

instance SomeClass (Foo x y z) …

where the x, y, and z are type variables, i.e. things with kind * . Your instance involved (,,) t which is definitely not a type variable. But GHC can deal with many more instance forms than those allowed by the Haskell 98 standard, and you can turn on these extensions by enabling FlexibleInstances.

Hope that is helpful! Let me know if you have any other questions.

codders says:

July 1st, 2008 at 8:11 am

Oooooh. Commas. That makes much more sense. I’d been getting mixed up about their presence / absence for a little while. That and forgetting to enclose my arguments in brackets. Bit of practice and I’ll be set, hopefully.

Thanks for the tip, and the explanation of FlexibleInstances. If I get a chance I’ll update the post to show what happens when the commas are in the right place