Re: [Haskell-cafe] Removing polymorphism from type classes (viz. Functor) (Again)
Alexey Karakulov ankaraku...@gmail.com writes: (Ord b) must be deduced from (Functor (Set b)) but it doesn't. I don't know whether it's my mistake somewhere or ghc problem. I've come across this problem as well; the best solution I've seen so far is the one taken by Ganesh in his rmonad library: http://hackage.haskell.org/package/rmonad Thanks for the link, but RFunctor typeclass is still (more or less) polymorphic, so I couldn't write ByteString instance for it. (Really I don't care about ByteString, but it's good example). However, I could try to use Suitable+Constraints concept for non-polymorphic functors. Yeah, I'm working on something like this at the moment, but I'm currently stuck on naming: if I want to have Functor for kind * - *, what's a good name for a type class for kind *? Also, is there any type for which having a map a - a _doesn't_ make sense? Bloomfilters maybe? -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Removing polymorphism from type classes (viz. Functor) (Again)
On 15 August 2010 08:50, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: Yeah, I'm working on something like this at the moment, but I'm currently stuck on naming: if I want to have Functor for kind * - *, what's a good name for a type class for kind *? Conor McBride has suggested looking at arity families of functor-like things (functor, traversable, foldable, halfzippable(?)) may be worthwhile: http://www.haskell.org/pipermail/haskell-cafe/2008-June/044011.html Functors and bi-functors have obvious names, but naming zero arity and three-and-higher ones would need systematic treatment. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Removing polymorphism from type classes (viz. Functor) (Again)
On Sun, Aug 15, 2010 at 10:50 AM, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: Yeah, I'm working on something like this at the moment, but I'm currently stuck on naming: if I want to have Functor for kind * - *, what's a good name for a type class for kind *? I was thinking about EtaFunctor, which stands for η-expanded Functor. But I'm not sure about η-expansion is correct term for removing polymorphism from the type class. Also, is there any type for which having a map a - a _doesn't_ make sense? Bloomfilters maybe? Not the answer, but there are cases where having a map (a - b) - f - g could make some new sense: data BitList = ... fromBoolList :: [Bool] - BitList type instance NewPt [a] b = [b] type instance NewPt [a] Bool = BitList But this kind of overlapping type instance is not allowed in ghc (yet?) -- All the best, Alexey ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Removing polymorphism from type classes (viz. Functor) (Again)
I was inspired by George Pollard's posthttp://www.haskell.org/pipermail/haskell-cafe/2009-July/063981.htmlat haskell-cafe and tried to implement the non-polymorphic Functor class ( I named it Functor' ). I changed some names and added reasonable constraints. type family NewPt f a class Functor' f where type Point f map ∷ (a ~ Point f, b ~ Point g, g ~ NewPt f b, Functor' g) ⇒ (a → b) → f → g I would like to be able to write: type OldPt f = NewPt f (Point f) class (f ~ OldPt f) ⇒ Functor' f ... but ghc says it's not implemented yet (version 6.12.1). However, it's not the main problem. Now I can write some instances: type instance NewPt [a] b = [b] instance Functor' [a] where type Point [a] = a map = fmap type instance NewPt ByteString a = ByteString instance Functor' ByteString where type Point ByteString = Word8 map = BS.map But I can't write instance for Set: type instance NewPt (Set a) b = Set b instance Ord a ⇒ Functor' (Set a) where type Point (Set a) = a map = Set.map ghci complains: Could not deduce (Ord a1) from the context (g ~ NewPt (Set a) a1, a1 ~ Point g, Functor' g) arising from a use of `Set.map' at ... The type of Set.map is Set.map :: (Ord a, Ord b) = (a - b) - Set a - Set b (Ord a) is in the instance context, and what about b? Type of map for Set instance would be: original: map ∷ (a ~ Point f, b ~ Point g, g ~ NewPt f b, Functor' g) ⇒ (a → b) → f → g substitute: f → Set a, g → Set b map :: Functor' (Set b) ⇒ (a →b) →Set a →Set b (Ord b) must be deduced from (Functor (Set b)) but it doesn't. I don't know whether it's my mistake somewhere or ghc problem. (Sorry for my English, it's not perfect). -- All the best, Alexey ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Removing polymorphism from type classes (viz. Functor) (Again)
Alexey Karakulov ankaraku...@gmail.com writes: (Ord b) must be deduced from (Functor (Set b)) but it doesn't. I don't know whether it's my mistake somewhere or ghc problem. I've come across this problem as well; the best solution I've seen so far is the one taken by Ganesh in his rmonad library: http://hackage.haskell.org/package/rmonad -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Removing polymorphism from type classes (viz. Functor) (Again)
On Sat, Aug 14, 2010 at 2:27 PM, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: Alexey Karakulov ankaraku...@gmail.com writes: (Ord b) must be deduced from (Functor (Set b)) but it doesn't. I don't know whether it's my mistake somewhere or ghc problem. I've come across this problem as well; the best solution I've seen so far is the one taken by Ganesh in his rmonad library: http://hackage.haskell.org/package/rmonad -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com Thanks for the link, but RFunctor typeclass is still (more or less) polymorphic, so I couldn't write ByteString instance for it. (Really I don't care about ByteString, but it's good example). However, I could try to use Suitable+Constraints concept for non-polymorphic functors. -- All the best, Alexey ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Removing polymorphism from type classes (viz. Functor) (Again)
The non-type-changing map can be implemented as a type class - in my graphics lib Wumpus, I call it pointwise: class Pointwise sh where type Pt sh :: * pointwise :: (Pt sh - Pt sh) - sh - sh I think other people have posted it to the cafe under a different name, before I did: http://www.haskell.org/pipermail/haskell-cafe/2010-July/079784.html If I was doing Wumpus again though, I'd probably do with Pointwise. Best wishes Stephen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Removing polymorphism from type classes (viz. Functor) (Again)
On 14 August 2010 20:27, Stephen Tetley stephen.tet...@gmail.com wrote: If I was doing Wumpus again though, I'd probably do with Pointwise. Ahem, do without Pointwise Originally the types I operated on with Pointwise were more complicated than they are now and Pointwise seemed a benefit. But as I got a better understanding of the domain I was working in, I could simply my types; after doing this Pointwise has become rather superfluous. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Removing polymorphism from type classes (viz. Functor)
George Pollard schrieb: Ok, so I have a small idea I'm trying to work on; call it a Prelude-rewrite if you want. For this I want to be able to have the hierarchy Functor → Applicative → Monad. For Functor, I would like to be able to implement it for a wider variety of types, as there are types which have aren't polymorphic which would also benefit from having an instance. My running example for this set of types is ByteString; the module contains the method: map ∷ (Word8 → Word8) → ByteString → ByteString However, we cannot use this for Functor because ByteString isn't polymorphic. To get around this, I devised the following: Introduce a type family which represents ‘points’ inside the type: type family Point f ∷ ★ For ByteString we have: type instance Point ByteString = Word8 For a polymorphic example (lists) we have: type instance Point [a] = a I had the same in mind for Data.Set with Ord constraint for elements, StorableVector with Storable constraint for the elements, and Control.Monad.Excepetion.Asynchronous monad with Monoid constraint for the monadic result. I tried to come up with a class hierarchy: http://code.haskell.org/~thielema/category-constrained/src/Control/Constrained/ but I encountered the same problem with the Applicative class. Different from what I tried in Applicative.hs I think that the most flexible approach is to convert the ByteString (or Data.Set or StorableVector) to an interim data structure first where you do, say 'liftA3' aka 'zipWith3', then convert back to the real data structure, here ByteString. The interim data structure can be stream-fusion:Data.Stream, i.e. not a real data structure but an algorithm to read from the ByteString. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Removing polymorphism from type classes (viz. Functor)
It does seem that having quantified contexts would make this *much* easier... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Removing polymorphism from type classes (viz. Functor)
Well, you're going to wind up with a lot of cases where you really want a quantified context, even with just your Functor definition, but in that same spirit you can build an 'Applicative-like' instance as well. type family Arg f :: * type instance Arg [a - b] = [a] type family Result f :: * type instance Result [a - b] = [b] class Pointed f = Applicative f where (*) :: f - Arg f - Result f instance Applicative [a - b] where fs * xs = do f - fs; map f The thing is these definitions are very hard to actually use. I have a similar construction for Foldable/Traversable-like containers in the 'monoids' package as Data.Generator that you might want to look at for ideas. -Edward Kmett On Tue, Jul 7, 2009 at 7:03 PM, George Pollard por...@porg.es wrote: Ok, so I have a small idea I'm trying to work on; call it a Prelude-rewrite if you want. For this I want to be able to have the hierarchy Functor → Applicative → Monad. For Functor, I would like to be able to implement it for a wider variety of types, as there are types which have aren't polymorphic which would also benefit from having an instance. My running example for this set of types is ByteString; the module contains the method: map ∷ (Word8 → Word8) → ByteString → ByteString However, we cannot use this for Functor because ByteString isn't polymorphic. To get around this, I devised the following: Introduce a type family which represents ‘points’ inside the type: type family Point f ∷ ★ For ByteString we have: type instance Point ByteString = Word8 For a polymorphic example (lists) we have: type instance Point [a] = a Now Functor becomes: class SimpleFunctor f where fmap ∷ (Point f → Point f) → (f → f) However, this doesn't allow for the existence of functions with the type (a → b). I need to introduce another type into the class: class Functor f g where fmap ∷ (Point f → Point g) → (f → g) But having two types isn't very nice (for one thing we can't introduce a fundep because for lists as it fails one of the coverage conditions), so introduce another type family to represent types which can be produced by giving a free variable: type Subst f a ∷ ★ type Subst [a] b = [b] type Subst ByteString b = ByteString class Functor f where fmap ∷ (Point f → Point (Subst f a)) → (f → Subst f a) I'm not sure how much of a hack this is, or if there is a better way. It seems to be OK... Now I want to implement Applicative. It would make sense to have ‘return’ be split out into a separate class, because this can be restricted in a similar way to Functor: class Pointed f where return ∷ Point f → f instance Pointed [a] where return x = [x] instance Pointed ByteString where return = BS.singleton Now, I want to be able to restrict Applicative to things which have [Pointed f, and forall a b. Point f ~ (a → b)]. At the moment I can't figure this out because I believe it would require something like the ‘quantified contexts’ proposal: class (Pointed f, ∀ a b. Point f ~ (a → b)) ⇒ Applicative f where ... I could have something like: class (Pointed f, Point f ~ (a → b)) ⇒ Applicative f a b where apply ∷ f → Subst f a → Subst f b This is still not very nice, because it requires two more type variables in the class, and the non-type-families version is far more straightforward... in fact, it makes sense for the Applicative class to have a polymorphic type because it must be able to have ‘return’ applied to arbitrary functions (remember [fmap f xs ≡ return f `apply` xs]). So back to: class Applicative f where apply ∷ f (a → b) → f a → f b But then ‘return’ cannot be added via a superclass restriction to Pointed! I seem to have painted myself into a corner. Does anyone see a better way to go about this? Thanks, - George ___ 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] Removing polymorphism from type classes (viz. Functor)
Ok, so I have a small idea I'm trying to work on; call it a Prelude-rewrite if you want. For this I want to be able to have the hierarchy Functor → Applicative → Monad. For Functor, I would like to be able to implement it for a wider variety of types, as there are types which have aren't polymorphic which would also benefit from having an instance. My running example for this set of types is ByteString; the module contains the method: map ∷ (Word8 → Word8) → ByteString → ByteString However, we cannot use this for Functor because ByteString isn't polymorphic. To get around this, I devised the following: Introduce a type family which represents ‘points’ inside the type: type family Point f ∷ ★ For ByteString we have: type instance Point ByteString = Word8 For a polymorphic example (lists) we have: type instance Point [a] = a Now Functor becomes: class SimpleFunctor f where fmap ∷ (Point f → Point f) → (f → f) However, this doesn't allow for the existence of functions with the type (a → b). I need to introduce another type into the class: class Functor f g where fmap ∷ (Point f → Point g) → (f → g) But having two types isn't very nice (for one thing we can't introduce a fundep because for lists as it fails one of the coverage conditions), so introduce another type family to represent types which can be produced by giving a free variable: type Subst f a ∷ ★ type Subst [a] b = [b] type Subst ByteString b = ByteString class Functor f where fmap ∷ (Point f → Point (Subst f a)) → (f → Subst f a) I'm not sure how much of a hack this is, or if there is a better way. It seems to be OK... Now I want to implement Applicative. It would make sense to have ‘return’ be split out into a separate class, because this can be restricted in a similar way to Functor: class Pointed f where return ∷ Point f → f instance Pointed [a] where return x = [x] instance Pointed ByteString where return = BS.singleton Now, I want to be able to restrict Applicative to things which have [Pointed f, and forall a b. Point f ~ (a → b)]. At the moment I can't figure this out because I believe it would require something like the ‘quantified contexts’ proposal: class (Pointed f, ∀ a b. Point f ~ (a → b)) ⇒ Applicative f where ... I could have something like: class (Pointed f, Point f ~ (a → b)) ⇒ Applicative f a b where apply ∷ f → Subst f a → Subst f b This is still not very nice, because it requires two more type variables in the class, and the non-type-families version is far more straightforward... in fact, it makes sense for the Applicative class to have a polymorphic type because it must be able to have ‘return’ applied to arbitrary functions (remember [fmap f xs ≡ return f `apply` xs]). So back to: class Applicative f where apply ∷ f (a → b) → f a → f b But then ‘return’ cannot be added via a superclass restriction to Pointed! I seem to have painted myself into a corner. Does anyone see a better way to go about this? Thanks, - George ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe