Duncan Coutts wrote:

On Tue, 2007-12-11 at 07:07 -0800, Stefan O'Rear wrote:

...

This is almost exactly the http://haskell.org/haskellwiki/Class_system_extension_proposal; that page has some discussion of implementation issues.

Oh yes, so it is. Did this proposal get discussed on any mailing list? I'd like to see what people thought. Was there any conclusion about feasibility?

Ross proposed this on the libraries list in 2005: http://www.haskell.org//pipermail/libraries/2005-March/003494.html and I brought it up for Haskell': http://www.haskell.org//pipermail/haskell-prime/2006-April/001344.html see also this: http://www.haskell.org//pipermail/haskell-prime/2006-August/001582.html Unfortunately the Haskell' wiki doesn't have a good summary of the issues; it should. I'll add these links at least. Cheers, Simon

On Tue, 2007-12-11 at 16:38 +0000, Ross Paterson wrote:

On Tue, Dec 11, 2007 at 04:26:52PM +0000, Simon Marlow wrote:

...

Duncan Coutts wrote:

...

On Tue, 2007-12-11 at 07:07 -0800, Stefan O'Rear wrote:

...

This is almost exactly the http://haskell.org/haskellwiki/Class_system_extension_proposal; that page has some discussion of implementation issues.

Oh yes, so it is. Did this proposal get discussed on any mailing list? I'd like to see what people thought. Was there any conclusion about feasibility?

Ross proposed this on the libraries list in 2005:

http://www.haskell.org//pipermail/libraries/2005-March/003494.html

and again in 2003:

http://www.haskell.org/pipermail/haskell-cafe/2003-July/004654.html

Ross, you need to shout louder! :-) If it really would work ok we should get it fully specified and implemented so we can fix the most obvious class hierarchy problems in a nice backwards compatible way. Things are only supposed to be candidates for Haskell' if they're already implemented. So how about the objection that two sub classes could try and define conflicting defaults for a superclass method? David Menendez had the example of Monad and CoMonad defining Functor's fmap. Can that easily be rejected? I suppose it gives rise to duplicate instance declarations so it'd be an error in the same way that defining clashing instances in two different modules and importing both into a third module. Another error case would be: module A where data Foo module B where instance Functor Foo module C where instance Monad Foo module D import Bar import Baz Now we get slashing instances for Functor, since both Bar and Baz export Functor instances for Foo. Since the instance for Functor Foo was not visible in module C, so we get the default instance defined in C. So the one slightly surprising thing about this suggestion is that we get an instance defined or not depending on whether there is already an instance in scope. In the Functor, Applicative, Monad case I don't see that causing a problem in practise but is it worse more generally? Duncan

Another suggestion, maybe completely off the wall, would be to do something with stand-alone deriving syntax? So instead of "instance Functor T" one might write "deriving Functor for T" ? This might make it more clear that default methods were being brought into play. With this syntax, it would seem appropriate to me that any case of overlap would produce an error (modulo, perhaps, some funny new ghc flag such as -fallow-overlapping-derivations). --s. instance Monad T On Dec 11, 2007, at 12:30 PM, Simon Peyton-Jones wrote:

| If it really would work ok we should get it fully specified and | implemented so we can fix the most obvious class hierarchy problems in a | nice backwards compatible way. Things are only supposed to be candidates | for Haskell' if they're already implemented.

Getting it fully specified is the first thing.

Personally I am not keen about

a) coupling it to explicit import/export (independently-desirable though such a change might be)

b) having instance declarations silently spring into existence

Concerning (b) here's a suggestion. As now, require that every instance requires an instance declaration. So, in the main example of http://haskell.org/haskellwiki/Class_system_extension_proposal, for a new data type T you'd write instance Monad T where return = ... (>>=) = ...

instance Functor T instance Applicative T

The instance declaration for (Functor T) works just as usual (no explicit method, so use the default method) except for one thing: how the default method is found. The change is this: Given "instance C T where ...", for any method 'm' not defined by "...": for every class D of which C is a superclass where there is an instance for (D T) see if the instance gives a binding for 'm' If this search finds exactly one binding, use it, otherwise behave as now

This formulation reduces the problem to a more manageable one: a search for the default method.

I'm not sure what is supposed to happen if the instance is for something more complicated (T a, say, or multi-parameter type class) but I bet you could work it out.

All these instances would need to be in the same module: - you can't define Functor T without Monad T, because you want to pick up the monad-specific default method - you can't define Monad T without Functor T, because the latter is a superclass of the former

It still sounds a bit complicated.

Simon _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

Simon Peyton-Jones wrote:

Given "instance C T where ...", for any method 'm' not defined by "...": for every class D of which C is a superclass where there is an instance for (D T) see if the instance gives a binding for 'm' If this search finds exactly one binding, use it, otherwise behave as now

A better rule would be: If this search finds exactly one binding that is minimal in the partial ordering defined by the superclass hierarchy, use it, otherwise behave as now. Would that be much harder to implement? -Yitz

I had it pretty well worked out for single parameter type classes, but I couldn't see any nice extension to multiple parameters. On Dec 11, 2007 5:30 PM, Simon Peyton-Jones wrote:

| If it really would work ok we should get it fully specified and | implemented so we can fix the most obvious class hierarchy problems in a | nice backwards compatible way. Things are only supposed to be candidates | for Haskell' if they're already implemented.

Getting it fully specified is the first thing.

Personally I am not keen about

a) coupling it to explicit import/export (independently-desirable though such a change might be)

b) having instance declarations silently spring into existence

Concerning (b) here's a suggestion. As now, require that every instance requires an instance declaration. So, in the main example of http://haskell.org/haskellwiki/Class_system_extension_proposal, for a new data type T you'd write instance Monad T where return = ... (>>=) = ...

instance Functor T instance Applicative T

The instance declaration for (Functor T) works just as usual (no explicit method, so use the default method) except for one thing: how the default method is found. The change is this: Given "instance C T where ...", for any method 'm' not defined by "...": for every class D of which C is a superclass where there is an instance for (D T) see if the instance gives a binding for 'm' If this search finds exactly one binding, use it, otherwise behave as now

This formulation reduces the problem to a more manageable one: a search for the default method.

I'm not sure what is supposed to happen if the instance is for something more complicated (T a, say, or multi-parameter type class) but I bet you could work it out.

All these instances would need to be in the same module: - you can't define Functor T without Monad T, because you want to pick up the monad-specific default method - you can't define Monad T without Functor T, because the latter is a superclass of the former

It still sounds a bit complicated.

Simon _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

David Menendez wrote:

On Dec 11, 2007 9:20 AM, Duncan Coutts mailto:duncan.coutts@worc.ox.ac.uk> wrote:

So my suggestion is that we let classes declare default implementations of methods from super-classes.

Does this proposal have any unintended consequences? I'm not sure. Please discuss :-)

It creates ambiguity if two classes declare defaults for a common superclass.

My standard example involves Functor, Monad, and Comonad. Both Monad and Comonad could provide a default implementation for fmap. But let's say I have a type which is both a Monad and a Comonad: which default implementation gets used?

I'm disappointed to see this objection isn't listed on the wiki.

Doesn't sound like a very big problem. That would just be a compile time error ("More than one default for fmap possible for Foo, please reslve ambiguity"). Jules

On Dec 11, 2007 3:19 PM, David Menendez wrote:

On Dec 11, 2007 9:20 AM, Duncan Coutts wrote:

...

So my suggestion is that we let classes declare default implementations of methods from super-classes.

...

Does this proposal have any unintended consequences? I'm not sure. Please discuss :-)

It creates ambiguity if two classes declare defaults for a common superclass.

My standard example involves Functor, Monad, and Comonad. Both Monad and Comonad could provide a default implementation for fmap. But let's say I have a type which is both a Monad and a Comonad: which default implementation gets used?

Isn't a type which is both a Monad and a Comonad just Identity? (I'm actually not sure, I'm just conjecting) Luke

apfelmus wrote:

Luke Palmer wrote:

...

Isn't a type which is both a Monad and a Comonad just Identity?

(I'm actually not sure, I'm just conjecting)

Good idea, but it's not the case.

data L a = One a | Cons a (L a) -- non-empty list

Maybe I can entice you to elaborate slightly. From http://www.eyrie.org/~zednenem/2004/hsce/Control.Functor.html and Control.Comonad.html there is ---------------------------------------------------------- newtype O f g a -- Functor composition: f `O` g instance (Functor f, Functor g) => Functor (O f g) where ... instance Adjunction f g => Monad (O g f) where ... instance Adjunction f g => Comonad (O f g) where ... -- I assume Haskell can infer Functor (O g f) from Monad (O g f), which -- is why that is missing here? class (Functor f, Functor g) => Adjunction f g | f -> g, g -> f where leftAdjunct :: (f a -> b) -> a -> g b rightAdjunct :: (a -> g b) -> f a -> b ---------------------------------------------------------- Functors are associative but not generally commutative. Apparently a Monad is also a Comonad if there exist left (f) and right (g) adjuncts that commute. [and only if also??? Is there a contrary example of a Monad/Comonad for which no such f and g exist?] In the case of

data L a = One a | Cons a (L a) -- non-empty list

what are the appropriate definitions of leftAdjunct and rightAdjunct? Are they Monad.return and Comonad.extract respectively? That seems to unify a and b unnecessarily. Do they wrap bind and cobind? Are they of any practical utility? My category theory study stopped somewhere between Functor and Adjunction, but is there any deep magic you can describe here in a paragraph or two? I feel like I will never get Monad and Comonad until I understand Adjunction. Dan

On Dec 14, 2007 5:14 AM, Jules Bean wrote:

There are two standard ways to decompose a monad into two adjoint functors: the Kleisli decomposition and the Eilenberg-Moore decomposition.

However, neither of these categories is a subcategory of Hask in an obvious way, so I don't immediately see how to write "f" and "g" as haskell functors.

Maybe someone else can show the way :)

One possibility is to extend Haskell's Functor class. We can define a class of (some) categories whose objects are Haskell types:

class Category mor where id :: mor a a (.) :: mor b c -> mor a b -> mor a c

The instance for (->) should be obvious. We can also define an instance for Kleisli operations:

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b } instance (Monad m) => Category (Kleisli m) -- omitted

Next, a class for (some) functors between these categories:

class (Category morS, Category morT) => Functor f morS morT where fmap :: morS a b -> morT (f a) (f b)

Unlike the usual Haskell Functor class, this requires us to distinguish the functor itself from the type constructor involved in the functor. Here's an instance converting Kleisli operations to functions.

instance Monad m => Functor m (Kleisli m) (->) where -- fmap :: Kleisli m a b -> (m a -> m b) fmap f = (>>= runKleisli f)

Going the other way is tricker, because our Functor interface requires a type constructor. We'll use Id.

newtype Id a = Id { unId :: a }

instance Monad m => Functor Id (->) (Kleisli m) where -- fmap :: (a -> b) -> Kleisli m (Id a) (Id b) fmap f = Kleisli (return . Id . f . unId)

Finally, adjunctions between functors:

class (Functor f morS morT, Functor g morT morS) => Adjunction f g morS morT | f g morS -> morT, f g morT -> morS where leftAdj :: morT (f a) b -> morS a (g b) rightAdj :: morS a (g b) -> morT (f a) b

The functional dependency isn't really justified. It's there to eliminate ambiguity in the later code. The two functors above are adjoint:

instance (Monad m) => Adjunction Id m (->) (Kleisli m) where -- leftAdj :: Kleisli (Id a) b -> (a -> m b) leftAdj f = runKleisli f . Id

-- rightAdj :: (a -> m b) -> Kleisli (Id a) b rightAdj f = Kleisli (f . unId)

So, given two adjoint functors, we have a monad and a comonad. Note, however, that these aren't necessarily the same as the Haskell classes Monad and Comonad. Here are the monad operations:

unit :: (Adjunction f g morS morT) => morS a (g(f a)) unit = leftAdj id

extend :: (Adjunction f g morS morT) => morS a (g(f b)) -> morS (g(f a)) (g(f b)) extend f = fmap (rightAdj f)

The monad's type constructor is the composition of g and f. Extend corresponds to (>>=) with the arguments reversed. In our running example, unit and extend have these types: unit :: Monad m => a -> m (Id a) extend :: Monad m => (a -> m (Id b)) -> m (Id a) -> m (Id b) This corresponds to our original monad, only with the extra Id. Here are the comonad operations:

counit :: (Adjunction f g morS morT) => morT (f(g a)) a counit = rightAdj id

coextend :: (Adjunction f g morS morT) => morT (f(g a)) b -> morT (f(g a)) (f(g b)) coextend f = fmap (leftAdj f)

In our running example, counit and coextend have these types: counit :: Monad m => Kleisli m (Id (m a)) a coextend :: Monad m => Kleisli m (Id (m a)) b -> Kleisli m (Id (m a)) (Id (m b)) Thus, m is effectively a comonad in its Kleisli category. We can tell a similar story with Comonads and CoKleisli operations, eventually reaching an adjunction like this:

instance (Comonad w) => Adjunction w Id (CoKleisli w) (->) -- omitted

-- Dave Menendez http://www.eyrie.org/~zednenem/

On Sun, 2007-12-16 at 13:49 +0100, apfelmus wrote:

Dan Weston wrote:

...

newtype O f g a = O (f (g a)) -- Functor composition: f `O` g

instance (Functor f, Functor g) => Functor (O f g) where ... instance Adjunction f g => Monad (O g f) where ... instance Adjunction f g => Comonad (O f g) where ...

class (Functor f, Functor g) => Adjunction f g | f -> g, g -> f where leftAdjunct :: (f a -> b) -> a -> g b rightAdjunct :: (a -> g b) -> f a -> b ----------------------------------------------------------

Functors are associative but not generally commutative. Apparently a Monad is also a Comonad if there exist left (f) and right (g) adjuncts that commute.

Yes, but that's only sufficient, not necessary.

Jules and David already pointed out that while every monad comes from an adjunction, this adjunction usually involves categories different from Hask. So, there are probably no adjoint functors f and g in Hask such that

[] ~= g `O` f

or

...

...

data L a = One a | Cons a (L a) -- non-empty list

L ~= g `O` f

(proof?) Yet, both are monads and the latter is even a comonad.

Moreover, f and g can only commute if they have the same source and target category (Hask in our case). And even when they don't commute, the resulting monad could still be a comonad, too.

...

My category theory study stopped somewhere between Functor and Adjunction, but is there any deep magic you can describe here in a paragraph or two? I feel like I will never get Monad and Comonad until I understand Adjunction.

Alas, I wish I could, but I have virtually no clue about adjoint functors myself :)

Learn about representability. Representability is the core of category theory. (Though, of course, it is closely related to adjunctions.)

I only know the classic example that conjunction and implication

f a = (a,S) g b = S -> b

are adjoint

(a,S) -> b = a -> (S -> b)

which is just well-known currying. We get the state monad

(g `O` f) a = S -> (S,a)

and the stream comonad

(f `O` f) a = (S, S -> a)

out of that.

There is another very closely related adjunction that is less often mentioned. ((-)->C)^op -| (-)->C or a -> b -> C ~ b -> a -> C This gives rise to the monad, M a = (a -> C) -> C this is also exactly the comonad it gives rise to (in the op category which ends up being the above monad in the "normal" category).

On Dec 17, 2007 4:34 AM, Yitzchak Gale wrote:

Derek Elkins wrote:

...

There is another very closely related adjunction that is less often mentioned.

((-)->C)^op -| (-)->C or a -> b -> C ~ b -> a -> C

This gives rise to the monad, M a = (a -> C) -> C this is also exactly the comonad it gives rise to (in the op category which ends up being the above monad in the "normal" category).

That looks very like the type of mfix. Is this related to MonadFix?

I think that's the continuation monad. -- Dave Menendez http://www.eyrie.org/~zednenem/