Re: [Haskell-beginners] expressing constraints 101

13 Aug 2014

      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 
mailto:defigueiredo@ucdavis.edu> 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
    Beginners@haskell.org mailto:Beginners@haskell.org
    http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners