Beginners Digest, Vol 74, Issue 5

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

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>

Reply | Threaded
Open this post in threaded view
|

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>

Reply | Threaded
Open this post in threaded view
|

Beginners Digest, Vol 74, Issue 5

Bob Ippolito
In reply to this post by Neeraj Rao
The only necessary and common constraint is Eq. Other constraints such as
Ord or Hashable could be used to implement Set much more efficiently, but
they are not strictly necessary.


On Wed, Aug 13, 2014 at 8: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
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140813/e803ba2d/attachment.html>