Haskell Deriving Show Instance

Question

I am playing with a Red-Black tree:

-- Taken from Okasaki 1999
module RedBlackTree where

--node coloring data
--a node is R (red) or B (black)
data Color = R | B

--tree constructor
--a RBT can be E (empty) or be T (a non empty tree)
data RBT e = E | T Color (RBT e) e (RBT e)

--set operations on tree
type Set a = RBT a

--define an empty set
empty :: Set e
empty = E

--define a member of a set
--Sees if an item of type e is
--in a set if type e elements
member :: (Ord e) => e -> Set e -> Bool
member x E = False
member x (T _ a y b) | x <  y = member x a -- if less, go left
                     | x == y = True
                     | x >  y = member x b -- if more, go right


--tree operations
--Insert an element
insert :: (Ord e) => e -> Set e -> Set e
insert x s = makeBlack (ins s)
    where ins E = T R E x E --basically the typical BST insert
          ins (T color a y b) | x <  y = balance color (ins a) y b
                              | x == y = T color a y b
                              | x >  y = balance color a y (ins b)
          makeBlack (T _ a y b) = T B a y b --inserts a black node

-- balance operations
--case 1:
balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
--case 2:
balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
--case 3:
balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
--case 4:
balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
--generic balancing operation
balance color a x b = T color a x b

If I execute the following statement in GHCi:

> RedBlackTree.insert ('b') (RedBlackTree.T R E ('a') E)

The following error message tells me there is not an instance of show for Set Char:

<interactive>:116:1:
No instance for (Show (Set Char)) arising from a use of `print'
Possible fix: add an instance declaration for (Show (Set Char))
In a stmt of an interactive GHCi command: print it

I know the tree is working because by calling member 'b' ... where ... is the previously executed statement, the returned value is True. I've been reading the other SO posts on this problem but the solutions found for them (e.g.:Haskell: Deriving Show for custom type) does not work.

For example, by adding:

instance Show Set where:
    show (Set Char) = show Char

I get the following error message when I try to load using :l:

:l red-black-tree.hs [1 of 1] Compiling RedBlackTree ( red-black-tree.hs, interpreted )

red-black-tree.hs:54:11: Not in scope: data constructor `Set'

red-black-tree.hs:54:15: Not in scope: data constructor `Char'

red-black-tree.hs:54:28: Not in scope: data constructor `Char'
Failed, modules loaded: none.

I think there are a few problems going on with what I'm trying to do but I can't seem to figure it out from the available documentation.

Answer 1

To transform a value into a string, Haskell uses a so-called type class. Simplified, type classes just provide functions that behave differently depending on the type of their argument. This approach is very similar to method overloading known from object-oriented programming languages. The type class Show provides a function called show that transforms a value of some type into a string. For example, the expression show 1 yields the string "1". If there is a function show that transforms a value of some type into a string we say that there is an instance of the type class Show for this type. In other words, there is an instance of the type class Show for integers.

This show function is also used when you evaluate an expression in ghci. Therefore, it tells you that there is no instance (Show (Set Char)), in other words, it does not know, how to transform a value of type Set Char into a string. For custom types like your types Set, RBT, and Color you have to provide instances of the type class Show in order to display values of theses types on the console. To define an instance of the type class Show for the type Color you can use the following definition.

instance Show Color where:
  show R = "Red"
  show B = "Black"

That is, if you write R into ghci, it will print Red. For simple Haskell data types, there is a canonical definition of the Show type class. For example, the canonical definition of Show for Color is as follows.

instance Show Color where:
  show R = "R"
  show B = "B"

To relieve the user from defining instances like this, Haskell provides a so-called "deriving mechanism". That is, if you write

  deriving (Show)

after the definition of a data type, the compiler will generate a canonical instance of the Show type class for your data type.

If a data type makes use of another data type, deriving a Show instance of the former will require a Show instance of the latter. For example, consider the following data type.

data RBT e = E | T Color (RBT e) e (RBT e)

The data type RBT uses the type Color in its definition. The canonical Show instance of the T constructor will start with "T " and afterwards show the value of type Color. Therefore, deriving the Show instance for RBT requires an instance of Show for Color.

Answer 2

Your instance code is broken:

instance Show Set where
    show (Set Char) = show Char

1. The compiler complains that Set is not a data constructor, and it isn't - it's a type synonym name. So you incorrectly used Set in a pattern. You can use data constructors there - and for RBT data constructors are T and E.

2. Your instance declaration is ill-kinded: Set is a synonym for RBT and RBT has one type argument, that is it's a function from type to type, with a kind signature of * -> *. But Show instance requires a type without an argument, that is a type and not a type constructor, kind * instead of * -> * you supplied. So you should fix that by supplying either instance Show (RBT Char) or instance (Show a) => RBT a.

What you probably wanted is to write "show a set of char by showing chars inside of it".

So to fix your instance:

instance Show (RBT Char) where
    show a = "something"

But it doesn't show anything useful. You need to do pattern matching on constructors of RBT to get the work done:

instance Show (RBT Char) where
    show E = "something"
    show (T a b c d) = "something else"

But for your task it will be simpler just to use the derived Show instances for RBT a and Color.