Re: [Haskell-cafe] Instances of constrained datatypes
Can you not define functor like Hughes defines a restricted monad (section 3 in the paper)... Keean Arjun Guha wrote: One way to do roughly what you want is to pass the dictionary yourself: >data EqDict a = EqDict { >leq :: a -> a -> Bool } > >data EqList a = EqList (EqDict a) [a] > >test :: EqList a -> EqList a -> Bool >test (EqList dict (a0:as)) (EqList _ (b0:bs)) = (leq dict) a0 b0 This is like the `object-oriented approach' in John Hughes' paper. Let's switch to the set example in his paper: > data EqDict a = EqDict { isEq:: a -> a -> Bool } > data Set a = Set (EqDict a) [a] So, to make it a functor, as I originally wanted: > instance Functor Set where > fmap f (Set dict ls) = Set dict' ls' where > ls' = nubBy (isEq dict') ls > dict' = ??? There really isn't a way to define dict' for the resultant Set. -Arjun ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Instances of constrained datatypes
One way to do roughly what you want is to pass the dictionary yourself: >data EqDict a = EqDict { > leq :: a -> a -> Bool } > >data EqList a = EqList (EqDict a) [a] > >test :: EqList a -> EqList a -> Bool >test (EqList dict (a0:as)) (EqList _ (b0:bs)) = (leq dict) a0 b0 This is like the `object-oriented approach' in John Hughes' paper. Let's switch to the set example in his paper: > data EqDict a = EqDict { isEq:: a -> a -> Bool } > data Set a = Set (EqDict a) [a] So, to make it a functor, as I originally wanted: > instance Functor Set where > fmap f (Set dict ls) = Set dict' ls' where > ls' = nubBy (isEq dict') ls > dict' = ??? There really isn't a way to define dict' for the resultant Set. -Arjun ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Instances of constrained datatypes
I believe that you may find these papers relevant: "Bulk types with class" http://research.microsoft.com/%7Esimonpj/Papers/collections.ps.gz "Restricted data types" http://www.cs.chalmers.se/~rjmh/Papers/restricted-datatypes.ps John's paper mentions that it would be great if the constraint simplifier could generate recursive dictionaries --- and indeed GHC's constraint simplifier now does exactly that. So you can apply his technique. I'm not 100% certain this addresses your problem, but I think it does. Simon | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of | Keean Schupke | Sent: 07 April 2005 09:30 | To: Keean Schupke | Cc: haskell-cafe@haskell.org | Subject: Re: [Haskell-cafe] Instances of constrained datatypes | | One way to do roughly what you want is to pass the dictionary yourself: | | >data EqDict a = EqDict { | >leq :: a -> a -> Bool } | > | >data EqList a = EqList (EqDict a) [a] | > | >test :: EqList a -> EqList a -> Bool | >test (EqList dict (a0:as)) (EqList _ (b0:bs)) = (leq dict) a0 b0 | | In this way the definition of equality on elements of type 'a' is passed | with the list type, so it can be used wherever the list type is used, | without requiring extra constraints. | |Keean. | | Keean Schupke wrote: | | > I think it is more a problem of imlpementation than one of what is | > desirable. A Constrained data type: | > | > data (Eq v) => EqList v = EqList [v] | > | > The problem is how to get the dictionary for the class Eq to the | > application site: | > | > f :: EqList v -> EqList v | > f (EqList (u0:us)) (EqList (v0:vs)) | v0 == u0 = ... | > | > Which of course does not work... the constraint needs to be in the | > function | > type signature: | > | > f :: Eq v => EqList v -> EqList v | > | > Things are worse though, as even functions that use no methods of Eq will | > require the constraint. | > | > The constraint on the data type does not stop you construction EqLists | > from | > non Eq members... of course this gets detected the moment you try and | > use it | > in a constrained function. | > | > | > In other words using the constraint in the data type does nothing... | > you may as well just do: | > | > f :: Eq v => [v] -> [v] | > | > | > Infact I believe it was decided to remove the feature from Haskell98 | > entirely, but there was apparently some use for the 'syntax' although | > with a different effect. | > | >Keean. | > | > Cale Gibbard wrote: | > | >> I don't believe you can, but it would be nice. There are certain | >> types, such as Set, where it's not really possible to just remove the | >> constraint from the data declaration, and yet it would be nice if sets | >> could be instances of Monad and Functor. Currently, to be an instance | >> of Functor or Monad, your type has to be a functor defined on the | >> whole category of types. | >> | >> Could this issue be fixed somehow? Constrained instances would make | >> various typeclass-based libraries more applicable. What would it break | >> to allow instances where the types of functions defined by the | >> typeclass are further restricted? I suppose that checking that types | >> are correct becomes more difficult and non-local, because functions | >> which are defined using the typeclass won't already have that | >> constraint for obvious reasons. Still, the constraint is in the | >> instance, which must be around when the functions actually get | >> applied. There are probably bad interactions with the module system, | >> but I'm not certain. | >> | >> People must have talked about this before... was a consensus reached | >> that I'm not aware of? | >> | >> - Cale | >> | >> On Apr 6, 2005 2:10 AM, Arjun Guha <[EMAIL PROTECTED]> wrote: | >> | >> | >>> This is a contrived example, but contains the essence of what I'd like | >>> to do. Suppose I have this datatype: | >>> | >>> > data (Eq v) => EqList v = EqList [v] | >>> | >>> I'd like to make it an instance of Functor. However, fmap takes an | >>> arbitrary function of type a -> b. I need an Eq constraint on a and | >>> b. Is there any way to do this without creating my own `EqFunctor' | >>> class with explicitly-kinded quantification: | >>> | >>> > class (Eq a) => EqFunctor (f :: * -> *) a where | >>> > eqfmap:: (Eq b) => (a -> b) -> f a -> f b | >>> | >>> Thanks. | >>> | >>> -Arjun | >>> | >> | > | > ___ | > Haskell-Cafe mailing list | > Haskell-Cafe@haskell.org | > http://www.haskell.org/mailman/listinfo/haskell-cafe | | | ___ | Haskell-Cafe mailing list | Haskell-Cafe@haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Instances of constrained datatypes
One way to do roughly what you want is to pass the dictionary yourself: >data EqDict a = EqDict { >leq :: a -> a -> Bool } > >data EqList a = EqList (EqDict a) [a] > >test :: EqList a -> EqList a -> Bool >test (EqList dict (a0:as)) (EqList _ (b0:bs)) = (leq dict) a0 b0 In this way the definition of equality on elements of type 'a' is passed with the list type, so it can be used wherever the list type is used, without requiring extra constraints. Keean. Keean Schupke wrote: I think it is more a problem of imlpementation than one of what is desirable. A Constrained data type: data (Eq v) => EqList v = EqList [v] The problem is how to get the dictionary for the class Eq to the application site: f :: EqList v -> EqList v f (EqList (u0:us)) (EqList (v0:vs)) | v0 == u0 = ... Which of course does not work... the constraint needs to be in the function type signature: f :: Eq v => EqList v -> EqList v Things are worse though, as even functions that use no methods of Eq will require the constraint. The constraint on the data type does not stop you construction EqLists from non Eq members... of course this gets detected the moment you try and use it in a constrained function. In other words using the constraint in the data type does nothing... you may as well just do: f :: Eq v => [v] -> [v] Infact I believe it was decided to remove the feature from Haskell98 entirely, but there was apparently some use for the 'syntax' although with a different effect. Keean. Cale Gibbard wrote: I don't believe you can, but it would be nice. There are certain types, such as Set, where it's not really possible to just remove the constraint from the data declaration, and yet it would be nice if sets could be instances of Monad and Functor. Currently, to be an instance of Functor or Monad, your type has to be a functor defined on the whole category of types. Could this issue be fixed somehow? Constrained instances would make various typeclass-based libraries more applicable. What would it break to allow instances where the types of functions defined by the typeclass are further restricted? I suppose that checking that types are correct becomes more difficult and non-local, because functions which are defined using the typeclass won't already have that constraint for obvious reasons. Still, the constraint is in the instance, which must be around when the functions actually get applied. There are probably bad interactions with the module system, but I'm not certain. People must have talked about this before... was a consensus reached that I'm not aware of? - Cale On Apr 6, 2005 2:10 AM, Arjun Guha <[EMAIL PROTECTED]> wrote: This is a contrived example, but contains the essence of what I'd like to do. Suppose I have this datatype: > data (Eq v) => EqList v = EqList [v] I'd like to make it an instance of Functor. However, fmap takes an arbitrary function of type a -> b. I need an Eq constraint on a and b. Is there any way to do this without creating my own `EqFunctor' class with explicitly-kinded quantification: > class (Eq a) => EqFunctor (f :: * -> *) a where > eqfmap:: (Eq b) => (a -> b) -> f a -> f b Thanks. -Arjun ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Instances of constrained datatypes
One way to do roughly what you want is to pass the dictionary yourself: >data EqDict a = EqDict { >leq :: a -> a -> Bool } > >data EqList a = EqList (EqDict a) [a] > >test :: EqList a -> EqList a -> Bool >test (EqList dict (a0:as)) (EqList _ (b0:bs)) = (leq dict) a0 b0 In this way the definition of equality on elements of type 'a' is passed with the list type, so it can be used wherever the list type is used, without requiring extra constraints. Keean. Keean Schupke wrote: I think it is more a problem of imlpementation than one of what is desirable. A Constrained data type: data (Eq v) => EqList v = EqList [v] The problem is how to get the dictionary for the class Eq to the application site: f :: EqList v -> EqList v f (EqList (u0:us)) (EqList (v0:vs)) | v0 == u0 = ... Which of course does not work... the constraint needs to be in the function type signature: f :: Eq v => EqList v -> EqList v Things are worse though, as even functions that use no methods of Eq will require the constraint. The constraint on the data type does not stop you construction EqLists from non Eq members... of course this gets detected the moment you try and use it in a constrained function. In other words using the constraint in the data type does nothing... you may as well just do: f :: Eq v => [v] -> [v] Infact I believe it was decided to remove the feature from Haskell98 entirely, but there was apparently some use for the 'syntax' although with a different effect. Keean. Cale Gibbard wrote: I don't believe you can, but it would be nice. There are certain types, such as Set, where it's not really possible to just remove the constraint from the data declaration, and yet it would be nice if sets could be instances of Monad and Functor. Currently, to be an instance of Functor or Monad, your type has to be a functor defined on the whole category of types. Could this issue be fixed somehow? Constrained instances would make various typeclass-based libraries more applicable. What would it break to allow instances where the types of functions defined by the typeclass are further restricted? I suppose that checking that types are correct becomes more difficult and non-local, because functions which are defined using the typeclass won't already have that constraint for obvious reasons. Still, the constraint is in the instance, which must be around when the functions actually get applied. There are probably bad interactions with the module system, but I'm not certain. People must have talked about this before... was a consensus reached that I'm not aware of? - Cale On Apr 6, 2005 2:10 AM, Arjun Guha <[EMAIL PROTECTED]> wrote: This is a contrived example, but contains the essence of what I'd like to do. Suppose I have this datatype: > data (Eq v) => EqList v = EqList [v] I'd like to make it an instance of Functor. However, fmap takes an arbitrary function of type a -> b. I need an Eq constraint on a and b. Is there any way to do this without creating my own `EqFunctor' class with explicitly-kinded quantification: > class (Eq a) => EqFunctor (f :: * -> *) a where > eqfmap:: (Eq b) => (a -> b) -> f a -> f b Thanks. -Arjun ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Instances of constrained datatypes
I think it is more a problem of imlpementation than one of what is desirable. A Constrained data type: data (Eq v) => EqList v = EqList [v] The problem is how to get the dictionary for the class Eq to the application site: f :: EqList v -> EqList v f (EqList (u0:us)) (EqList (v0:vs)) | v0 == u0 = ... Which of course does not work... the constraint needs to be in the function type signature: f :: Eq v => EqList v -> EqList v Things are worse though, as even functions that use no methods of Eq will require the constraint. The constraint on the data type does not stop you construction EqLists from non Eq members... of course this gets detected the moment you try and use it in a constrained function. In other words using the constraint in the data type does nothing... you may as well just do: f :: Eq v => [v] -> [v] Infact I believe it was decided to remove the feature from Haskell98 entirely, but there was apparently some use for the 'syntax' although with a different effect. Keean. Cale Gibbard wrote: I don't believe you can, but it would be nice. There are certain types, such as Set, where it's not really possible to just remove the constraint from the data declaration, and yet it would be nice if sets could be instances of Monad and Functor. Currently, to be an instance of Functor or Monad, your type has to be a functor defined on the whole category of types. Could this issue be fixed somehow? Constrained instances would make various typeclass-based libraries more applicable. What would it break to allow instances where the types of functions defined by the typeclass are further restricted? I suppose that checking that types are correct becomes more difficult and non-local, because functions which are defined using the typeclass won't already have that constraint for obvious reasons. Still, the constraint is in the instance, which must be around when the functions actually get applied. There are probably bad interactions with the module system, but I'm not certain. People must have talked about this before... was a consensus reached that I'm not aware of? - Cale On Apr 6, 2005 2:10 AM, Arjun Guha <[EMAIL PROTECTED]> wrote: This is a contrived example, but contains the essence of what I'd like to do. Suppose I have this datatype: > data (Eq v) => EqList v = EqList [v] I'd like to make it an instance of Functor. However, fmap takes an arbitrary function of type a -> b. I need an Eq constraint on a and b. Is there any way to do this without creating my own `EqFunctor' class with explicitly-kinded quantification: > class (Eq a) => EqFunctor (f :: * -> *) a where > eqfmap:: (Eq b) => (a -> b) -> f a -> f b Thanks. -Arjun ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Instances of constrained datatypes
I don't believe you can, but it would be nice. There are certain types, such as Set, where it's not really possible to just remove the constraint from the data declaration, and yet it would be nice if sets could be instances of Monad and Functor. Currently, to be an instance of Functor or Monad, your type has to be a functor defined on the whole category of types. Could this issue be fixed somehow? Constrained instances would make various typeclass-based libraries more applicable. What would it break to allow instances where the types of functions defined by the typeclass are further restricted? I suppose that checking that types are correct becomes more difficult and non-local, because functions which are defined using the typeclass won't already have that constraint for obvious reasons. Still, the constraint is in the instance, which must be around when the functions actually get applied. There are probably bad interactions with the module system, but I'm not certain. People must have talked about this before... was a consensus reached that I'm not aware of? - Cale On Apr 6, 2005 2:10 AM, Arjun Guha <[EMAIL PROTECTED]> wrote: > This is a contrived example, but contains the essence of what I'd like > to do. Suppose I have this datatype: > > > data (Eq v) => EqList v = EqList [v] > > I'd like to make it an instance of Functor. However, fmap takes an > arbitrary function of type a -> b. I need an Eq constraint on a and > b. Is there any way to do this without creating my own `EqFunctor' > class with explicitly-kinded quantification: > > > class (Eq a) => EqFunctor (f :: * -> *) a where > > eqfmap:: (Eq b) => (a -> b) -> f a -> f b > > Thanks. > > -Arjun > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Instances of constrained datatypes
Arjun Guha <[EMAIL PROTECTED]> writes: > > data (Eq v) => EqList v = EqList [v] > > I'd like to make it an instance of Functor. However, fmap takes an > arbitrary function of type a -> b. I need an Eq constraint on a and > b. Is there any way to do this without creating my own `EqFunctor' > class with explicitly-kinded quantification: No. Why not to remove the Eq v constraint in the type? -- __("< Marcin Kowalczyk \__/ [EMAIL PROTECTED] ^^ http://qrnik.knm.org.pl/~qrczak/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Instances of constrained datatypes
This is a contrived example, but contains the essence of what I'd like to do. Suppose I have this datatype: > data (Eq v) => EqList v = EqList [v] I'd like to make it an instance of Functor. However, fmap takes an arbitrary function of type a -> b. I need an Eq constraint on a and b. Is there any way to do this without creating my own `EqFunctor' class with explicitly-kinded quantification: > class (Eq a) => EqFunctor (f :: * -> *) a where > eqfmap:: (Eq b) => (a -> b) -> f a -> f b Thanks. -Arjun ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe