Why not add the Ord constraint to the function signatures in the class
definition?
class Set s where
empty :: s a
insert :: Ord a => a -> s a -> s a
member :: Ord a => a -> s a -> Bool
Seems to me like insert and member do need those constraints, irrespective
of what type 's' is.
Message: 1
> Date: Tue, 12 Aug 2014 21:14:09 -0600
> From: Dimitri DeFigueiredo <defigueiredo(a)ucdavis.edu>
> To: The Haskell-Beginners Mailing List - Discussion of primarily
> beginner-level topics related to Haskell <beginners(a)haskell.org>
> Subject: [Haskell-beginners] expressing constraints 101
> Message-ID: <53EAD801.30801(a)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!
Dimitri
