[Haskell-beginners] expressing constraints 101

12 Aug 2014

      Hi All,

I am working through an exercise in Chris Okasaki's book (#2.2). In the 
book, he is trying to implement a minimal interface for a Set. I wrote 
that simple interface in Haskell as:

class Set s where
     empty  :: s a                -- returns an empty set of type Set of a
     insert :: a -> s a -> s a   -- returns set with new element inserted
     member :: a -> s a -> Bool  -- True if element is a member of the Set

To implement that interface with the appropriately O(log n) insert and 
member functions he suggests the use of a Binary Search Tree, which I 
translated to Haskell as:

data Tree a = Empty | MkTree (Tree a) a (Tree a)

But for the tree to work, we also need the "a"s to be totally ordered. 
I.e. (Ord a) is a constraint. So, it makes sense to write:

treeEmpty :: Tree a
treeEmpty = Empty

treeInsert :: Ord a => a -> Tree a -> Tree a
treeInsert = undefined

treeMember :: Ord a => a -> Tree a -> Bool
treeMember = undefined

Now, I would like to bind this implementation using Trees of an ordered 
type "a" to the set type class. So, I would like to write something like:

instance Set Tree where
     empty  = treeEmpty
     insert = treeInsert
     member = treeMember

But that doesn't work. Using GHC 7.6.3, I get a:

     No instance for (Ord a) arising from a use of `treeInsert'
     Possible fix:
       add (Ord a) to the context of
         the type signature for insert :: a -> Tree a -> Tree a
     In the expression: treeInsert a
     In an equation for `insert': insert a = treeInsert a
     In the instance declaration for `Set Tree'

Which makes sense, but I'm not sure how to express this constraint.
So, what is the proper way to do this?
Where have I gone wrong?

Thanks!

Dimitri

[Haskell-beginners] expressing constraints 101

Dimitri DeFigueiredo