damodar kulkarni | 15 Oct 13:46 2012
Picon

Why Kleisli composition is not in the Monad signature?

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
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Ertugrul Söylemez | 15 Oct 13:59 2012
Picon

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

damodar kulkarni <kdamodar2000 <at> gmail.com> 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
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Benjamin Franksen | 15 Oct 15:12 2012
Picon

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

Ertugrul Söylemez wrote:
> damodar kulkarni <kdamodar2000 <at> gmail.com> 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
AUGER Cédric | 15 Oct 16:45 2012
Picon

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

Le Mon, 15 Oct 2012 15:12:28 +0200,
Benjamin Franksen <benjamin.franksen <at> helmholtz-berlin.de> a écrit :

> Ertugrul Söylemez wrote:
> > damodar kulkarni <kdamodar2000 <at> gmail.com> 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
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Jake McArthur | 15 Oct 17:33 2012
Picon

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

On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez <es <at> ertes.de> 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
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Jake McArthur | 15 Oct 17:39 2012
Picon

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

On Mon, Oct 15, 2012 at 11:33 AM, Jake McArthur <jake.mcarthur <at> gmail.com> wrote:
> On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez <es <at> ertes.de> 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
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
damodar kulkarni | 16 Oct 04:05 2012
Picon

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

<at> 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.

<at> 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 <jake.mcarthur <at> gmail.com> wrote:
On Mon, Oct 15, 2012 at 11:33 AM, Jake McArthur <jake.mcarthur <at> gmail.com> wrote:
> On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez <es <at> ertes.de> 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
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe




_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Dan Doel | 16 Oct 05:29 2012
Picon

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

On Mon, Oct 15, 2012 at 10:05 PM, damodar kulkarni
<kdamodar2000 <at> gmail.com> wrote:
>  <at> 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
Jake McArthur | 16 Oct 15:51 2012
Picon

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

On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <dan.doel <at> gmail.com> 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
AUGER Cédric | 16 Oct 16:37 2012
Picon

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

Le Tue, 16 Oct 2012 09:51:29 -0400,
Jake McArthur <jake.mcarthur <at> gmail.com> a écrit :

> On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <dan.doel <at> gmail.com> 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
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Daniel Peebles | 16 Oct 17:22 2012
Picon

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

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 <sedrikov <at> gmail.com> wrote:
Le Tue, 16 Oct 2012 09:51:29 -0400,
Jake McArthur <jake.mcarthur <at> gmail.com> a écrit :

> On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <dan.doel <at> gmail.com> 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
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
AUGER Cédric | 16 Oct 17:49 2012
Picon

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

Le Tue, 16 Oct 2012 11:22:08 -0400,
Daniel Peebles <pumpkingod <at> gmail.com> 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 <sedrikov <at> gmail.com>
> wrote:
> 
> > Le Tue, 16 Oct 2012 09:51:29 -0400,
> > Jake McArthur <jake.mcarthur <at> gmail.com> a écrit :
> >
> > > On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <dan.doel <at> gmail.com>
> > > 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
> > Haskell-Cafe <at> haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Dan Doel | 16 Oct 17:58 2012
Picon

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

On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric <sedrikov <at> gmail.com> 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
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
AUGER Cédric | 16 Oct 19:19 2012
Picon

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

Le Tue, 16 Oct 2012 11:58:44 -0400,
Dan Doel <dan.doel <at> gmail.com> a écrit :

> On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric <sedrikov <at> gmail.com>
> 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
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Brandon Allbery | 16 Oct 19:46 2012
Picon

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

On Tue, Oct 16, 2012 at 1:19 PM, AUGER Cédric <sedrikov <at> gmail.com> 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
allbery.b <at> gmail.com                                  ballbery <at> sinenomine.net
unix/linux, openafs, kerberos, infrastructure          http://sinenomine.net

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Ben Franksen | 29 Nov 04:28 2012
Picon

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

Dan Doel wrote:
> On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric <sedrikov <at> gmail.com> 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.

Right. Mathematical /conventions/ can and should be questioned. Sometimes 
they are not appropriate to the application domain. Sometimes the 
conventions are just stupid or obsolete even in a purely mathematical 
context (a well-known example is the extra "syntax sugar" for binomial 
coefficients, but there are worse ones), and you still find them in modern 
text books. Talk about "backwards compatibility"...

My preference for Kleisli composition is because it makes the monad laws so 
much easier to write down and understand. Everywhere it is said that >>= 
must be "associative" and then the laws are written down for >>= and return 
and it is very hard to see what this "lambda grave" has to do with 
associativity or units. When I started with Haskell, this was all I could 
find. It was years later that I stumbled over a text that explained it with 
>=> and suddenly it all became simple and clear and I finally understood the 
monad laws!

So, maybe >>= is the better primitive operation w.r.t. implementation, but 
IMO >=> is *much* more efficient w.r.t. understanding the monad laws. Since 
it is natural to explain the laws of a class using only class methods, I 
would prefer if >=> was added to the class with default implementations for 
>=> in terms of >>= and vice versa, so that you can still use >>= as the 
primitive operation when implementing an instance.

Cheers
--

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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Kim-Ee Yeoh | 24 Oct 07:36 2012

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

On Tue, Oct 16, 2012 at 9:37 PM, AUGER Cédric <sedrikov <at> gmail.com> 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 <sedrikov <at> gmail.com> wrote:
Le Tue, 16 Oct 2012 09:51:29 -0400,
Jake McArthur <jake.mcarthur <at> gmail.com> a écrit :

> On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <dan.doel <at> gmail.com> 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
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
AUGER Cédric | 24 Oct 11:24 2012
Picon

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

Le Wed, 24 Oct 2012 12:36:52 +0700,
Kim-Ee Yeoh <ky3 <at> atamo.com> a écrit :

> On Tue, Oct 16, 2012 at 9:37 PM, AUGER Cédric <sedrikov <at> gmail.com>
> 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.

It is not my wish to be a troller. So please keep or don't keep your
point of view on that matter, and I'll keep mine.

bind is an injection of a Kleisli category to the Hask category to
allow composition,
return is the identity of that same Kleisli category.

I do not pretend <return,bind> to be useless, just that the name
"Monad" does not fit very well. I do not want to fight the people who
have chosen this name, which has spread to many other paradigms. I just
say that it is not very fortunate.

> 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.

Once again that set is not uninteresting, just the name does not fit
very well. And for your comment on proofs, I am perfectly aware of the
Curry Howard correspondance, and that proofs given by Haskell programs
are not very interesting from a mathematical point of view (beside the
fact that this system is unsound, ie. any statement [ie. a type] can
be proved [ie. admits a program of that type], due to the "undefined"
value [I do not want to enter a new troll of wether "undefined" is or
is not a value, if the word value does not please you, replace it]).

> I don't understand your dogmatism about return and join being
> canonically the best monad definition in all possible mathematics.

I am not that dogmatic, if I need to write a program on Haskell, I
won't cry because I will produce some "IO stuff".

> That's truly a quantifier that beggars imagination.
> 
> -- Kim-Ee
> 
> 
> On Tue, Oct 16, 2012 at 9:37 PM, AUGER Cédric <sedrikov <at> gmail.com>
> wrote:
> 
> > Le Tue, 16 Oct 2012 09:51:29 -0400,
> > Jake McArthur <jake.mcarthur <at> gmail.com> a écrit :
> >
> > > On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <dan.doel <at> gmail.com>
> > > 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
> > Haskell-Cafe <at> haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
AUGER Cédric | 16 Oct 16:03 2012
Picon

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

Le Tue, 16 Oct 2012 07:35:34 +0530,
damodar kulkarni <kdamodar2000 <at> gmail.com> a écrit :

>  <at> 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.
> 
>  <at>  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
> <jake.mcarthur <at> gmail.com>wrote:
> 
> > On Mon, Oct 15, 2012 at 11:33 AM, Jake McArthur
> > <jake.mcarthur <at> gmail.com> wrote:
> > > On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez <es <at> ertes.de>
> > > 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
> > Haskell-Cafe <at> haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
David Thomas | 16 Oct 20:14 2012
Picon

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

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 <sedrikov <at> gmail.com> 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
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
Simon Thompson | 16 Oct 21:45 2012
Picon

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


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 <davidleothomas <at> gmail.com> 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
s.j.thompson <at> kent.ac.uk | M +44 7986 085754 | W www.cs.kent.ac.uk/~sjt
Andreas Abel | 22 Oct 18:45 2012
Picon

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

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 <davidleothomas <at> gmail.com> 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
> s.j.thompson <at> kent.ac.uk | M +44 7986 085754 | W www.cs.kent.ac.uk/~sjt
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> 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

andreas.abel <at> ifi.lmu.de
http://www2.tcs.ifi.lmu.de/~abel/
Alberto G. Corona | 24 Oct 13:56 2012
Picon

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

What hiders according with my experience, the understanding of this generalization are some mistakes. two typical mistakes from my side was to consider an arrow as a function, and the consideration of  m  as a kind of container, which it is not from the point of view of category theory. 


a -> m b

instead of as a container, 'm b' must be considered as the set of elements of type b (wrapped within some constructor) plus zero or more null elements of the monad 'm', Such are elements like, for example, Nothing, the empty list or Left .  so that:

null >>= f= null            and
f >>= \x -> null= null

in the other side (->) is an arrow of category theory, not a function.That means that  there may be weird additional things that functions are not be permitted to have. For example, from an element in the set of 'a' may depart many arrows to elements of 'b'. This permits the nondeterminism of the list monad. 

A function like this:

repeatN :: Int -> a -> [a]

can have two interpretations: one functional interpretation, where repeatN is a pure function with results in the list container. The other is the category interpretation, where 'repeatN n' is a morphism that produces n arrows from the set of the Strings to the set of String plus the empty set, The list container is a particular case of container that hold the result of this nondeterministic morphism (other instantiations of this nondeterministic monad would be a set monad or whatever monad build using a multielement container. The container type is not the essence. the essence it is the nondeterministic nature, which, in haskell practical terms, needs a multielement container to hold the multiple results).

so the monadic re-ínterpretation of the repeatN signature is:

repeatN ::Int -> a -> a + {[]}

Here the empty list is the null element of the list monad

in the same way:
functional signature:  a -> Maybe b
monadic interpretation:  a -> b + {Nothing}

functional signature:  a -> Either c b
monadic interpretation:   a -> b + {Left c}

So when i see m b in the context of a monad, I think on nothing more that the set of values of type b (wrapped within some constructor) plus some null elements (if they exist). 

so in essence

a -> m b

is a -> (b + some null elements)

that´s a generalisation of  a -> b

where -> is an arrow, not a function (can return more than one result, can return different things on each computation etc)

And this instance of monoid show how kleisly is the composition and return is the identity element

instance Monad m => Monoid  (a -> m a) where
   mappend = (>=>)
   mempty  = return


According with the above said,   'a -> m a' must be understood as the set of monadic endomorphisms in a:   

a -> a +{null elements of the monad m}

Which is, in essence, a -> a

2012/10/16 Simon Thompson <s.j.thompson <at> kent.ac.uk>

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 <davidleothomas <at> gmail.com> 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
s.j.thompson <at> kent.ac.uk | M +44 7986 085754 | W www.cs.kent.ac.uk/~sjt


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe



--
Alberto.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Alberto G. Corona | 24 Oct 14:08 2012
Picon

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

The particular case from which the former is a generalization:



instance Monad m => Monoid  (a -> a) where
   mappend = (.)
   mempty  = id

Here the monoid is defined for the functions within the set of values of type a. There are no null elements.



2012/10/24 Alberto G. Corona <agocorona <at> gmail.com>
What hiders according with my experience, the understanding of this generalization are some mistakes. two typical mistakes from my side was to consider an arrow as a function, and the consideration of  m  as a kind of container, which it is not from the point of view of category theory. 

a -> m b

instead of as a container, 'm b' must be considered as the set of elements of type b (wrapped within some constructor) plus zero or more null elements of the monad 'm', Such are elements like, for example, Nothing, the empty list or Left .  so that:

null >>= f= null            and
f >>= \x -> null= null

in the other side (->) is an arrow of category theory, not a function.That means that  there may be weird additional things that functions are not be permitted to have. For example, from an element in the set of 'a' may depart many arrows to elements of 'b'. This permits the nondeterminism of the list monad. 

A function like this:

repeatN :: Int -> a -> [a]

can have two interpretations: one functional interpretation, where repeatN is a pure function with results in the list container. The other is the category interpretation, where 'repeatN n' is a morphism that produces n arrows from the set of the Strings to the set of String plus the empty set, The list container is a particular case of container that hold the result of this nondeterministic morphism (other instantiations of this nondeterministic monad would be a set monad or whatever monad build using a multielement container. The container type is not the essence. the essence it is the nondeterministic nature, which, in haskell practical terms, needs a multielement container to hold the multiple results).

so the monadic re-ínterpretation of the repeatN signature is:

repeatN ::Int -> a -> a + {[]}

Here the empty list is the null element of the list monad

in the same way:
functional signature:  a -> Maybe b
monadic interpretation:  a -> b + {Nothing}

functional signature:  a -> Either c b
monadic interpretation:   a -> b + {Left c}

So when i see m b in the context of a monad, I think on nothing more that the set of values of type b (wrapped within some constructor) plus some null elements (if they exist). 

so in essence

a -> m b

is a -> (b + some null elements)

that´s a generalisation of  a -> b

where -> is an arrow, not a function (can return more than one result, can return different things on each computation etc)

And this instance of monoid show how kleisly is the composition and return is the identity element

instance Monad m => Monoid  (a -> m a) where
   mappend = (>=>)
   mempty  = return


According with the above said,   'a -> m a' must be understood as the set of monadic endomorphisms in a:   

a -> a +{null elements of the monad m}

Which is, in essence, a -> a

2012/10/16 Simon Thompson <s.j.thompson <at> kent.ac.uk>

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 <davidleothomas <at> gmail.com> 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
s.j.thompson <at> kent.ac.uk | M +44 7986 085754 | W www.cs.kent.ac.uk/~sjt


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe



--
Alberto.



--
Alberto.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Tony Morris | 24 Oct 08:22 2012
Picon

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

As a side note, I think a direct superclass of Functor for Monad is not
a good idea, just sayin'

class Functor f where
  fmap :: (a -> b) -> f a -> f b

class Functor f => Apply f where
  (<*>) :: f (a -> b) -> f a -> f b

class Apply f => Bind f where
  (=<<) :: (a -> f b) -> f a -> f b

class Apply f => Applicative f where
  unit :: a -> f a

class (Applicative f, Bind f) => Monad f where

Same goes for Comonad (e.g. [] has (=<<) but not counit)
... and again for Monoid, Category, I could go on...

On 17/10/12 04:14, David Thomas wrote:
> 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 <sedrikov <at> gmail.com> 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
>> Haskell-Cafe <at> haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

--

-- 
Tony Morris
http://tmorris.net/
Ben Franksen | 29 Nov 03:52 2012
Picon

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

Tony Morris wrote:
> As a side note, I think a direct superclass of Functor for Monad is not
> a good idea, just sayin'
> 
> class Functor f where
>   fmap :: (a -> b) -> f a -> f b
> 
> class Functor f => Apply f where
>   (<*>) :: f (a -> b) -> f a -> f b
> 
> class Apply f => Bind f where
>   (=<<) :: (a -> f b) -> f a -> f b
> 
> class Apply f => Applicative f where
>   unit :: a -> f a
> 
> class (Applicative f, Bind f) => Monad f where
> 
> Same goes for Comonad (e.g. [] has (=<<) but not counit)
> ... and again for Monoid, Category, I could go on...

Hi Tony

even though I dismissed your mentioning this on the Haskell' list, I do have 
to admit that the proposal has a certain elegance. However, before I buy 
into this scheme, I'd like to see some striking examples for types with 
natural (or at least useful) Apply and Bind instances that cannot be made 
Applicative resp. Monad. Also, it is not clear to me what laws should hold 
for them.

Cheers
--

-- 
Ben Franksen
()  ascii ribbon campaign - against html e-mail 
/\  www.asciiribbon.org   - against proprietary attachments
Brent Yorgey | 29 Nov 23:17 2012

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

On Thu, Nov 29, 2012 at 03:52:58AM +0100, Ben Franksen wrote:
> Tony Morris wrote:
> > As a side note, I think a direct superclass of Functor for Monad is not
> > a good idea, just sayin'
> > 
> > class Functor f where
> >   fmap :: (a -> b) -> f a -> f b
> > 
> > class Functor f => Apply f where
> >   (<*>) :: f (a -> b) -> f a -> f b
> > 
> > class Apply f => Bind f where
> >   (=<<) :: (a -> f b) -> f a -> f b
> > 
> > class Apply f => Applicative f where
> >   unit :: a -> f a
> > 
> > class (Applicative f, Bind f) => Monad f where
> > 
> > Same goes for Comonad (e.g. [] has (=<<) but not counit)
> > ... and again for Monoid, Category, I could go on...
> 
> Hi Tony
> 
> even though I dismissed your mentioning this on the Haskell' list, I do have 
> to admit that the proposal has a certain elegance. However, before I buy 
> into this scheme, I'd like to see some striking examples for types with 
> natural (or at least useful) Apply and Bind instances that cannot be made 
> Applicative resp. Monad. 

Try writing an Applicative instances for (Data.Map.Map k).  It can't
be done, but the Apply instance is (I would argue) both natural and useful.

> Also, it is not clear to me what laws should hold 
> for them.

http://hackage.haskell.org/package/semigroupoids defines all of these
and specifies laws, presumably derived in a principled way.

-Brent
Ben Franksen | 30 Nov 02:33 2012
Picon

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

Brent Yorgey wrote:
> On Thu, Nov 29, 2012 at 03:52:58AM +0100, Ben Franksen wrote:
>> Tony Morris wrote:
>> > As a side note, I think a direct superclass of Functor for Monad is not
>> > a good idea, just sayin'
>> > 
>> > class Functor f where
>> >   fmap :: (a -> b) -> f a -> f b
>> > 
>> > class Functor f => Apply f where
>> >   (<*>) :: f (a -> b) -> f a -> f b
>> > 
>> > class Apply f => Bind f where
>> >   (=<<) :: (a -> f b) -> f a -> f b
>> > 
>> > class Apply f => Applicative f where
>> >   unit :: a -> f a
>> > 
>> > class (Applicative f, Bind f) => Monad f where
>> > 
>> > Same goes for Comonad (e.g. [] has (=<<) but not counit)
>> > ... and again for Monoid, Category, I could go on...
>> 
>> Hi Tony
>> 
>> even though I dismissed your mentioning this on the Haskell' list, I do 
have 
>> to admit that the proposal has a certain elegance. However, before I buy 
>> into this scheme, I'd like to see some striking examples for types with 
>> natural (or at least useful) Apply and Bind instances that cannot be made 
>> Applicative resp. Monad. 
> 
> Try writing an Applicative instances for (Data.Map.Map k).  It can't
> be done, but the Apply instance is (I would argue) both natural and 
useful.

I see. So there is one example. Are there more? I'd like to get a feeling 
for the abstraction and this is hard if there is only a single example.

>> Also, it is not clear to me what laws should hold 
>> for them.
> 
> http://hackage.haskell.org/package/semigroupoids defines all of these
> and specifies laws, presumably derived in a principled way.

Ok. I was not surprised to see that there are not many laws for the classes 
without unit.

Cheers
--

-- 
Ben Franksen
()  ascii ribbon campaign - against html e-mail 
/\  www.asciiribbon.org   - against proprietary attachments
Brent Yorgey | 30 Nov 15:51 2012

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

On Fri, Nov 30, 2012 at 02:33:54AM +0100, Ben Franksen wrote:
> Brent Yorgey wrote:
> > On Thu, Nov 29, 2012 at 03:52:58AM +0100, Ben Franksen wrote:
> >> Tony Morris wrote:
> >> > As a side note, I think a direct superclass of Functor for Monad is not
> >> > a good idea, just sayin'
> >> > 
> >> > class Functor f where
> >> >   fmap :: (a -> b) -> f a -> f b
> >> > 
> >> > class Functor f => Apply f where
> >> >   (<*>) :: f (a -> b) -> f a -> f b
> >> > 
> >> > class Apply f => Bind f where
> >> >   (=<<) :: (a -> f b) -> f a -> f b
> >> > 
> >> > class Apply f => Applicative f where
> >> >   unit :: a -> f a
> >> > 
> >> > class (Applicative f, Bind f) => Monad f where
> >> > 
> >> > Same goes for Comonad (e.g. [] has (=<<) but not counit)
> >> > ... and again for Monoid, Category, I could go on...
> >> 
> >> Hi Tony
> >> 
> >> even though I dismissed your mentioning this on the Haskell' list, I do 
> have 
> >> to admit that the proposal has a certain elegance. However, before I buy 
> >> into this scheme, I'd like to see some striking examples for types with 
> >> natural (or at least useful) Apply and Bind instances that cannot be made 
> >> Applicative resp. Monad. 
> > 
> > Try writing an Applicative instances for (Data.Map.Map k).  It can't
> > be done, but the Apply instance is (I would argue) both natural and 
> useful.
> 
> I see. So there is one example. Are there more? I'd like to get a feeling 
> for the abstraction and this is hard if there is only a single example.

Any data type which admits structures of arbitrary but *only finite*
size has a natural "zippy" Apply instance but no Applicative (since
pure would have to be an infinite structure).  The Map instance I
mentioned above falls in this category.  Though I guess I'm having
trouble coming up with other examples, but I'm sure some exist.  Maybe
Edward knows of other examples.

-Brent
Dan Doel | 30 Nov 16:44 2012
Picon

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

Lists! The finite kind.

This could mean Seq for instance.

On Nov 30, 2012 9:53 AM, "Brent Yorgey" <byorgey <at> seas.upenn.edu> wrote:
On Fri, Nov 30, 2012 at 02:33:54AM +0100, Ben Franksen wrote:
> Brent Yorgey wrote:
> > On Thu, Nov 29, 2012 at 03:52:58AM +0100, Ben Franksen wrote:
> >> Tony Morris wrote:
> >> > As a side note, I think a direct superclass of Functor for Monad is not
> >> > a good idea, just sayin'
> >> >
> >> > class Functor f where
> >> >   fmap :: (a -> b) -> f a -> f b
> >> >
> >> > class Functor f => Apply f where
> >> >   (<*>) :: f (a -> b) -> f a -> f b
> >> >
> >> > class Apply f => Bind f where
> >> >   (=<<) :: (a -> f b) -> f a -> f b
> >> >
> >> > class Apply f => Applicative f where
> >> >   unit :: a -> f a
> >> >
> >> > class (Applicative f, Bind f) => Monad f where
> >> >
> >> > Same goes for Comonad (e.g. [] has (=<<) but not counit)
> >> > ... and again for Monoid, Category, I could go on...
> >>
> >> Hi Tony
> >>
> >> even though I dismissed your mentioning this on the Haskell' list, I do
> have
> >> to admit that the proposal has a certain elegance. However, before I buy
> >> into this scheme, I'd like to see some striking examples for types with
> >> natural (or at least useful) Apply and Bind instances that cannot be made
> >> Applicative resp. Monad.
> >
> > Try writing an Applicative instances for (Data.Map.Map k).  It can't
> > be done, but the Apply instance is (I would argue) both natural and
> useful.
>
> I see. So there is one example. Are there more? I'd like to get a feeling
> for the abstraction and this is hard if there is only a single example.

Any data type which admits structures of arbitrary but *only finite*
size has a natural "zippy" Apply instance but no Applicative (since
pure would have to be an infinite structure).  The Map instance I
mentioned above falls in this category.  Though I guess I'm having
trouble coming up with other examples, but I'm sure some exist.  Maybe
Edward knows of other examples.

-Brent

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Gershom Bazerman | 30 Nov 18:21 2012
Picon

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

On 11/30/12 10:44 AM, Dan Doel wrote:

Lists! The finite kind.

This could mean Seq for instance.

On Nov 30, 2012 9:53 AM, "Brent Yorgey" <byorgey <at> seas.upenn.edu> wrote:

Any data type which admits structures of arbitrary but *only finite*
size has a natural "zippy" Apply instance but no Applicative (since
pure would have to be an infinite structure).  The Map instance I
mentioned above falls in this category.  Though I guess I'm having
trouble coming up with other examples, but I'm sure some exist.  Maybe
Edward knows of other examples.

Another common case would be an embedded DSL representing code in a different language, targeting a different platform (or even an FPGA or the like), etc. You can apply `OtherLang (a -> b)` to an `OtherLang a` and get an `OtherLang b`, but you clearly can't promote (or "lower," I guess) an arbitrary Haskell function into a function in your target language. This is the same reason that GArrows remove the `arr` function (http://www.cs.berkeley.edu/~megacz/garrows/).

--Gershom
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Ben Franksen | 30 Nov 23:00 2012
Picon

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

Gershom Bazerman wrote:
> On 11/30/12 10:44 AM, Dan Doel wrote:
>>
>> Lists! The finite kind.
>>
>> This could mean Seq for instance.
>>
>> On Nov 30, 2012 9:53 AM, "Brent Yorgey" <byorgey <at> seas.upenn.edu 
>> <mailto:byorgey <at> seas.upenn.edu>> wrote:
>>
>>
>>     Any data type which admits structures of arbitrary but *only finite*
>>     size has a natural "zippy" Apply instance but no Applicative (since
>>     pure would have to be an infinite structure).  The Map instance I
>>     mentioned above falls in this category.  Though I guess I'm having
>>     trouble coming up with other examples, but I'm sure some exist.  
Maybe
>>     Edward knows of other examples.
>>
> 
> Another common case would be an embedded DSL representing code in a 
> different language, targeting a different platform (or even an FPGA or 
> the like), etc. You can apply `OtherLang (a -> b)` to an `OtherLang a` 
> and get an `OtherLang b`, but you clearly can't promote (or "lower," I 
> guess) an arbitrary Haskell function into a function in your target 
> language. This is the same reason that GArrows remove the `arr` function 
> (http://www.cs.berkeley.edu/~megacz/garrows/).

A fine example! And I am getting the drift... yes, this could be a useful 
abstraction.

Now, on to Bind: the standard finite structure example for Bind is most 
probably the substitution thingy, i.e. if m :: m a, f :: a -> m b, then m 
>>= f means replace all elements x :: a in m with f x and then flatten the 
result so it's an m b again. Like concatMap for lists, right? So, there is 
no return for that in the Map case for exactly the same reason as with 
Apply: the unit would have have value id for every possible key, so cannot 
be finite.

So what about an example for Bind\\Monad that is not yet another variation 
of the finite structure theme?

Cheers
--

-- 
Ben Franksen
()  ascii ribbon campaign - against html e-mail 
/\  www.asciiribbon.org   - against proprietary attachments
Kim-Ee Yeoh | 1 Dec 05:48 2012

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

Ben,


> Now, on to Bind: the standard finite structure example for Bind is most probably the substitution thingy ...

Danger of conflating a bunch of things here:

(1) the substitution monadic effect is always also applicative and always also unital/pointed because monads are always applicative and pointed.

(2) the zippy applicative effect is NOT monadic (see main applicative paper)

(3) for finite structures, there's even a pre-applicative-but-still-zippy-ish Apply effect that's apparently NOT unital/pointed. I don't know of any results that crystallize this intuition about finite/infinite cleanly distributing itself into Applicative and Apply bins.

(4) all the above has thus far been functors! Gershom has explained a use case where Apply isn't even one.

HTH,
-- Kim-Ee


On Sat, Dec 1, 2012 at 5:00 AM, Ben Franksen <ben.franksen <at> online.de> wrote:
Gershom Bazerman wrote:
> On 11/30/12 10:44 AM, Dan Doel wrote:
>>
>> Lists! The finite kind.
>>
>> This could mean Seq for instance.
>>
>> On Nov 30, 2012 9:53 AM, "Brent Yorgey" <byorgey <at> seas.upenn.edu
>> <mailto:byorgey <at> seas.upenn.edu>> wrote:
>>
>>
>>     Any data type which admits structures of arbitrary but *only finite*
>>     size has a natural "zippy" Apply instance but no Applicative (since
>>     pure would have to be an infinite structure).  The Map instance I
>>     mentioned above falls in this category.  Though I guess I'm having
>>     trouble coming up with other examples, but I'm sure some exist.
Maybe
>>     Edward knows of other examples.
>>
>
> Another common case would be an embedded DSL representing code in a
> different language, targeting a different platform (or even an FPGA or
> the like), etc. You can apply `OtherLang (a -> b)` to an `OtherLang a`
> and get an `OtherLang b`, but you clearly can't promote (or "lower," I
> guess) an arbitrary Haskell function into a function in your target
> language. This is the same reason that GArrows remove the `arr` function
> (http://www.cs.berkeley.edu/~megacz/garrows/).

A fine example! And I am getting the drift... yes, this could be a useful
abstraction.

Now, on to Bind: the standard finite structure example for Bind is most
probably the substitution thingy, i.e. if m :: m a, f :: a -> m b, then m
>>= f means replace all elements x :: a in m with f x and then flatten the
result so it's an m b again. Like concatMap for lists, right? So, there is
no return for that in the Map case for exactly the same reason as with
Apply: the unit would have have value id for every possible key, so cannot
be finite.

So what about an example for Bind\\Monad that is not yet another variation
of the finite structure theme?

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


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
oleg | 23 Oct 10:28 2012

Why Kleisli composition is not in the Monad signature?


Andreas Abel wrote:
> 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

Indeed! I'd like to point out an old academic paper that was written
exactly on the subject at hand: how Category Theory monads relate to
monads in Haskell. Here is the relevant quotation:

    Monads are typically equated with single-threadedness, and are
    therefore used as a technique for incorporating imperative features
    into a purely functional language. Category theory monads have little
    to do with single-threadedness; it is the sequencing imposed by
    composition that ensures single-threadedness. In a Wadler-ised monad
    this is a consequence of bundling the Kleisli star and flipped compose
    into the bind operator. There is nothing new in this connection. Peter
    Landin in his Algol 60 used functional composition to model
    semi-colon. Semi-colon can be thought of as a state transforming
    operator that threads the state of the machine throughout a program.
    The work of Peyton-Jones and Wadler has turned full circle back to
    Landin's earlier work as their use of Moggi's sequencing monad enables
    real side-effects to be incorporated into monad operations such as
    print.

Quoted from: Sec 3: An historical aside
Jonathan M. D. Hill and Keith Clarke:
An Introduction to Category Theory, Category Theory Monads,
and Their Relationship to Functional Programming. 1994.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.6497

I'd like to stress: the single-threadedness, the trick that lets us
embed imperative language into a pure one, has *little to do* with
category-theoretic monads with their Klesli star. 

The web page
	http://okmij.org/ftp/Computation/IO-monad-history.html
describes the work of Landin in detail, contrasting Landin's and
Peyton-Jones' papers.

Gmane