Re: [Haskell-cafe] Why Kleisli composition is not in the Monad signature?

16 Oct 2012

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