CODEWITHSUNDEEP
haskelltypestreeinstanceshow
norman
norman

Reputation: 5556

Making a data type an instance of Show in Haskell

I need to make the following data type an instance of Show:

data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a

I'm fairly new at this, but to start with, I interpreted this declaration as

"We have made a new type called Tree, which is parameterized with types a and b. A tree can be one of two things: a Branch which holds a piece of data of type b, plus two more Trees, or a Leaf which holds a data item of type a."

Now, I need to make a way to "Show" it nicely (nested branches, etc.), without using deriving. So far, I have only been writing functions in a module Main and loading/playing with them in an interpreter window, so I haven't actually done things with constructors, etc, before. Nevertheless, I figured I could just start off by declaring the tree data type within my file, as shown at the beginning of the question, and go from there.

As I messed around with "Show" without much success, I thought maybe I needed to define a small component of the tree and how to "Show" it first, before trying to work with the whole tree: 

data Leaf a = Leaf a

instance Show (Leaf a) where
show (Leaf a) = ???

I tried a number of things in the ??? spot, such as "a", just a by itself, putStrLn, etc., but none are printing out the value of a when I say something like

>show (Leaf 3)

In fact, I have in many cases encountered this, which probably means I am not locating things right:

Ambiguous occurrence `show'
    It could refer to either `Main.show', defined at a2.hs:125:1
                          or `Prelude.show',
                             imported from `Prelude' at a2.hs:2:8-11
                             (and originally defined in `GHC.Show')

...which I addressed by calling "Main.show," which of course doesn't work.

I guess the question is, where do I go with all this...or maybe just, "How can I fix the Leaf "Show" utility so that I can figure out how to extend it?" (assuming I have to define it first...)

Upvotes: 15

Views: 25200

Answers (4)

MathematicalOrchid
MathematicalOrchid

Reputation: 62808

Here's a minor hint: By writing

 instance Show (Leaf a) where
 show (Leaf a) = ???

what you actually did was define an empty Show instance, followed by a top-level show function. This is why you get the "ambiguous show" error; you've defined a new show function, whose name clashes with the existing one.

What you meant to say was

 instance Show (Leaf a) where
   show (Leaf a) = ???

Note how the second line is indented now. This means you're redefining the existing show method, as you presumably intended.

Upvotes: 9

Matt S
Matt S

Reputation: 376

Your data-type is a perfect candidate for deriving Show.

data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a deriving Show

That will automatically generate the Show instance for you.

If you want to create a manual instance of Show, here's the thought process.

First, the basic skeleton:

instance Show (Tree a b) where
   -- show :: Tree a b -> String
   show (Branch b ltree rtree) = {- some string -}
   show (Leaf a) = {- some string -}

Now we know that we'll need some way to show values of type a and b as strings. Of course, that means we need to be able to call show on them directly, so a and b must have instances of Show. Here's how that's done:

instance (Show a, Show b) => Show (Tree a b) where
   -- show :: Tree a b -> String
   show (Branch b ltree rtree) = {- some string -}
   show (Leaf a) = {- some string -}

Then it's just filling in the blanks with appropriate strings, such as:

instance (Show a, Show b) => Show (Tree a b) where
   -- show :: Tree a b -> String
   show (Branch b ltree rtree) = "(( " ++ show ltree ++ " ) <-- ( " ++ b ++ " ) --> ( " ++ show rtree ++ " ))"
   show (Leaf a) = "L " ++ show a

Upvotes: 3

mergeconflict
mergeconflict

Reputation: 8266

The easiest answer would be to automatically derive a Show instance:

data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a deriving Show

But let's say that doesn't give you output of the form you want. If you want to define your own Show instance, you'd do something like:

instance (Show a, Show b) => Show (Tree a b) where
    show (Leaf a) = "Leaf " ++ (show a)
    show (Branch b l r) = "Branch " ++ (show b) ++ " { " ++ l ++ ", " ++ r " }"

The way you might read that first line is, "given a and b are both instances of the Show typeclass, Tree a b is also an instance of the Show typeclass..."

By the way, indentation is important. It may have gotten mangled in the snippet you pasted, but you must indent the show function definitions under the instance declaration.

Upvotes: 9

Daniel
Daniel

Reputation: 27549

You have to start like that:

data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a

instance (Show a, Show b) => Show (Tree a b) where
    show (Leaf x) = show x
    show (Branch p l r) = ???

In order to show a Tree a b you have to first be able to show as and bs. That's what the (Show a, Show b) => part does, it specifies the preconditions you require for your instance to work.

Upvotes: 25

Related Questions