20

After reading this article I understand that >=> (Kleisli arrow) is just a higher order function to compose functions, that return "monadic values". For example:

val f: A => M[B] = ...
val g: B => M[C] = ...

val h: A => M[C] = f >=> g // compose f and g with Kleisli arrow

It looks like a simple composition of "simple" functions (i.e. pure functions that return simple values):

val f: A => B = ...
val g: B => C = ...

val h = f andThen g; // compose f and g

Now I guess this "simple" composition andThen conforms to certain laws

  • Identity: f andThen g == g and g andThen f == g for identity function: f[A](a:A):A = a
  • Associativity: (f1 andThen f2) andThen f3 == f1 andThen (f2 andThen f3)

And now my questions:

  • Does >=> conform to those laws, where identity is f(a:A) = M[a].unit(a) ?
  • Can we derive the monadic laws from the those laws ? Are those laws and the monadic laws equivalent ?
Michael
  • 41,026
  • 70
  • 193
  • 341

1 Answers1

12

What you have here is the immediate consequence of this construction being a category.

  1. Yes, they do conform. And that they conform is indeed the reason they are called Kleisli, because the Kleisli arrows plus types form the Kleisli category of the monad (to which every monad gives rise to). It's also why unit is called like that: it is the unit under composition of Kleisli arrows.
  2. Yes, they can be derived. Use the transformation (f <=< g) x = f =<< (g x) (where <=< is andThen, and =<< is probably something like flip(bind) in Scala). The exact steps of the derivation can be found here.
phipsgabler
  • 20,535
  • 4
  • 40
  • 60
  • Thank you. `=<<` is _flatMap_ in Scala, by the way. – Michael Feb 01 '14 at 18:29
  • BTW, could you explain _why_ the identity law is _important_? It's _intuitive_ but _why_ is it important ? What if I have a structure, which does not comply to the identity law ? What bad thing can happen ? – Michael Feb 01 '14 at 18:32
  • 1
    Well, the point is that having identities under composition is required by the _definition_ of a category. If you don't have them, nothing "bad" will happen, but the structure cannot be called a category. Like a "monoid" without identity is just not a monoid, but a semigroup. I'll also put a link to a somewhat easier introduction to categories into the answer. – phipsgabler Feb 01 '14 at 18:39
  • The part about the intuition is that most intuitive structures of this kind just turn out to be based on category theory. You'll find composable morphisms with identities almost everywhere in maths, and so in functional programming. That's what makes CT so useful (and also so general). – phipsgabler Feb 01 '14 at 18:44