[Haskell-beginners] Beginners Digest, Vol 74, Issue 5

[Neeraj Rao]

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 at ucdavis.edu>
> To: The Haskell-Beginners Mailing List - Discussion of primarily
>         beginner-level topics related to Haskell <beginners at haskell.org>
> Subject: [Haskell-beginners] expressing constraints 101
> Message-ID: <53EAD801.30801 at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140813/6d4fe279/attachment.html>