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

Alberto G. Corona agocorona at gmail.com
Wed Oct 24 13:56:02 CEST 2012

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20121024/321a46e0/attachment.htm>

More information about the Haskell-Cafe mailing list