22
$\begingroup$

In monads, Kleisli composition has the type

infix oK: ('b -> 'c monad) -> ('a -> 'b monad) -> ('a -> 'c monad)

and it satisfies the nice algebraic associativity law

(f oK g) oK h = f oK (g oK h)

But in Haskell rather bind is used:

bind: ('a monad) -> ('a -> 'b monad) -> ('b monad)

whose "associativity" law in not the classic algebraic one:

bind m (λa. bind  (k a) (λb. h b)) = bind (bind m (λa. k a)) (λb. h b)

What reasoning led to this choice of favoring bind over Kleisli composition?

$\endgroup$
8
  • 4
    $\begingroup$ Also, who's "they"? Kleisli composition is available in Haskell as >=>, it's just not used quite as much as other combinators. I also don't know what "practical" rationale you're expecting. You can always rewrite a >>= b ≡ (const a >=> b) () and a >=> b ≡ (>>= b) . a. The closest thing to a 'reason' is that monads were introduced originally to represent IO, and you'd typically want to end on IO () not a -> IO (), other than that slight convenience the choice is completely arbitrary $\endgroup$
    – Cubic
    Aug 7, 2023 at 11:13
  • $\begingroup$ Associativity being a little easier to express with one form certainly isn't really a selling point for preferring that form in a programming language. $\endgroup$
    – Cubic
    Aug 7, 2023 at 11:19
  • 1
    $\begingroup$ @Cubic: If one's language is point-free, then associativity directly leads to shorter code. This question was useful food for thought. $\endgroup$
    – Corbin
    Aug 8, 2023 at 20:50
  • $\begingroup$ @Cubic - I've not written a huge amount of Haskell code (a handful of parsers and interpreters when I was playing with parser combinators a while back probably represents most of it) but I have found Kleisli composition very useful at times, enough that I've wondered why it doesn't feature in tutorials more often. This also applies to some of the Arrow combinators, which are particularly useful due to the fact that there's a default instance of Arrow for functions, so you can use them anywhere. $\endgroup$
    – occipita
    Aug 9, 2023 at 16:30
  • 1
    $\begingroup$ @KarlKnechtel In the Haskell standard library, bind is taken as the fundamental operation and Kleisli composition is implemented in terms of bind. It's possible to do it the other way around, this is just the choice Haskell has made. I think the question is about this choice. $\endgroup$ Mar 21 at 2:39

3 Answers 3

25
$\begingroup$

The original reason monads were introduced in Haskell was to implement I/O. This answer of mine discusses many of the details of that usage, including the way things are implemented internally. Therefore, to understand the particular choice of methods included in the Monad typeclass, it’s helpful to focus on IO itself.

I/O involves sequencing a series of actions together. The goal is to essentially embed an effectful, imperative language into a pure, lazy, functional one. Each action to be sequenced is not something we think of as a function, but something we think of as an expression returning a value. This can be seen most obviously in do notation, which allows monadic programming to be performed in terms of statements that sequence these monadic values. blueberry’s answer already discusses how >>= naturally maps to do notation.

This is the main reason. But there are a few other factors as well:

  1. Bind and Kleisli composition are trivially expressible in terms of each other, and Haskell provides Kleisli composition in its standard library under the names >=> and <=<.

  2. Arguably, join would be a better choice than either >>= or >=>, as Monad has a Functor superclass, so a minimal specification would define join rather than >>= (as a definition of >>= essentially duplicates the definition of fmap). However, in practice, there are two reasons to prefer >>=:

    • For many Monad implementations, specification in terms of pure and >>= is clearer than specification in terms of pure, fmap, and join. For that reason, many instances define fmap (and <*>, if we also consider Applicative) in terms of >>= rather than the other way around.

    • In theory, it ought to be possible to make join a method of Monad and allow users to specify whichever method they prefer, and in fact this used to be the case! However, the nested use of the monadic type in the argument to join prevents GHC’s automatic newtype deriving mechanism from working with the class. In theory, this should be possible to fix using some relatively recent extensions to the type system, see this blog post for the details, but it’s such a minor thing that nobody has cared enough to do the necessary work.

  3. Since >=> always uses -> as the underlying arrow, >>= is necessarily closer to what monads operationally do than >=> is. If composition is generalized to an arbitrary arrow, this may no longer be the case, as the “function-like thing” may be a user-defined type, and its members may themselves be primitive. However, as long as we’re known to be working with ->, it can be slightly more efficient to use >>= as the method, since it will be packed in the dictionary used to implement unspecialized polymorphic functions with a Monad constraint.

$\endgroup$
1
  • 1
    $\begingroup$ +1 - this is a more thorough answer then mine. $\endgroup$
    – blueberry
    Aug 8, 2023 at 1:26
13
$\begingroup$

Two examples:

  1. Consider do notation:

    do
      a <- f x
      b <- g a
      h b
    

    This desugars to:

    f x >>= (\a -> g a >>= (\b -> h b))
    

    Quite simple to understand, and a straightforward transformation. Now, with Kleisli composition, this is much harder to "nicely" implement.

  2. Consider bind itself:

    f x 
    >>= g
    >>= h
    

    This reads nicely in a programming language, whereas the equivalent with kleisli composition does not. (I personally can't even do kleisli composition in my head, whereas bind is easy). Remember, not everything is about properties like nice associativity or similar - readability is paramount.

$\endgroup$
1
  • 5
    $\begingroup$ Please don’t delete your answer! It has useful examples, and I linked to it from mine, so if you deleted it, I’d have to incorporate them into my answer, anyway. :) $\endgroup$
    – Alexis King
    Aug 8, 2023 at 1:27
2
$\begingroup$

All the above are neat answers. Just to add to the understanding of the importance of bind associativity and especially blueberry's answer, this article helped me understanding why bind is important from a programming language design point of view:

https://wiki.haskell.org/Monad_laws

So bind is an implementation of a nice syntactic sugar, the do notation, which is intuitive for programmers.

Forgive me being an algebraist.

$\endgroup$
1
  • 2
    $\begingroup$ As a trigonometrist myself, all your sins are forgiven. $\endgroup$
    – kaya3
    Mar 14 at 13:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .