How to avoid both duplicate instances and extraneous instance declarations?
I am having trouble making a type system for my EDSL in Haskell. Can someone help? A simplified description of my problem follows. I have three classes, A, B1, and B2. I want all instances of B1 to be instances of A. I want all instances of B2 to be instances of A. None of the classes have methods. The following does NOT work, because of a duplicate instance declaration for A: class A a class B1 b1 class B2 b2 instance B1 x => A x instance B2 x => A x -- duplicate instance, won't compile data T = T instance B1 T The following DOES work, but it requires that I explicitly give instance declarations of A for all instances of B1 and B2: class A a class A a => B1 a class A a => B2 a data T = T instance A T -- I don't want to have to specify this! instance B1 T Of course, this is a simplified example. In a complicated type class hierarchy, in a program with many instances of, say B1, having to provide instance declarations for A is laborious. Is there a way to avoid this? How can I tell Haskell "all instances of B1 are automatically instances of A". -- Robin Bate Boerop
On 4/22/06, Robin Bate Boerop <robin_bb@acm.org> wrote:
I am having trouble making a type system for my EDSL in Haskell. Can someone help? A simplified description of my problem follows.
I have three classes, A, B1, and B2. I want all instances of B1 to be instances of A. I want all instances of B2 to be instances of A. None of the classes have methods.
The following does NOT work, because of a duplicate instance declaration for A:
I think with GHC, you can use the flag -fallow-overlapping-instances, and for GHCi, there's :set -fallow-overlapping-instances and then :reload.
This does not work. The compiler gives the same error with or without "-fallow-overlapping-instances". -- Robin Bate Boerop On 22-Apr-06, at 12:39 PM, ihope wrote:
On 4/22/06, Robin Bate Boerop <robin_bb@acm.org> wrote:
I am having trouble making a type system for my EDSL in Haskell. Can someone help? A simplified description of my problem follows.
I have three classes, A, B1, and B2. I want all instances of B1 to be instances of A. I want all instances of B2 to be instances of A. None of the classes have methods.
The following does NOT work, because of a duplicate instance declaration for A:
I think with GHC, you can use the flag -fallow-overlapping-instances, and for GHCi, there's :set -fallow-overlapping-instances and then :reload. _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
The error given by GHC (with or without the -fallow-overlapping- instances) is question.hs:6:0: Duplicate instance declarations: question.hs:6:0: instance (B1 x) => A x question.hs:7:0: instance (B2 x) => A x -- Robin Bate Boerop On 22-Apr-06, at 1:01 PM, ihope wrote:
On 4/22/06, Robin Bate Boerop <robin_bb@acm.org> wrote:
This does not work. The compiler gives the same error with or without "-fallow-overlapping-instances".
Just what is the error?
Robin,
The following does NOT work, because of a duplicate instance declaration for A:
class A a class B1 b1 class B2 b2 instance B1 x => A x instance B2 x => A x -- duplicate instance, won't compile data T = T instance B1 T
Yes, this doesn't work and I think there is no GHC extension that supports this.
The following DOES work, but it requires that I explicitly give instance declarations of A for all instances of B1 and B2:
class A a class A a => B1 a class A a => B2 a data T = T instance A T -- I don't want to have to specify this! instance B1 T
If you replace the instance you don't want to specify with:
instance B1 a => A a and use the following flags to start ghc: -fglasgow-exts -fallow-undecidable-instances
You can add other datatypes, and you only have to give an instance for class B1. Good luck! Gerrit
Gerrit, Thanks for your help. Yes, your suggestion below will allow me to give only an instance declaration for B1 (and get the A declaration for free, if you will). However, I meant to suggest that there were other T's which are not instances of B1 but of B2. I will be back in the same situation for those T's as I was previously in with T. I can't add instance B2 a => A a in addition to instance B1 a => A a because of the duplicate instance situation. So, my problem remains. -- Robin Bate Boerop On 22-Apr-06, at 2:01 PM, Gerrit van den Geest wrote:
Robin,
The following does NOT work, because of a duplicate instance declaration for A:
class A a class B1 b1 class B2 b2 instance B1 x => A x instance B2 x => A x -- duplicate instance, won't compile data T = T instance B1 T
Yes, this doesn't work and I think there is no GHC extension that supports this.
The following DOES work, but it requires that I explicitly give instance declarations of A for all instances of B1 and B2:
class A a class A a => B1 a class A a => B2 a data T = T instance A T -- I don't want to have to specify this! instance B1 T
If you replace the instance you don't want to specify with:
instance B1 a => A a and use the following flags to start ghc: -fglasgow-exts -fallow-undecidable-instances
You can add other datatypes, and you only have to give an instance for class B1.
Good luck!
Gerrit
You want all instances of B1 to be instances of A and all instances of B2 to be instances of A. This means: forall a. B1 a => A a and forall a. B2 a => A a I think this is not possible with type-classes and the type class extensions in Haskell, because the compiler can't construct the proofs deterministically anymore. The compiler has two choices, use an instance of B1 to construct a proof for A, or use an instance of B2 to construct a proof for A. However, if the compiler has to proof (A Int) and there is no instance (B1 Int), but there is an instance (B2 Int). I can imagine that a compiler is smart enough to use (B2 Int) .... Gerrit
Gerrit,
Thanks for your help. Yes, your suggestion below will allow me to give only an instance declaration for B1 (and get the A declaration for free, if you will).
However, I meant to suggest that there were other T's which are not instances of B1 but of B2. I will be back in the same situation for those T's as I was previously in with T. I can't add
instance B2 a => A a
in addition to
instance B1 a => A a
because of the duplicate instance situation. So, my problem remains.
-- Robin Bate Boerop
On 22-Apr-06, at 2:01 PM, Gerrit van den Geest wrote:
Robin,
The following does NOT work, because of a duplicate instance declaration for A:
class A a class B1 b1 class B2 b2 instance B1 x => A x instance B2 x => A x -- duplicate instance, won't compile data T = T instance B1 T
Yes, this doesn't work and I think there is no GHC extension that supports this.
The following DOES work, but it requires that I explicitly give instance declarations of A for all instances of B1 and B2:
class A a class A a => B1 a class A a => B2 a data T = T instance A T -- I don't want to have to specify this! instance B1 T
If you replace the instance you don't want to specify with:
instance B1 a => A a and use the following flags to start ghc: -fglasgow-exts -fallow-undecidable-instances
You can add other datatypes, and you only have to give an instance for class B1.
Good luck!
Gerrit
You want all instances of B1 to be instances of A and all instances of B2 to be instances of A. This means: forall a. B1 a => A a and forall a. B2 a => A a I think this is not possible with type-classes and the type class extensions in Haskell, because the compiler can't construct the proofs deterministically anymore. The compiler has two choices, use an instance of B1 to construct a proof for A, or use an instance of B2 to construct a proof for A. However, if the compiler has to proof (A Int) and there is no instance (B1 Int), but there is an instance (B2 Int). I can imagine that a compiler is smart enough to use (B2 Int) .... Gerrit
Gerrit,
Thanks for your help. Yes, your suggestion below will allow me to give only an instance declaration for B1 (and get the A declaration for free, if you will).
However, I meant to suggest that there were other T's which are not instances of B1 but of B2. I will be back in the same situation for those T's as I was previously in with T. I can't add
instance B2 a => A a
in addition to
instance B1 a => A a
because of the duplicate instance situation. So, my problem remains.
-- Robin Bate Boerop
On 22-Apr-06, at 2:01 PM, Gerrit van den Geest wrote:
Robin,
The following does NOT work, because of a duplicate instance declaration for A:
class A a class B1 b1 class B2 b2 instance B1 x => A x instance B2 x => A x -- duplicate instance, won't compile data T = T instance B1 T
Yes, this doesn't work and I think there is no GHC extension that supports this.
The following DOES work, but it requires that I explicitly give instance declarations of A for all instances of B1 and B2:
class A a class A a => B1 a class A a => B2 a data T = T instance A T -- I don't want to have to specify this! instance B1 T
If you replace the instance you don't want to specify with:
instance B1 a => A a and use the following flags to start ghc: -fglasgow-exts -fallow-undecidable-instances
You can add other datatypes, and you only have to give an instance for class B1.
Good luck!
Gerrit
I have three classes, A, B1, and B2. I want all instances of B1 to be instances of A. I want all instances of B2 to be instances of A.
if you mean to ensure that an instance of A should be a pre-requisite for defining instances of B1/B2, then your second approach might be more appropriate. if you mean to ensure that an instance of A is a necessary consequence of having an instance for either of B1/B2, then your first approach seems close, but runs into a technical issue: by default, an instance of A by means of an instance of B1 may differ from an instance of A by means of an instance of B2.
None of the classes have methods.
The following does NOT work, because of a duplicate instance declaration for A:
class A a class B1 b1 class B2 b2 instance B1 x => A x instance B2 x => A x -- duplicate instance, won't compile data T = T instance B1 T
the question is: if both B1 x and B2 x hold, does it matter which one is chosen in the proof of A x? if it does, how is the implementation to choose the right one, and if it doesn't (one might then ask why B1 and B2 are separate in the first place), how is the implementation to know that? you can introduce an arbitrary distinction in the two proofs, and then throw that distinction away later, as shown below, but whether or not that works depends on your application context. for instance, f is accepted and can be applied in either hugs or ghc; but hugs would complain about the commented out A; ghci would accept A, and the definition of g, but would complain about any use of g. cheers, claus {-# OPTIONS_GHC -fglasgow-exts #-} {-# OPTIONS_GHC -fallow-undecidable-instances #-} class A' a x -- class A a -- instance A' a b => A a data B1T class B1 b1 data B2T class B2 b2 instance B1 x => A' x B1T instance B2 x => A' x B2T -- duplicate instance, won't compile data T = T instance B1 T f :: (forall b . A' x b => x) -> String f x = undefined -- g :: A x => x -> String -- g = undefined
Claus, You have given a very good analysis of the situation. Thank you. I mean to ensure that "an instance of A is a necessary consequence of having an instance for either of B1/B2", in your words. Further, in my situation, no data type will be an instance of both B1 and B2. So, the compiler will never have to make the choice that you discuss. However, I have no way (that I know) to tell the compiler this. If I did, then the compiler would never need to decide between an instance of A by means of B1 and an instance of A by means of B2. While the code you give may do the job (I haven't tried it), it doesn't help my problem because it requires that I do more typing. I want to avoid the extra typing of "instance A T" when I've already typed "instance B1 T", say. -- Robin Bate Boerop On 22-Apr-06, at 3:51 PM, Claus Reinke wrote:
I have three classes, A, B1, and B2. I want all instances of B1 to be instances of A. I want all instances of B2 to be instances of A.
if you mean to ensure that an instance of A should be a pre- requisite for defining instances of B1/B2, then your second approach might be more appropriate. if you mean to ensure that an instance of A is a necessary consequence of having an instance for either of B1/B2, then your first approach seems close, but runs into a technical issue:
by default, an instance of A by means of an instance of B1 may differ from an instance of A by means of an instance of B2.
None of the classes have methods. The following does NOT work, because of a duplicate instance declaration for A: class A a class B1 b1 class B2 b2 instance B1 x => A x instance B2 x => A x -- duplicate instance, won't compile data T = T instance B1 T
the question is: if both B1 x and B2 x hold, does it matter which one is chosen in the proof of A x? if it does, how is the implementation to choose the right one, and if it doesn't (one might then ask why B1 and B2 are separate in the first place), how is the implementation to know that?
you can introduce an arbitrary distinction in the two proofs, and then throw that distinction away later, as shown below, but whether or not that works depends on your application context. for instance, f is accepted and can be applied in either hugs or ghc; but hugs would complain about the commented out A; ghci would accept A, and the definition of g, but would complain about any use of g.
cheers, claus
{-# OPTIONS_GHC -fglasgow-exts #-} {-# OPTIONS_GHC -fallow-undecidable-instances #-}
class A' a x -- class A a -- instance A' a b => A a
data B1T class B1 b1
data B2T class B2 b2
instance B1 x => A' x B1T instance B2 x => A' x B2T -- duplicate instance, won't compile
data T = T instance B1 T
f :: (forall b . A' x b => x) -> String f x = undefined
-- g :: A x => x -> String -- g = undefined
participants (4)
-
Claus Reinke -
Gerrit van den Geest -
ihope -
Robin Bate Boerop