<div dir="ltr">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.</div><div class="gmail_extra">
<br><br><div class="gmail_quote">On Wed, Aug 13, 2014 at 8:21 AM, Neeraj Rao <span dir="ltr"><<a href="mailto:neeraj2608@gmail.com" target="_blank">neeraj2608@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Why not add the Ord constraint to the function signatures in the class definition?<div><br></div><div><div>class Set s where</div><div>    empty :: s a</div><div>    insert :: Ord a => a -> s a -> s a</div>

<div>    member :: Ord a => a -> s a -> Bool</div><div><br></div><div>Seems to me like insert and member do need those constraints, irrespective of what type 's' is.</div><div class="gmail_extra"><br></div>

<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Message: 1<br>Date: Tue, 12 Aug 2014 21:14:09 -0600<br>From: Dimitri DeFigueiredo <<a href="mailto:defigueiredo@ucdavis.edu" target="_blank">defigueiredo@ucdavis.edu</a>><br>

To: The Haskell-Beginners Mailing List - Discussion of primarily<br>        beginner-level topics related to Haskell <<a href="mailto:beginners@haskell.org" target="_blank">beginners@haskell.org</a>><br>Subject: [Haskell-beginners] expressing constraints 101<br>

Message-ID: <<a href="mailto:53EAD801.30801@ucdavis.edu" target="_blank">53EAD801.30801@ucdavis.edu</a>><br>Content-Type: text/plain; charset=ISO-8859-1; format=flowed<br>Hi All,<br>I am working through an exercise in Chris Okasaki's book (#2.2). In the<br>

book, he is trying to implement a minimal interface for a Set. I wrote<br>that simple interface in Haskell as:<br>class Set s where<br>     empty  :: s a                -- returns an empty set of type Set of a<br>     insert :: a -> s a -> s a   -- returns set with new element inserted<br>

     member :: a -> s a -> Bool  -- True if element is a member of the Set<br>To implement that interface with the appropriately O(log n) insert and<br>member functions he suggests the use of a Binary Search Tree, which I<br>

translated to Haskell as:<br>data Tree a = Empty | MkTree (Tree a) a (Tree a)<br>But for the tree to work, we also need the "a"s to be totally ordered.<br>I.e. (Ord a) is a constraint. So, it makes sense to write:<br>

treeEmpty :: Tree a<br>treeEmpty = Empty<br>treeInsert :: Ord a => a -> Tree a -> Tree a<br>treeInsert = undefined<br>treeMember :: Ord a => a -> Tree a -> Bool<br>treeMember = undefined<br>Now, I would like to bind this implementation using Trees of an ordered<br>

type "a" to the set type class. So, I would like to write something like:</blockquote><br>instance Set Tree where<br>     empty  = treeEmpty<br>     insert = treeInsert<br>     member = treeMember<br><br>But that doesn't work. Using GHC 7.6.3, I get a:<br>

<br>     No instance for (Ord a) arising from a use of `treeInsert'<br>     Possible fix:<br>       add (Ord a) to the context of<br>         the type signature for insert :: a -> Tree a -> Tree a<br>     In the expression: treeInsert a<br>

     In an equation for `insert': insert a = treeInsert a<br>     In the instance declaration for `Set Tree'<br><br>Which makes sense, but I'm not sure how to express this constraint.<br>So, what is the proper way to do this?<br>

Where have I gone wrong?<br><br><br>Thanks!<br><br><div class="gmail_extra">Dimitri </div></div></div>
<br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div>