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






_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners