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

[Neeraj Rao]

Sorry, I just realized this is exactly what Akash suggested.


On Wed, Aug 13, 2014 at 11:21 AM, Neeraj Rao <neeraj2608 at gmail.com> wrote:

> 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/0bdcff8b/attachment.html>