Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. expressing constraints 101 (Dimitri DeFigueiredo)
2. Re: expressing constraints 101 (akash g)
3. Re: expressing constraints 101 (Dimitri DeFigueiredo)
4. Re: expressing constraints 101 (Karl Voelker)
----------------------------------------------------------------------
Message: 1
Date: Tue, 12 Aug 2014 21:14:09 -0600
From: Dimitri DeFigueiredo <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] expressing constraints 101
Message-ID: <[email protected]>
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
------------------------------
Message: 2
Date: Wed, 13 Aug 2014 10:48:19 +0530
From: akash g <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] expressing constraints 101
Message-ID:
<caliga_cye-f+p32hqfd79tf6+nqsurm3pk1pwh9mszcqs7_...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi Dimitri,
You can express the constraints as below
class Set s where
empty :: s a -- returns an empty set of type Set of a
insert :: (Ord a) => a -> s a -> s a -- returns set with new element
inserted
member :: (Ord a) => a -> s a -> Bool -- True if element is a member of
the Set
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:
treeInsert :: Ord a => a -> Tree a -> Tree a
treeInsert = undefined
instance Set Tree where
empty = treeEmpty
insert = treeInsert
member = treeMember
The type signature doesn't match when you do insert=treeInsert or
member=treeMember, since you have
class Set s where
insert :: a -> s a -> s a
Hope this helps
- G Akash
On Wed, Aug 13, 2014 at 8:44 AM, Dimitri DeFigueiredo <
[email protected]> wrote:
> 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
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140813/f9cb50b1/attachment-0001.html>
------------------------------
Message: 3
Date: Wed, 13 Aug 2014 00:11:08 -0600
From: Dimitri DeFigueiredo <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] expressing constraints 101
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
Hi G Akash,
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.
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?
Thanks,
Dimitri
Em 12/08/14 23:18, akash g escreveu:
> Hi Dimitri,
>
> You can express the constraints as below
>
> class Set s where
> empty :: s a -- returns an empty set of type Set of a
> insert :: (Ord a) => a -> s a -> s a -- returns set with new
> element inserted
> member :: (Ord a) => a -> s a -> Bool -- True if element is a
> member of the Set
>
> 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:
>
>
> treeInsert :: Ord a => a -> Tree a -> Tree a
> treeInsert = undefined
>
> instance Set Tree where
> empty = treeEmpty
> insert = treeInsert
> member = treeMember
>
> The type signature doesn't match when you do insert=treeInsert or
> member=treeMember, since you have
>
> class Set s where
> insert :: a -> s a -> s a
>
> Hope this helps
>
> - G Akash
>
>
>
> On Wed, Aug 13, 2014 at 8:44 AM, Dimitri DeFigueiredo
> <[email protected] <mailto:[email protected]>> wrote:
>
> 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
> [email protected] <mailto:[email protected]>
> http://www.haskell.org/mailman/listinfo/beginners
>
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140813/188f3d71/attachment-0001.html>
------------------------------
Message: 4
Date: Wed, 13 Aug 2014 00:15:07 -0700
From: Karl Voelker <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] expressing constraints 101
Message-ID:
<1407914107.2360121.152160749.08f0f...@webmail.messagingengine.com>
Content-Type: text/plain; charset="us-ascii"
On Tue, Aug 12, 2014, at 11:11 PM, Dimitri DeFigueiredo wrote:
Hi G Akash,
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.
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?
There are a variety of ways to deal with this using language
extensions, such as:
[1]https://gist.github.com/ktvoelker/af613fe5308b748b4606
-Karl
References
1. https://gist.github.com/ktvoelker/af613fe5308b748b4606
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140813/5dc3e082/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 74, Issue 5
****************************************
