flexible contexts and context reduction
Hi, I'm a bit confused about why the following program doesn't compile (in any of 6.6.1, 6.8.1 and 6.9.20080316). Shouldn't the Ord (a, b) context be reduced? Cheers, Ganesh {-# LANGUAGE FlexibleContexts #-} module Test2 where foo :: Ord (a, b) => (a, b) -> (a, b) foo = bar bar :: (Ord a, Ord b) => (a, b) -> (a, b) bar = id
On Wed, Mar 26, 2008 at 08:52:43PM +0000, Ganesh Sittampalam wrote:
I'm a bit confused about why the following program doesn't compile (in any of 6.6.1, 6.8.1 and 6.9.20080316). Shouldn't the Ord (a, b) context be reduced?
{-# LANGUAGE FlexibleContexts #-}
module Test2 where
foo :: Ord (a, b) => (a, b) -> (a, b) foo = bar
bar :: (Ord a, Ord b) => (a, b) -> (a, b) bar = id
To use bar, you need (Ord a, Ord b). You're assuming that Ord (a, b) implies that, but it's the other way round.
On Wed, 26 Mar 2008, Ross Paterson wrote:
On Wed, Mar 26, 2008 at 08:52:43PM +0000, Ganesh Sittampalam wrote:
I'm a bit confused about why the following program doesn't compile (in any of 6.6.1, 6.8.1 and 6.9.20080316). Shouldn't the Ord (a, b) context be reduced?
To use bar, you need (Ord a, Ord b). You're assuming that Ord (a, b) implies that, but it's the other way round.
Oh yes, I see. Thanks. Ganesh
On Wed, 26 Mar 2008, Ganesh Sittampalam wrote:
On Wed, 26 Mar 2008, Ross Paterson wrote:
On Wed, Mar 26, 2008 at 08:52:43PM +0000, Ganesh Sittampalam wrote:
I'm a bit confused about why the following program doesn't compile (in any of 6.6.1, 6.8.1 and 6.9.20080316). Shouldn't the Ord (a, b) context be reduced?
To use bar, you need (Ord a, Ord b). You're assuming that Ord (a, b) implies that, but it's the other way round.
Logically, the implication holds. There's an equivalence: Ord a /\ Ord b <=> Ord (a,b) Why it does or doesn't work in a Haskell impelmentation iss an implementation issue / language design issue.. There's a paper by Martin Sulzmann about extensible superclasses, which shows how this can be implemented if you don't use dictionaries for your typeclasses, but the type-passing scheme. The problem with dictionaries is that you have to store the superclass dictionaries, here Ord a and Ord b, in the dictionary, here Ord (a,b). However, what superclass dictionaries you have to store depends on the instance, e.g. Ord Int doesn't have any superclass and Ord [a] has superclass Ord a. There maybe wasn't an easy solution, but here is my idea of how to to it with data or type families. The dictionary type would be: data OrdDict a = { (<) :: a -> a -> Bool , ... , super :: Super a } type family Super a :: * type instance Super Int = () type instance Super [a] = OrdDict a type instance Super (a,b) = (OrdDict a, OrdDict b) A similar solution is possible with a data family Super (but obviously I'm in favor of type families :) The openness of the family matches the openness of the type classes. There is a little overhead in carrying around the superclasses. Now ask your favorite Haskell system to implement this feature :) Tom -- Tom Schrijvers Department of Computer Science K.U. Leuven Celestijnenlaan 200A B-3001 Heverlee Belgium tel: +32 16 327544 e-mail: tom.schrijvers@cs.kuleuven.be url: http://www.cs.kuleuven.be/~toms/
| >> To use bar, you need (Ord a, Ord b). You're assuming that Ord (a, b) | >> implies that, but it's the other way round. | | Logically, the implication holds. There's an equivalence: | | Ord a /\ Ord b <=> Ord (a,b) | ... | The problem with dictionaries is that you have to store the superclass | dictionaries, here Ord a and Ord b, in the dictionary, here Ord (a,b). | However, what superclass dictionaries you have to store depends on the | instance, e.g. Ord Int doesn't have any superclass and Ord [a] has | superclass Ord a. In Haskell the "superclass(es)", if any, are declared in the class decl. Thus class Eq a => Ord a where ... Here Eq is the superclass of Ord. You're talking about something else: the dictionaries (Ord a, Ord b) from which the Ord (a,b) dictionary were constructed. We don't have a very good name for these guys, but "superclass" isn't a good one. Otherwise I agree with all you say. Your idea of using type families is cool. | data OrdDict a = | { (<) :: a -> a -> Bool | , ... | , super :: Super a | } | | type family Super a :: * | type instance Super Int = () | type instance Super [a] = OrdDict a | type instance Super (a,b) = (OrdDict a, OrdDict b) | | A similar solution is possible with a data family Super (but obviously I'm | in favor of type families :) Can you say why? A data family would work fine here. But it's not a big deal. So the other question is whether this is useful. How often do people write stuff like this? f :: Ord [a] => a -> a -> Bool f x y = x>y Nevertheless, I hadn't realised it was possible before, and now I can see it is. Simon
You're talking about something else: the dictionaries (Ord a, Ord b) from which the Ord (a,b) dictionary were constructed. We don't have a very good name for these guys, but "superclass" isn't a good one.
Otherwise I agree with all you say. Your idea of using type families is cool.
| data OrdDict a = | { (<) :: a -> a -> Bool | , ... | , super :: Super a | } | | type family Super a :: * | type instance Super Int = () | type instance Super [a] = OrdDict a | type instance Super (a,b) = (OrdDict a, OrdDict b) | | A similar solution is possible with a data family Super (but obviously I'm | in favor of type families :)
Can you say why? A data family would work fine here. But it's not a big deal.
Just a matter of taste, and familiarity.
So the other question is whether this is useful. How often do people write stuff like this? f :: Ord [a] => a -> a -> Bool f x y = x>y
This paper has some examples, I believe: Modular Generic Programming with Extensible Superclasses Martin Sulzmann and Meng Wang In Workshop on Generic Programming (WGP'06) http://www.comp.nus.edu.sg/~sulzmann/publications/wgp06-modulargeneric.ps
Nevertheless, I hadn't realised it was possible before, and now I can see it is.
I'd be nice to know of people who need or would like to have this feature. Tom -- Tom Schrijvers Department of Computer Science K.U. Leuven Celestijnenlaan 200A B-3001 Heverlee Belgium tel: +32 16 327544 e-mail: tom.schrijvers@cs.kuleuven.be url: http://www.cs.kuleuven.be/~toms/
participants (4)
-
Ganesh Sittampalam -
Ross Paterson -
Simon Peyton-Jones -
Tom Schrijvers