Why Kleisli composition is not in the Monad signature?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
33 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Why Kleisli composition is not in the Monad signature?

damodar kulkarni
Hi,
The Monad class makes us define bind (>>=) and unit (return) for our monads.

Why the Kleisli composition (>=>) or (<=<) is not made a part of Monad class instead of bind (>>=)?

Is there any historical reason behind this?

The bind (>>=) is not as elegant as (>=>), at least as I find it.

Am I missing something?


- Damodar


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Ertugrul Söylemez
damodar kulkarni <[hidden email]> wrote:

> The Monad class makes us define bind (>>=) and unit (return) for our
> monads.
>
> Why the Kleisli composition (>=>) or (<=<) is not made a part of Monad
> class instead of bind (>>=)?
>
> Is there any historical reason behind this?
>
> The bind (>>=) is not as elegant as (>=>), at least as I find it.
>
> Am I missing something?
Try to express

    do x <- getLine
       y <- getLine
       print (x, y)

using only Kleisli composition (without cheating).  Through cheating
(doing non-categorical stuff) it's possible to implement (>>=) in terms
of (<=<), but as said that's basically breaking the abstraction.


Greets,
Ertugrul

--
Not to be or to be and (not to be or to be and (not to be or to be and
(not to be or to be and ... that is the list monad.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Benjamin Franksen
Ertugrul Söylemez wrote:

> damodar kulkarni <[hidden email]> wrote:
>> The Monad class makes us define bind (>>=) and unit (return) for our
>> monads.
>>
>> Why the Kleisli composition (>=>) or (<=<) is not made a part of Monad
>> class instead of bind (>>=)?
>>
>> Is there any historical reason behind this?
>>
>> The bind (>>=) is not as elegant as (>=>), at least as I find it.
>>
>> Am I missing something?
>
> Try to express
>
>     do x <- getLine
>        y <- getLine
>        print (x, y)
>
> using only Kleisli composition (without cheating).  Through cheating
> (doing non-categorical stuff) it's possible to implement (>>=) in terms
> of (<=<), but as said that's basically breaking the abstraction.

What do you mean with "cheating" / "doing non-categorical stuff"?

m >>= f = (const m >=> f) ()

f >=> g = \x -> f x >>= g

How does the first definition "break the abstraction" while the second does
not?

Cheers
--
Ben Franksen
()  ascii ribbon campaign - against html e-mail
/\  www.asciiribbon.org   - against proprietary attachments



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

AUGER Cédric
Le Mon, 15 Oct 2012 15:12:28 +0200,
Benjamin Franksen <[hidden email]> a écrit :

> Ertugrul Söylemez wrote:
> > damodar kulkarni <[hidden email]> wrote:
> >> The Monad class makes us define bind (>>=) and unit (return) for
> >> our monads.
> >>
> >> Why the Kleisli composition (>=>) or (<=<) is not made a part of
> >> Monad class instead of bind (>>=)?
> >>
> >> Is there any historical reason behind this?
> >>
> >> The bind (>>=) is not as elegant as (>=>), at least as I find it.
> >>
> >> Am I missing something?
> >
> > Try to express
> >
> >     do x <- getLine
> >        y <- getLine
> >        print (x, y)
> >
> > using only Kleisli composition (without cheating).  Through cheating
> > (doing non-categorical stuff) it's possible to implement (>>=) in
> > terms of (<=<), but as said that's basically breaking the
> > abstraction.
>
> What do you mean with "cheating" / "doing non-categorical stuff"?
>
> m >>= f = (const m >=> f) ()
>
> f >=> g = \x -> f x >>= g
>
> How does the first definition "break the abstraction" while the
> second does not?
>
> Cheers

It does not really break the categorical stuff, but I think that bind
has better its place rather than being replaced by the Kleisli arrow.

I am quite new to Haskell, so I do not know its history, but for the
categorical point of view, bind would better have received the
signature "∀ α β, (α→Mβ) → (Mα→Mβ)", expressing 'M' as a functor from
Kleisli(M) category to the Hask category, sending each morphism "α→Mβ"
from "α" to "β" in Kleisli category, to a morphism "Mα→Mβ" in the Hask
category.

As you may have already read, the usual point of view of monads in
mathematic is not with (return, bind) but (return, join) [return is
usually noted ε and is called the unit, and join is usually noted μ and
called multiplication]. In this context, "return : ∀ α, (α→Mα)" and
"join : ∀ α, (MMα→Mα)" are called natural transformations and must
respect some additionnal rules (called monad laws).

If you do not know what a natural transformation is, this is some
definition (in a Haskell context).
Consider two functors S and T, "f: ∀ α, (Sα→Tα)" is a natural
transformation from S to T, if for any types "t1" and "t2" and any
pure function "g: t1→t2", we following egality holds: "f.(fmap
g)=(fmap g).f"

For instance when S is the identity functor, and T is the functor
associated to the monad, you must have "return.(fmap g) = (fmap
g).return".

Now, I do not really know why "bind" is used rather than "join". I
guess that join is not very common in practice, so we would have to
write "join (fmap f) x" each time we would like to write "bind x f".
Another reason may be history, and the last one would be efficiency (I
guess that "bind" correspond better to machine models than "join"). In
any case, "join" has a simpler type than "bind" (only one type
variable), which in turn is simpler than your Kleisli arrow (you need 3
type variables).

It would be rather awful to expand each of your Kleisli arrows with
"const" as you said. Of course you wouldn't have to do it, but for
efficient compilation, as I guess that in most cases "bind" can be
rather efficiently implemented, while "kleisli" would not, I fear some
minor performance issues with "bind" defined in terms of "kleisli".
Once again I am not a Haskell expert.

For the small story, the concept of Monad is strongly linked to the one
of Adjunction (although adjunctions in Haskell are probably not very
commonly used and easy to define). The composition of a left and a
right adjunction gives a Monad, and given a Monad, we can build an
adjunction. One of the adjunction you can build is using … the Kleisli
category (see Wikipedia).

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Jake McArthur
In reply to this post by Ertugrul Söylemez
On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez <[hidden email]> wrote:
> Try to express
>
>     do x <- getLine
>        y <- getLine
>        print (x, y)
>
> using only Kleisli composition (without cheating).

In my opinion, this is not as nice as the do-notation version, but at
least it's compositional:

    print <=< (<$> getLine) . (,) <=< const getLine $ ()

I do think there is value in favoring Kleisli composition for a lot of
code. Unfortunately, however, it doesn't tend to work out so nicely
for IO.

- Jake

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Jake McArthur
On Mon, Oct 15, 2012 at 11:33 AM, Jake McArthur <[hidden email]> wrote:
> On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez <[hidden email]> wrote:
>> Try to express
>>
>>     do x <- getLine
>>        y <- getLine
>>        print (x, y)
>>
>> using only Kleisli composition (without cheating).

My previous answer didn't do the Kleisli style much justice. It could
look a bit nicer with more Arrow-style combinators:

    f &=& g = runKleisli $ Kleisli f &&& Kleisli g

    print <=< const getLine &=& const getLine $ ()

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

damodar kulkarni
@Jake

In my opinion, this is not as nice as the do-notation version, but at
least it's compositional:

That's an important point you have made, as Haskellers value code composition so much.
If code composition is the "holy grail", why not encourage the monadic code, too, to be compositional? Nicety can wait; some syntax sugar might take care of it.

And as you have pointed out, arrows make a superior choice in this regard, but they are rather newer to monads.

@ AUGER Cédric

It would be rather awful to expand each of your Kleisli arrows with
"const" as you said.

The const is required in this example because we are dealing with getLine (as getLine can return different strings at different times without taking any argument). Again, some syntactic sugar would have taken care of this "const" thing.

Correct me if I am wrong. 

and thanks for responses.

Damodar

On Mon, Oct 15, 2012 at 9:09 PM, Jake McArthur <[hidden email]> wrote:
On Mon, Oct 15, 2012 at 11:33 AM, Jake McArthur <[hidden email]> wrote:
> On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez <[hidden email]> wrote:
>> Try to express
>>
>>     do x <- getLine
>>        y <- getLine
>>        print (x, y)
>>
>> using only Kleisli composition (without cheating).

My previous answer didn't do the Kleisli style much justice. It could
look a bit nicer with more Arrow-style combinators:

    f &=& g = runKleisli $ Kleisli f &&& Kleisli g

    print <=< const getLine &=& const getLine $ ()

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe





_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Dan Doel
On Mon, Oct 15, 2012 at 10:05 PM, damodar kulkarni
<[hidden email]> wrote:

> @Jake
>
>
>> In my opinion, this is not as nice as the do-notation version, but at
>> least it's compositional:
>
>
> That's an important point you have made, as Haskellers value code
> composition so much.
> If code composition is the "holy grail", why not encourage the monadic code,
> too, to be compositional? Nicety can wait; some syntax sugar might take care
> of it.
>
> And as you have pointed out, arrows make a superior choice in this regard,
> but they are rather newer to monads.

I'm uncertain where this, "compositional means written as the
composition of functions," thing started. But it is not what I, and
I'm sure any others mean by the term, "compositional."

For instance, one of the key properties of denotational semantics is
that they are compositional. But this does not mean that the semantics
is written as the composition of functions. Perhaps it could be, but
that is a rather superficial criterion. What it means is that the
semantics of compound expressions are merely functions of the
semantics of the constituent pieces, so one can stick together well
understood pieces to get well understood wholes, and the whole does
not have to be analyzed as an entire unit.

Now, one can give almost anything a compositional semantics in this
sense, by denoting things by pieces that pass context along. And this
is a reason to avoid effects and whatnot. But this is true whether one
writes things as a pipeline of functions or as some other sort of
expression. Context may be threaded through a series of expressions,
or through a series of composed functions. Choosing either way of
writing makes no difference.

So I don't really care whether people write their code involving
monads as the composition of Kleisli arrows, except for which makes
the code look nicer. And the arrow option does not always do so,
especially when one must artificially extend things of type 'M a' into
constant functions. Kleisli arrows aren't the end all and be all of
monads (if you read books on the math end, the Eilenberg-Moore
category tends to be emphasized far more, and the Kleisli category
might not even be presented in the same way as it typically is amongst
Haskellers).

As for why (>>=) is a good primitive.... For one, it works very nicely
for writing statement sequences without any sugar (for when you want
to do that):

    getLine >>= \x ->
    getLine >>= \y ->
    print (x, y)

For two, it corresponds to the nice operation of substitution of an
expression for a variable (which is a large part of what monads are
actually about in category theory, but doesn't get a lot of play in
Haskell monad tutorials).

For three, I can't for the life of me think of how anyone would write
(>=>) as a primitive operation _except_ for writing (>>=) and then '(f
>=> g) x = f x >>= g'. The function cannot be inspected to get the
result except by applying it.  I suppose one _can_ write (>=>)
directly. For instance:

    data Free f a = Pure a | Roll (f (Free f a))

    (g >=> h) x = case g x of
      Pure b -> h b
      Roll f -> Roll $ fmap (id >=> h) f

But the (id >=> h) is there because we want to put (>>= h) and don't
have it. The g is sort of an illusion. We use it to get an initial
value, but all our recursive calls use g = id, so we're subsequently
defining (>>=) in disguise. (And, amusingly, we're even using
polymorphic recursion, so if this isn't in a class, or given an
explicit type signature, inference will silently get the wrong
answer.)

So, there are good reasons for making (>>=) primitive, and not really
any (that I can see) for making (>=>) more than a derived function.
I'd be down with putting join in the class, but that tends to not be
terribly important for most cases, either.

-- Dan

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Jake McArthur
On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <[hidden email]> wrote:
> I'm uncertain where this, "compositional means written as the
> composition of functions," thing started. But it is not what I, and
> I'm sure any others mean by the term, "compositional."

You're right. It's a rather recent, as far as I can tell, overloading
of the word that I inadvertently picked up. The meaning of this
overloading, at least as I understand and intended it, is that it
forms a category. I will try to avoid this use of the word in the
future.

> For three, I can't for the life of me think of how anyone would write
> (>=>) as a primitive operation _except_ for writing (>>=) and then '(f
>>=> g) x = f x >>= g'. The function cannot be inspected to get the
> result except by applying it.

This is a good point.

> I'd be down with putting join in the class, but that tends to not be
> terribly important for most cases, either.

Join is not the most important, but I do think it's often easier to
define than bind. I often find myself implementing bind by explicitly
using join.

- Jake

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

AUGER Cédric
In reply to this post by damodar kulkarni
Le Tue, 16 Oct 2012 07:35:34 +0530,
damodar kulkarni <[hidden email]> a écrit :

> @Jake
>
> In my opinion, this is not as nice as the do-notation version, but at
> > least it's compositional:
>
>
> That's an important point you have made, as Haskellers value code
> composition so much.
> If code composition is the "holy grail", why not encourage the monadic
> code, too, to be compositional? Nicety can wait; some syntax sugar
> might take care of it.
>
> And as you have pointed out, arrows make a superior choice in this
> regard, but they are rather newer to monads.
>
> @ AUGER Cédric
>
>  It would be rather awful to expand each of your Kleisli arrows with
> >
> "const" as you said.
> >
>
> The const is required in this example because we are dealing with
> getLine (as getLine can return different strings at different times
> without taking any argument). Again, some syntactic sugar would have
> taken care of this "const" thing.
>
> Correct me if I am wrong.

We were not dealing with getLine in particular. The point was about
knowing if >>= could be defined in terms of >=>. The const is necessary
for the general case. So I think that an implicit question was why
wouldn't we have:

class Monad m where
  return :: a -> m a
  kleisli :: (a -> m b) -> (b -> m c) -> (a -> m c)
  bind = \ x f -> ((const x) >=> f) ()
  join = id>=>id :: (m (m a) -> m a)

(Sorry, I do not remember the correct Haskell syntax, I am a beginner,
but I do not have touched the language for some time…)

That is "bind" would have a default construction (like "join" has got
its one now).

The definition of "join" would become rather nice this way ^^

Not redefining the "join" and "bind" function would lead to expand them
with "\ x f -> (const x) >=> f" and "id>=>id", that is what I meant, and
found it awful for "bind". Of course I do not say that Kleisli is a bad
idea. I even think it is better to use it when you want composition, or
you want to do the initial given example (readString >=> putString, or
something like that, I do not really remember). But I do not think
defining Monads from Kleisli (or T-algebras, for the other adjunction
construction) would be very nice. On the other hand, I guess that the
class Monad could contain the definition of Kleisli arrows. But as we
have instances ArrowApply a => Monad (ArrowMonad a) and Monad m =>
Arrow (Kleisli m), I do not think we lack some functionnality.

>
> and thanks for responses.
>
> Damodar
>
> On Mon, Oct 15, 2012 at 9:09 PM, Jake McArthur
> <[hidden email]>wrote:
>
> > On Mon, Oct 15, 2012 at 11:33 AM, Jake McArthur
> > <[hidden email]> wrote:
> > > On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez <[hidden email]>
> > > wrote:
> > >> Try to express
> > >>
> > >>     do x <- getLine
> > >>        y <- getLine
> > >>        print (x, y)
> > >>
> > >> using only Kleisli composition (without cheating).
> >
> > My previous answer didn't do the Kleisli style much justice. It
> > could look a bit nicer with more Arrow-style combinators:
> >
> >     f &=& g = runKleisli $ Kleisli f &&& Kleisli g
> >
> >     print <=< const getLine &=& const getLine $ ()
> >
> > _______________________________________________
> > Haskell-Cafe mailing list
> > [hidden email]
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

AUGER Cédric
In reply to this post by Jake McArthur
Le Tue, 16 Oct 2012 09:51:29 -0400,
Jake McArthur <[hidden email]> a écrit :

> On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <[hidden email]> wrote:
> > I'd be down with putting join in the class, but that tends to not be
> > terribly important for most cases, either.
>
> Join is not the most important, but I do think it's often easier to
> define than bind. I often find myself implementing bind by explicitly
> using join.

join IS the most important from the categorical point of view.
In a way it is natural to define 'bind' from 'join', but in Haskell, it
is not always possible (see the Monad/Functor problem).

As I said, from the mathematical point of view, join (often noted μ in
category theory) is the (natural) transformation which with return (η
that I may have erroneously written ε in some previous mail) defines a
monad (and requires some additionnal law). As often some points it out,
Haskellers are not very right in their definition of Monad, not because
of the bind vs join (in fact in a Monad either of them can be defined
from the other one), but because of the functor status of a Monad. A
monad, should always be a functor (at least to fit its mathematical
definition). And this problem with the functor has probably lead to the
use of "bind" (which is polymorphic in two type variables) rather than
"join" (which has only one type variable, and thus is simpler).
The problem, is that when 'm' is a Haskell Monad which does not belong
to the Functor class, we cannot define 'bind' in general from 'join'.

That is in the context where you have:

return:∀ a. a → (m a)
join:∀ a. (m (m a)) → (m a)
x:m a
f:a → (m b)

you cannot define some term of type 'm b', since you would need to use
at the end, either 'f' (and you would require to produce a 'a' which
would be impossible), or 'return' (and you would need to produce a 'b',
which is impossible), or 'join' (and you would need to produce a 'm (m
b)', and recursively for that you cannot use return which would make
you go back to define a 'm b' term)

For that, you need the 'fmap' operation of the functor.

return:∀ a. a → (m a)
join:∀ a. (m (m a)) → (m a)
fmap:∀ a b. (a→b) → ((m a)→(m b))
x:m a
f:a → (m b)

in this context defining a term of type 'm b' is feasible (join (fmap f
x)), so that you can express "bind = \ x f -> join (fmap f x)".

To sum up, mathematical monads are defined from 'return' and 'join' as
a mathematical monad is always a functor (so 'fmap' is defined, and
'bind', which is more complex than 'join' can be defined from 'join'
and 'fmap'). Haskell does not use a very good definition for their
monads, as they may not be instance of the Functor class (although
most of them can easily be defined as such), and without this 'fmap',
'join' and 'return' would be pretty useless, as you wouldn't be able
to move from a type 'm a' to a type 'm b'.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Daniel Peebles
Although I agree that Functor should be a superclass of Monad, the two methods of the Monad typeclass _are_ sufficient to make any instance into a Functor in a mechanical/automatic way. The language may not know it, but return/bind is equivalent in power to fmap/return/join. Apart from bind being easier to use for the things we typically do with monads in programs, using bind is actually more "succinct" in that it doesn't require three primitive operations.

I'm not saying bind is a better primitive than join/fmap, but "mathematicians do it this way, therefore it's better" doesn't seem like a particularly convincing argument either. And for a more philosophical question, is something not a functor just because we don't have a Functor instance for it? If we agree that the Monad class (with no Functor superclass) does implicitly form a Functor with liftM, then I don't really see what the problem is, apart from the inconvenience of not being able to use fmap.

On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric <[hidden email]> wrote:
Le Tue, 16 Oct 2012 09:51:29 -0400,
Jake McArthur <[hidden email]> a écrit :

> On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <[hidden email]> wrote:
> > I'd be down with putting join in the class, but that tends to not be
> > terribly important for most cases, either.
>
> Join is not the most important, but I do think it's often easier to
> define than bind. I often find myself implementing bind by explicitly
> using join.

join IS the most important from the categorical point of view.
In a way it is natural to define 'bind' from 'join', but in Haskell, it
is not always possible (see the Monad/Functor problem).

As I said, from the mathematical point of view, join (often noted μ in
category theory) is the (natural) transformation which with return (η
that I may have erroneously written ε in some previous mail) defines a
monad (and requires some additionnal law). As often some points it out,
Haskellers are not very right in their definition of Monad, not because
of the bind vs join (in fact in a Monad either of them can be defined
from the other one), but because of the functor status of a Monad. A
monad, should always be a functor (at least to fit its mathematical
definition). And this problem with the functor has probably lead to the
use of "bind" (which is polymorphic in two type variables) rather than
"join" (which has only one type variable, and thus is simpler).
The problem, is that when 'm' is a Haskell Monad which does not belong
to the Functor class, we cannot define 'bind' in general from 'join'.

That is in the context where you have:

return:∀ a. a → (m a)
join:∀ a. (m (m a)) → (m a)
x:m a
f:a → (m b)

you cannot define some term of type 'm b', since you would need to use
at the end, either 'f' (and you would require to produce a 'a' which
would be impossible), or 'return' (and you would need to produce a 'b',
which is impossible), or 'join' (and you would need to produce a 'm (m
b)', and recursively for that you cannot use return which would make
you go back to define a 'm b' term)

For that, you need the 'fmap' operation of the functor.

return:∀ a. a → (m a)
join:∀ a. (m (m a)) → (m a)
fmap:∀ a b. (a→b) → ((m a)→(m b))
x:m a
f:a → (m b)

in this context defining a term of type 'm b' is feasible (join (fmap f
x)), so that you can express "bind = \ x f -> join (fmap f x)".

To sum up, mathematical monads are defined from 'return' and 'join' as
a mathematical monad is always a functor (so 'fmap' is defined, and
'bind', which is more complex than 'join' can be defined from 'join'
and 'fmap'). Haskell does not use a very good definition for their
monads, as they may not be instance of the Functor class (although
most of them can easily be defined as such), and without this 'fmap',
'join' and 'return' would be pretty useless, as you wouldn't be able
to move from a type 'm a' to a type 'm b'.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

AUGER Cédric
Le Tue, 16 Oct 2012 11:22:08 -0400,
Daniel Peebles <[hidden email]> a écrit :

> Although I agree that Functor should be a superclass of Monad, the two
> methods of the Monad typeclass _are_ sufficient to make any instance
> into a Functor in a mechanical/automatic way. The language may not
> know it, but return/bind is equivalent in power to fmap/return/join.
> Apart from bind being easier to use for the things we typically do
> with monads in programs, using bind is actually more "succinct" in
> that it doesn't require three primitive operations.

Succintness is not the point for me. For me, the point is
primitiveness/elementaryness. For instance bind has type
"m a → (a → m b) → m b"
[2 type variables, one functionnal argument, one 'scalar' argument]
whereas join has type
"m (m a) → m a"
[1 type variable, one 'scalar' argument]
and fmap has type
"(a → b) → (m a → m b)"
[2 type variables, one functionnal argument, one 'scalar' argument]

So here, 'join' is definitely more simple than 'bind'.
'fmap' and 'bind' are about same complexity (although we can consider
'fmap' slightly simpler as its functionnal argument has type 'a→b' and
not 'a→m b').

Having one single powerfull function is often overkill, and you will
probably require more simple functions which you will get by feeding
your big function with dummy ones (such as 'id' or 'const'), and you
may lose some efficiency. I do not know if you have studied the S, K, I
system of combinators. It is a system which is equivalent to λ-calculus
if I well remember. There are supercombinators system which requires
only one combinator, but almost nobody bother with them as they lead to
define too ugly terms.

>
> I'm not saying bind is a better primitive than join/fmap, but
> "mathematicians do it this way, therefore it's better" doesn't seem
> like a particularly convincing argument either.

I never said that, just that the "Monad" name is somehow not very
appropriate.

> And for a more
> philosophical question, is something not a functor just because we
> don't have a Functor instance for it? If we agree that the Monad
> class (with no Functor superclass) does implicitly form a Functor
> with liftM, then I don't really see what the problem is, apart from
> the inconvenience of not being able to use fmap.

I forgot about the liftM, so ok, the name is not that inapropriate,
although you have to wrap your stuff in the WrappedMonad…

>
> On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric <[hidden email]>
> wrote:
>
> > Le Tue, 16 Oct 2012 09:51:29 -0400,
> > Jake McArthur <[hidden email]> a écrit :
> >
> > > On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <[hidden email]>
> > > wrote:
> > > > I'd be down with putting join in the class, but that tends to
> > > > not be terribly important for most cases, either.
> > >
> > > Join is not the most important, but I do think it's often easier
> > > to define than bind. I often find myself implementing bind by
> > > explicitly using join.
> >
> > join IS the most important from the categorical point of view.
> > In a way it is natural to define 'bind' from 'join', but in
> > Haskell, it is not always possible (see the Monad/Functor problem).
> >
> > As I said, from the mathematical point of view, join (often noted μ
> > in category theory) is the (natural) transformation which with
> > return (η that I may have erroneously written ε in some previous
> > mail) defines a monad (and requires some additionnal law). As often
> > some points it out, Haskellers are not very right in their
> > definition of Monad, not because of the bind vs join (in fact in a
> > Monad either of them can be defined from the other one), but
> > because of the functor status of a Monad. A monad, should always be
> > a functor (at least to fit its mathematical definition). And this
> > problem with the functor has probably lead to the use of
> > "bind" (which is polymorphic in two type variables) rather than
> > "join" (which has only one type variable, and thus is simpler). The
> > problem, is that when 'm' is a Haskell Monad which does not belong
> > to the Functor class, we cannot define 'bind' in general from
> > 'join'.
> >
> > That is in the context where you have:
> >
> > return:∀ a. a → (m a)
> > join:∀ a. (m (m a)) → (m a)
> > x:m a
> > f:a → (m b)
> >
> > you cannot define some term of type 'm b', since you would need to
> > use at the end, either 'f' (and you would require to produce a 'a'
> > which would be impossible), or 'return' (and you would need to
> > produce a 'b', which is impossible), or 'join' (and you would need
> > to produce a 'm (m b)', and recursively for that you cannot use
> > return which would make you go back to define a 'm b' term)
> >
> > For that, you need the 'fmap' operation of the functor.
> >
> > return:∀ a. a → (m a)
> > join:∀ a. (m (m a)) → (m a)
> > fmap:∀ a b. (a→b) → ((m a)→(m b))
> > x:m a
> > f:a → (m b)
> >
> > in this context defining a term of type 'm b' is feasible (join
> > (fmap f x)), so that you can express "bind = \ x f -> join (fmap f
> > x)".
> >
> > To sum up, mathematical monads are defined from 'return' and 'join'
> > as a mathematical monad is always a functor (so 'fmap' is defined,
> > and 'bind', which is more complex than 'join' can be defined from
> > 'join' and 'fmap'). Haskell does not use a very good definition for
> > their monads, as they may not be instance of the Functor class
> > (although most of them can easily be defined as such), and without
> > this 'fmap', 'join' and 'return' would be pretty useless, as you
> > wouldn't be able to move from a type 'm a' to a type 'm b'.
> >
> > _______________________________________________
> > Haskell-Cafe mailing list
> > [hidden email]
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Dan Doel
In reply to this post by AUGER Cédric
On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric <[hidden email]> wrote:
> join IS the most important from the categorical point of view.
> In a way it is natural to define 'bind' from 'join', but in Haskell, it
> is not always possible (see the Monad/Functor problem).
>
> As I said, from the mathematical point of view, join (often noted μ in
> category theory) is the (natural) transformation which with return (η
> that I may have erroneously written ε in some previous mail) defines a
> monad (and requires some additionnal law).

This is the way it's typically presented. Can you demonstrate that it
is the most important presentation?

I'd urge caution in doing so, too. For instance, there is a paper,
Monads Need Not Be Endofunctors, that describes a generalization of
monads to monads relative to another functor. And there, bind is
necessarily primary, because join isn't even well typed. I don't think
it's written by mathematicians per se (rather, computer
scientists/type theorists). But mathematicians have their own
particular interests that affect the way they frame things, and that
doesn't mean those ways are better for everyone.

> As often some points it out,
> Haskellers are not very right in their definition of Monad, not because
> of the bind vs join (in fact in a Monad either of them can be defined
> from the other one), but because of the functor status of a Monad. A
> monad, should always be a functor (at least to fit its mathematical
> definition). And this problem with the functor has probably lead to the
> use of "bind" (which is polymorphic in two type variables) rather than
> "join" (which has only one type variable, and thus is simpler).
> The problem, is that when 'm' is a Haskell Monad which does not belong
> to the Functor class, we cannot define 'bind' in general from 'join'.

I don't think Functor being a superclass of Monad would make much
difference. For instance, Applicative is properly a subclass of
Functor, but we don't use the minimal definition that cannot reproduce
fmap on its own:

    class Functor f => LaxMonoidal f where
      unit :: f ()
      pair :: f a -> f b -> f (a, b)

Instead we use a formulation that subsumes fmap:

    fmap f x = pure f <*> x

Because those primitives are what we actually want to use, and it's
more efficient to implement those directly than to go through some set
of fully orthogonal combinators purely for the sake of mathematical
purity.

And this goes for Monad, as well. For most of the monads in Haskell,
the definition of join looks exactly like a definition of (>>= id),
and it's not very arduous to extend that to (>>= f). But if we do
define join, then we must recover (>>=) by traversing twice; once for
map and once for join. There are some examples where join can be
implemented more efficiently than bind, but I don't actually know of
any Haskell Monads for which this is the case.

And as I mentioned earlier, despite many Haskell folks often not
digging into monads as done by mathematicians much (and that's fine),
(>>=) does correspond to a nice operation: variable substitution. This
is true in category theory, when you talk about algebraic theories,
and it's true in Haskell when you start noticing that various little
languages are described by algebraic theories. But from this angle, I
see no reason why it's _better_ to split variable substitution into
two operations, first turning a tree into a tree of trees, and then
flattening.

It'd be nice if all Functor were a prerequisite for Monad, but even
then there are still reasons for making (>>=) a primitive.

-- Dan

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

AUGER Cédric
Le Tue, 16 Oct 2012 11:58:44 -0400,
Dan Doel <[hidden email]> a écrit :

> On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric <[hidden email]>
> wrote:
> > join IS the most important from the categorical point of view.
> > In a way it is natural to define 'bind' from 'join', but in
> > Haskell, it is not always possible (see the Monad/Functor problem).
> >
> > As I said, from the mathematical point of view, join (often noted μ
> > in category theory) is the (natural) transformation which with
> > return (η that I may have erroneously written ε in some previous
> > mail) defines a monad (and requires some additionnal law).
>
> This is the way it's typically presented. Can you demonstrate that it
> is the most important presentation?

What do you mean by demonstrate? If you do not want to fit the
mathematical presentation, then I have nothing to demonstrate, you have
your point of view, I have mine and they differ. Now, if you want to
fit the mathematical presentation, then a monad is an endofunctor with
two natural transformations (η=return and μ=join) satisfying some laws.
(when I write 'natural' I mean the mathematical definition of natural,
not its common definition as something on which we think immediately,
or something which is obvious).
A natural transformation from S to T (where S and T are functors from a
category C to a category D) is for each object 'x' of C, a morphism
from S x to T x satisfying some property.

return is a natural transformation from the "Id" functor to the "M"
functor (where M is the monad), while join is a natural transformation
from the "MM" functor to the "M" functor.

If you want to express bind, that would be a natural transformation
from a functor F to a functor G from "C*×C" (where C* is the opposite
category of C) to the "(Id↓M)" comma-category.

F would be defined as (a,b)↦Hom(a, M b)
    φ:Hom(a',a)×ψ:Hom(b,b')↦λ (f:Hom(a,M b)). (M ψ)∘f∘φ
while G would be defined as (a,b)↦Hom(M a, M b)
    φ:Hom(a',a)×ψ:Hom(b,b')↦λ (f:Hom(M a, M b)). (M ψ)∘f∘(M φ)

well, I guess it would be possible to define a monad with 'bind' as a
natural transformation, but how complex it would be where 'join' is so
simple. Plus 'return' and 'join' can be nicely composed to get the
monad laws.

> I'd urge caution in doing so, too. For instance, there is a paper,
> Monads Need Not Be Endofunctors, that describes a generalization of
> monads to monads relative to another functor.

Yes, so these are not monads. Your paper being written on 15 pages is
some indication that it is more complex than simple monads.

I will take a look on your relative adjunctions to understand what it
exactly is.

> And there, bind is
> necessarily primary, because join isn't even well typed. I don't think
> it's written by mathematicians per se (rather, computer
> scientists/type theorists). But mathematicians have their own
> particular interests that affect the way they frame things, and that
> doesn't mean those ways are better for everyone.

Once again, I never said that Monads with 'join' rather than 'bind'
are better in all points. I only said that it better fits the
mathematical point of view. Also note, that there is no true wall
between sciences. Lot of things being interesting in some scientific
domain can also be seen as interesting in some other scientific domain.

>
> > As often some points it out,
> > Haskellers are not very right in their definition of Monad, not
> > because of the bind vs join (in fact in a Monad either of them can
> > be defined from the other one), but because of the functor status
> > of a Monad. A monad, should always be a functor (at least to fit
> > its mathematical definition). And this problem with the functor has
> > probably lead to the use of "bind" (which is polymorphic in two
> > type variables) rather than "join" (which has only one type
> > variable, and thus is simpler). The problem, is that when 'm' is a
> > Haskell Monad which does not belong to the Functor class, we cannot
> > define 'bind' in general from 'join'.
>
> I don't think Functor being a superclass of Monad would make much
> difference. For instance, Applicative is properly a subclass of
> Functor, but we don't use the minimal definition that cannot reproduce
> fmap on its own:
>
>     class Functor f => LaxMonoidal f where
>       unit :: f ()
>       pair :: f a -> f b -> f (a, b)
>
> Instead we use a formulation that subsumes fmap:
>
>     fmap f x = pure f <*> x
>

My background on that matter is not strong enough to discuss that
point, I never used that stuff.

> Because those primitives are what we actually want to use, and it's
> more efficient to implement those directly than to go through some set
> of fully orthogonal combinators purely for the sake of mathematical
> purity.

That is not a problem of purity, that is a problem of simplicity.

>
> And this goes for Monad, as well. For most of the monads in Haskell,
> the definition of join looks exactly like a definition of (>>= id),
> and it's not very arduous to extend that to (>>= f). But if we do
> define join, then we must recover (>>=) by traversing twice; once for
> map and once for join. There are some examples where join can be
> implemented more efficiently than bind, but I don't actually know of
> any Haskell Monads for which this is the case.
>
> And as I mentioned earlier, despite many Haskell folks often not
> digging into monads as done by mathematicians much (and that's fine),
> (>>=) does correspond to a nice operation: variable substitution. This
> is true in category theory, when you talk about algebraic theories,
> and it's true in Haskell when you start noticing that various little
> languages are described by algebraic theories. But from this angle, I
> see no reason why it's _better_ to split variable substitution into
> two operations, first turning a tree into a tree of trees, and then
> flattening.

Shouldn't variable substitution be done by mapping?

>
> It'd be nice if all Functor were a prerequisite for Monad, but even
> then there are still reasons for making (>>=) a primitive.

I do not mean the contrary, and I am very sorry if all readers consider
me as a troll.

>
> -- Dan


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Brandon Allbery
On Tue, Oct 16, 2012 at 1:19 PM, AUGER Cédric <[hidden email]> wrote:
What do you mean by demonstrate? If you do not want to fit the
mathematical presentation, then I have nothing to demonstrate, you have
your point of view, I have mine and they differ. Now, if you want to

I think the point is that Monad is not part of Haskell to satisfy mathematical (or categorical) purity, but to solve a particular set of problems.  Those problems are best addressed with bind, and join works rather less well for them.  Since one of those problems involves interfacing with the world outside of the program, an inefficient but categorically/mathematically more "pure" solution may not be a viable option in practice.

Alternative Preludes which focus on other purposes are a dime a dozen; if you want a categorically pure Monad, nothing stops you from writing one and using it.

--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix/linux, openafs, kerberos, infrastructure          http://sinenomine.net


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

David Thomas
In reply to this post by AUGER Cédric
I think the version below (with a Functor or Applicative superclass)
is clearly the right answer if we were putting the prelude together
from a clean slate.  You can implement whichever is easiest for the
particular monad, use whichever is most appropriate to the context
(and add optimized versions if you prove to need them).  I see no
advantage in any other specific proposal, except the enormous
advantage held by the status quo that it is already written, already
documented, already distributed, and already coded to.

Regarding mathematical "purity" of the solutions, "this is in every
way isomorphic to a monad, but we aren't calling it a monad because we
are describing it a little differently than the most common way to
describe a monad in category theory" strikes me as *less*
mathematically grounded than "we are calling this a monad because it
is in every way isomorphic to a monad."

On Tue, Oct 16, 2012 at 7:03 AM, AUGER Cédric <[hidden email]> wrote:

>
> So I think that an implicit question was why wouldn't we have:
>
> class Monad m where
>   return :: a -> m a
>   kleisli :: (a -> m b) -> (b -> m c) -> (a -> m c)
>   bind = \ x f -> ((const x) >=> f) ()
>   join = id>=>id :: (m (m a) -> m a)
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Simon  Thompson

Not sure I really have anything substantial to contribute, but it's certainly true that if you see

  a -> m b

as a generalisation of the usual function type, a -> b, then return generalises the identity and
kleisli generalises function composition. This makes the types pretty memorable (and often the
definitions too).

Simon


On 16 Oct 2012, at 20:14, David Thomas <[hidden email]> wrote:

>> class Monad m where
>>  return :: a -> m a
>>  kleisli :: (a -> m b) -> (b -> m c) -> (a -> m c)

Simon Thompson | Professor of Logic and Computation
School of Computing | University of Kent | Canterbury, CT2 7NF, UK
[hidden email] | M +44 7986 085754 | W www.cs.kent.ac.uk/~sjt


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Andreas Abel
When I teach my students Haskell's monads, I never put "Kleisli" into my
mouth.  I tell them that monads are for sequencing effects; and the
sequencing is visible clearly in

   (>>)  :: IO a -> IO b -> IO b
   (>>=) :: IO a -> (a -> IO b) -> IO b

but not in

   fmap :: (a -> b) -> IO a -> IO b
   join :: IO (IO a) -> IO a

To me,

   print 1 >> print 2

looks natural, and

   print 1 >>= const (print 2)

still understandable, but

   join $ fmap (const (print 2)) (print 1)

rather not (I needed ghci to get this example right).

I would not want to introduce category theory or Kleisli composition
just to teach my students some effectful Haskell programming.

Cheers,
Andreas

On 16.10.2012 21:45, Simon Thompson wrote:

>
> Not sure I really have anything substantial to contribute, but it's certainly true that if you see
>
>    a -> m b
>
> as a generalisation of the usual function type, a -> b, then return generalises the identity and
> kleisli generalises function composition. This makes the types pretty memorable (and often the
> definitions too).
>
> Simon
>
>
> On 16 Oct 2012, at 20:14, David Thomas <[hidden email]> wrote:
>
>>> class Monad m where
>>>   return :: a -> m a
>>>   kleisli :: (a -> m b) -> (b -> m c) -> (a -> m c)
>
> Simon Thompson | Professor of Logic and Computation
> School of Computing | University of Kent | Canterbury, CT2 7NF, UK
> [hidden email] | M +44 7986 085754 | W www.cs.kent.ac.uk/~sjt
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>


--
Andreas Abel  <><      Du bist der geliebte Mensch.

Theoretical Computer Science, University of Munich
Oettingenstr. 67, D-80538 Munich, GERMANY

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Why Kleisli composition is not in the Monad signature?

Kim-Ee Yeoh
Administrator
In reply to this post by AUGER Cédric
On Tue, Oct 16, 2012 at 9:37 PM, AUGER Cédric <[hidden email]> wrote:
As I said, from the mathematical point of view, join (often noted μ in
category theory) is the (natural) transformation which with return (η
that I may have erroneously written ε in some previous mail) defines a
monad (and requires some additionnal law). 

Auger:

Your emails keep invoking "the mathematical point of view" as if it were something unique and universal.

Mathematical definitions are created and adopted to the extent that they give rise to interesting, meaningful proofs. Coding in Haskell is precisely proving theorems in a branch of constructive mathematics. Its practitioners have found one set of monad definitions more intuitive and sensible when working on such proofs than another such set.

I don't understand your dogmatism about return and join being canonically the best monad definition in all possible mathematics. That's truly a quantifier that beggars imagination.

-- Kim-Ee


On Tue, Oct 16, 2012 at 9:37 PM, AUGER Cédric <[hidden email]> wrote:
Le Tue, 16 Oct 2012 09:51:29 -0400,
Jake McArthur <[hidden email]> a écrit :

> On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <[hidden email]> wrote:
> > I'd be down with putting join in the class, but that tends to not be
> > terribly important for most cases, either.
>
> Join is not the most important, but I do think it's often easier to
> define than bind. I often find myself implementing bind by explicitly
> using join.

join IS the most important from the categorical point of view.
In a way it is natural to define 'bind' from 'join', but in Haskell, it
is not always possible (see the Monad/Functor problem).

As I said, from the mathematical point of view, join (often noted μ in
category theory) is the (natural) transformation which with return (η
that I may have erroneously written ε in some previous mail) defines a
monad (and requires some additionnal law). As often some points it out,
Haskellers are not very right in their definition of Monad, not because
of the bind vs join (in fact in a Monad either of them can be defined
from the other one), but because of the functor status of a Monad. A
monad, should always be a functor (at least to fit its mathematical
definition). And this problem with the functor has probably lead to the
use of "bind" (which is polymorphic in two type variables) rather than
"join" (which has only one type variable, and thus is simpler).
The problem, is that when 'm' is a Haskell Monad which does not belong
to the Functor class, we cannot define 'bind' in general from 'join'.

That is in the context where you have:

return:∀ a. a → (m a)
join:∀ a. (m (m a)) → (m a)
x:m a
f:a → (m b)

you cannot define some term of type 'm b', since you would need to use
at the end, either 'f' (and you would require to produce a 'a' which
would be impossible), or 'return' (and you would need to produce a 'b',
which is impossible), or 'join' (and you would need to produce a 'm (m
b)', and recursively for that you cannot use return which would make
you go back to define a 'm b' term)

For that, you need the 'fmap' operation of the functor.

return:∀ a. a → (m a)
join:∀ a. (m (m a)) → (m a)
fmap:∀ a b. (a→b) → ((m a)→(m b))
x:m a
f:a → (m b)

in this context defining a term of type 'm b' is feasible (join (fmap f
x)), so that you can express "bind = \ x f -> join (fmap f x)".

To sum up, mathematical monads are defined from 'return' and 'join' as
a mathematical monad is always a functor (so 'fmap' is defined, and
'bind', which is more complex than 'join' can be defined from 'join'
and 'fmap'). Haskell does not use a very good definition for their
monads, as they may not be instance of the Functor class (although
most of them can easily be defined as such), and without this 'fmap',
'join' and 'return' would be pretty useless, as you wouldn't be able
to move from a type 'm a' to a type 'm b'.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
12