Message: 1
Date: Tue, 12 Aug 2014 21:14:09 -0600
From: Dimitri DeFigueiredo <defigueiredo@ucdavis.edu>
To: The Haskell-Beginners Mailing List - Discussion of primarily
        beginner-level topics related to Haskell <beginners@haskell.org>
Subject: [Haskell-beginners] expressing constraints 101
Message-ID: <53EAD801.30801@ucdavis.edu>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
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!