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. Re: expressing constraints 101 (akash g)
----------------------------------------------------------------------
Message: 1
Date: Wed, 13 Aug 2014 12:53:44 +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_eb9oacbeozk5wkavggjz7uekcpy74+zlbluuqcv2z...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi Dimitri,
Did a bit of research and found type families to be a good fit for this (
http://www.haskell.org/ghc/docs/latest/html/users_guide/type-families.html).
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.
{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE TypeFamilies #-}
import GHC.Exts
class Set s where
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.
empty :: s a
insert :: (C s a) => a -> s a -> s a
member :: (C s a) => a -> s a -> Bool
data Tree a = Empty | MkTree (Tree a) a (Tree a)
treeEmpty :: Tree a
treeEmpty = Empty
treeInsert :: Ord a => a -> Tree a -> Tree a
treeInsert = undefined
treeMember :: Ord a => a -> Tree a -> Bool
treeMember = undefined
instance Set Tree where
type C Tree a = Ord a -- Here, we are setting the type constraint to Ord
a, where a is again a type variable.
empty = treeEmpty
member = treeMember
insert = treeInsert
- Akash G
On Wed, Aug 13, 2014 at 11:41 AM, Dimitri DeFigueiredo <
[email protected]> 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?
>
>
> 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]> 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
>>
>
>
>
> _______________________________________________
> Beginners mailing
> [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/184c21dd/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 74, Issue 6
****************************************
