[Haskell-beginners] expressing constraints 101
Dimitri DeFigueiredo
defigueiredo at ucdavis.edu
Wed Aug 13 03:14:09 UTC 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
More information about the Beginners
mailing list