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.
You don't have any fancy extensions in use, so you should be able to use the built-in
deriving
mechanism forShow
.In order for it to automatically derive a
Show
instance for a data type, all of the types used in your type definition must also haveShow
instances. Just addderiving (Show)
to the end of all of yourdata
definitions. You may want to just get in the habit of addingderiving (Eq, Show)
to all yourdata
types, since you'll almost always want structural equality tests and showability for your types.Also, you cannot make a class instance of any sort for a type alias, only for a type. The keyword
type
defines a type alias, not a new type. If you make aShow
instance for yourRBT a
type, it will automatically be used for anything you declare as aSet a
, sinceSet a
is just an alias forRBT a
.