<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Thanks guys. It seems like type families are the way to go, but I am
surprised that there is no way to express this in standard Haskell.<br>
<br>
On a follow up note, will GADTs bring this into the main language? I
seem to remember a talk by Simon PJ on how to build data structures
whose representation depend on the types of their elements by using
GADTs. Thinking about it now, it seems that's what I want here. If
the elements are Ord-ered I can implement Set with a Tree, on the
other hand, if they are only Eq and Hashable, I can use a hash table
to implement Set.<br>
<br>
Dimitri<br>
<br>
<br>
<div class="moz-cite-prefix">Em 13/08/14 01:23, akash g escreveu:<br>
</div>
<blockquote
cite="mid:CALiga_eb9OAcbeOZK5wkaVggJZ7uEkcPY74+zLbLuuqCv2ZX1g@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>Hi Dimitri,<br>
<br>
Did a bit of research and found type families to be a good
fit for this (<a moz-do-not-send="true"
href="http://www.haskell.org/ghc/docs/latest/html/users_guide/type-families.html">http://www.haskell.org/ghc/docs/latest/html/users_guide/type-families.html</a>).
Type families lets us define the contraints (and a lot of
other things) when creating an instance. I still do not know
if this is the ideal solution, but it is still a lot better
than the previous solution that I posted.<br>
<br>
{-# LANGUAGE ConstraintKinds #-}<br>
{-# LANGUAGE TypeFamilies #-}<br>
import GHC.Exts<br>
<br>
class Set s where<br>
type C s a :: Constraint -- Here, the explicit type that we
would have given is turned into a type synonym of the kind
Constraint, from GHC.Exts. <br>
empty :: s a <br>
insert :: (C s a) => a -> s a -> s a<br>
member :: (C s a) => a -> s a -> Bool <br>
<br>
<br>
data Tree a = Empty | MkTree (Tree a) a (Tree a)<br>
<br>
treeEmpty :: Tree a<br>
treeEmpty = Empty<br>
<br>
treeInsert :: Ord a => a -> Tree a -> Tree a<br>
treeInsert = undefined<br>
<br>
treeMember :: Ord a => a -> Tree a -> Bool<br>
treeMember = undefined<br>
<br>
instance Set Tree where<br>
type C Tree a = Ord a -- Here, we are setting the type
constraint to Ord a, where a is again a type variable.<br>
empty = treeEmpty<br>
member = treeMember<br>
insert = treeInsert<br>
<br>
<br>
</div>
<div>- Akash G<br>
</div>
<div><br>
</div>
<br>
<div><br>
</div>
</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On Wed, Aug 13, 2014 at 11:41 AM,
Dimitri DeFigueiredo <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:defigueiredo@ucdavis.edu" target="_blank">defigueiredo@ucdavis.edu</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> Hi G Akash,<br>
<br>
Is that the only solution? I thought about that. The
problem with it is that it changes the Set type class. I
want the Set type class to be able to contain elements of
any type, not just members of Ord. <br>
<br>
I think the type class represents a "Set" interface that
is general. It is the implementation using trees that is
only available for Ordered types. And there may be other
implementations that don't need this constraint. So, if
possible, I don't want to change the Set type class. Isn't
there another way to fix it?<br>
<br>
<br>
Thanks,<br>
<br>
<br>
Dimitri<br>
<br>
<br>
<div>Em 12/08/14 23:18, akash g escreveu:<br>
</div>
<div>
<div class="h5">
<blockquote type="cite">
<div dir="ltr">
<div>
<div>Hi Dimitri,<br>
<br>
</div>
You can express the constraints as below<br>
<br>
class Set s where<br>
empty :: s a -- returns an
empty set of type Set of a<br>
insert :: (Ord a) => a -> s a -> s
a -- returns set with new element inserted<br>
member :: (Ord a) => a -> s a ->
Bool -- True if element is a member of the Set<br>
<br>
</div>
<div>This is because when you define tree as an
instance of the typeclass 'Set', you don't match
the constraints on the functions that the
functions that it wants you to implement That
is, when you do:<br>
<br>
<br>
treeInsert :: Ord a => a -> Tree a ->
Tree a<br>
treeInsert = undefined<br>
<br>
instance Set Tree where<br>
empty = treeEmpty<br>
insert = treeInsert<br>
member = treeMember<br>
<br>
</div>
<div>The type signature doesn't match when you do
insert=treeInsert or member=treeMember, since
you have<br>
</div>
<div><br>
class Set s where<br>
</div>
<div> insert :: a -> s a -> s a<br>
<br>
</div>
<div>Hope this helps<br>
</div>
<div><br>
</div>
<div>- G Akash <br>
</div>
<div>
<div><br>
</div>
</div>
</div>
<div class="gmail_extra"> <br>
<br>
<div class="gmail_quote">On Wed, Aug 13, 2014 at
8:44 AM, Dimitri DeFigueiredo <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:defigueiredo@ucdavis.edu"
target="_blank">defigueiredo@ucdavis.edu</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0
0 0 .8ex;border-left:1px #ccc
solid;padding-left:1ex"> Hi All,<br>
<br>
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:<br>
<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>
<br>
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:<br>
<br>
data Tree a = Empty | MkTree (Tree a) a (Tree
a)<br>
<br>
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:<br>
<br>
treeEmpty :: Tree a<br>
treeEmpty = Empty<br>
<br>
treeInsert :: Ord a => a -> Tree a ->
Tree a<br>
treeInsert = undefined<br>
<br>
treeMember :: Ord a => a -> Tree a ->
Bool<br>
treeMember = undefined<br>
<br>
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:<br>
<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>
Dimitri<br>
<br>
<br>
<br>
<br>
<br>
<br>
_______________________________________________<br>
Beginners mailing list<br>
<a moz-do-not-send="true"
href="mailto:Beginners@haskell.org"
target="_blank">Beginners@haskell.org</a><br>
<a moz-do-not-send="true"
href="http://www.haskell.org/mailman/listinfo/beginners"
target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
Beginners mailing list
<a moz-do-not-send="true" href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a>
<a moz-do-not-send="true" href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a>
</pre>
</blockquote>
<br>
</div>
</div>
</div>
<br>
_______________________________________________<br>
Beginners mailing list<br>
<a moz-do-not-send="true"
href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a moz-do-not-send="true"
href="http://www.haskell.org/mailman/listinfo/beginners"
target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
<br>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Beginners mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Beginners@haskell.org">Beginners@haskell.org</a>
<a class="moz-txt-link-freetext" href="http://www.haskell.org/mailman/listinfo/beginners">http://www.haskell.org/mailman/listinfo/beginners</a>
</pre>
</blockquote>
<br>
</body>
</html>