On Clojure

March 5, 2009

A monad tutorial for Clojure programmers (part 1)

Filed under: Libraries — khinsen @ 6:15 pm

Monads in functional programming are most often associated with the Haskell language, where they play a central role in I/O and have found numerous other uses. Most introductions to monads are currently written for Haskell programmers. However, monads can be used with any functional language, even languages quite different from Haskell. Here I want to explain monads in the context of Clojure, a modern Lisp dialect with strong support for functional programming. A monad implementation for Clojure is available in the library clojure.algo.monads. Before trying out the examples given in this tutorial, type (use 'clojure.algo.monads) into your Clojure REPL. You also have to install the monad library, of course, which you can do by hand, or using build tools such as leiningen.

Monads are about composing computational steps into a bigger multi-step computation. Let's start with the simplest monad, known as the identity monad in the Haskell world. It's actually built into the Clojure language, and you have certainly used it: it's the let form.

Consider the following piece of code:

(let [a  1
      b  (inc a)]
  (* a b))

This can be seen as a three-step calculation:

  1. Compute 1 (a constant), and call the result a.
  2. Compute (inc a), and call the result b.
  3. Compute (* a b), which is the result of the multi-step computation.

Each step has access to the results of all previous steps through the symbols to which their results have been bound.

Now suppose that Clojure didn't have a let form. Could you still compose computations by binding intermediate results to symbols? The answer is yes, using functions. The following expression is in fact equivalent to the previous one:

( (fn [a]  ( (fn [b] (* a b)) (inc a) ) )  1 )

The outermost level defines an anonymous function of a and calls with with the argument 1 - this is how we bind 1 to the symbol a. Inside the function of a, the same construct is used once more: the body of (fn [a] ...) is a function of b called with argument (inc a). If you don't believe that this somewhat convoluted expression is equivalent to the original let form, just paste both into Clojure!

Of course the functional equivalent of the let form is not something you would want to work with. The computational steps appear in reverse order, and the whole construct is nearly unreadable even for this very small example. But we can clean it up and put the steps in the right order with a small helper function, bind. We will call it m-bind (for monadic bind) right away, because that's the name it has in Clojure's monad library. First, its definition:

(defn m-bind [value function]
  (function value))

As you can see, it does almost nothing, but it permits to write a value before the function that is applied to it. Using m-bind, we can write our example as

(m-bind 1        (fn [a]
(m-bind (inc a)  (fn [b]
        (* a b)))))

That's still not as nice as the let form, but it comes a lot closer. In fact, all it takes to convert a let form into a chain of computations linked by m-bind is a little macro. This macro is called domonad, and it permits us to write our example as

(domonad identity-m
  [a  1
   b  (inc a)]
  (* a b))

This looks exactly like our original let form. Running macroexpand-1 on it yields

(clojure.algo.monads/with-monad identity-m
  (m-bind 1 (fn [a] (m-bind (inc a) (fn [b] (m-result (* a b)))))))

This is the expression you have seen above, wrapped in a (with-monad identity-m ...) block (to tell Clojure that you want to evaluate it in the identity monad) and with an additional call to m-result that I will explain later. For the identity monad, m-result is just identity - hence its name.

As you might guess from all this, monads are generalizations of the let form that replace the simple m-bind function shown above by something more complex. Each monad is defined by an implementation of m-bind and an associated implementation of m-result. A with-monad block simply binds (using a let form!) these implementations to the names m-bind and m-result, so that you can use a single syntax for composing computations in any monad. Most frequently, you will use the domonad macro for this.

As our second example, we will look at another very simple monad, but one that adds something useful that you don't get in a let form. Suppose your computations can fail in some way, and signal failure by producing nil as a result. Let's take our example expression again and wrap it into a function:

(defn f [x]
  (let [a  x
        b  (inc a)]
    (* a b)))

In the new setting of possibly-failing computations, you want this to return nil when x is nil, or when (inc a) yields nil. (Of course (inc a) will never yield nil, but that's the nature of examples...) Anyway, the idea is that whenever a computational step yields nil, the final result of the computation is nil, and the remaining steps are never executed. All it takes to get this behaviour is a small change:

(defn f [x]
  (domonad maybe-m
    [a  x
     b  (inc a)]
    (* a b)))

The maybe monad represents computations whose result is maybe a valid value, but maybe nil. Its m-result function is still identity, so we don't have to discuss m-result yet (be patient, we will get there in the second part of this tutorial). All the magic is in the m-bind function:

(defn m-bind [value function]
  (if (nil? value)
      nil
      (function value)))

If its input value is non-nil, it calls the supplied function, just as in the identity monad. Recall that this function represents the rest of the computation, i.e. all following steps. If the value is nil, then m-bind returns nil and the rest of the computation is never called. You can thus call (f 1), yielding 2 as before, but also (f nil) yielding nil, without having to add nil-detecting code after every step of your computation, because m-bind does it behind the scenes.

In part 2, I will introduce some more monads, and look at some generic functions that can be used in any monad to aid in composing computations.

About these ads

29 Comments »

  1. Great tutorial! Thanks so much for writing this!

    There is one thing I’m not sure about. It says “For the identity monad, m-result is just identity”. Does the term “identity” in the context of monads just mean that the m-result function simply returns the result of the applying a given function to a given value with no other logic?

    Comment by Mark Volkmann — March 5, 2009 @ 7:03 pm

    • “Identity monad” is the name commonly given to the most basic monad that adds nothing to the bare computation. Its definition in Clojure is

      (defmonad identity-m
      [m-result identity
      m-bind (fn m-result-id [mv f]
      (f mv))
      ])

      The definition of any monad always consists of both m-bind and m-result, the two must in fact satisfy certain conditions.

      Comment by khinsen — March 5, 2009 @ 8:06 pm

    • Yes. For more advanced explanation see khinsen’s answer.

      Comment by Jacek Laskowski — October 12, 2010 @ 7:26 am

  2. I can’t follow the meaning of the following sentence beyond the word “permits”:

    “As you can see, it does almost nothing, but it permits to write a value before the function that is applied to it.”

    Comment by Tracy Harms — March 5, 2009 @ 7:58 pm

    • What I want to say is that replacing (function value) by (m-bind value function)arranges the computations in the right order, i.e. they appear in the order in which they are executed.

      Comment by khinsen — March 5, 2009 @ 8:10 pm

      • Perhaps “… but it permits one to write…” or “…it permits the programmer…” or even “…it permits you…”. At worst, “it permits the value to appear before the function that is applied to it.”

        Comment by Ron Lusk — August 21, 2009 @ 4:43 pm

  3. [...] for Clojure programmers (part 2) Filed under: Libraries — khinsen @ 1:09 pm In the first part of this tutorial, I have introduced the two most basic monads: the identity monad and the maybe [...]

    Pingback by A monad tutorial for Clojure programmers (part 2) « On Clojure — March 6, 2009 @ 1:14 pm

  4. I’ve read this and part two a few times, after getting a handle on the absolute basics via the Python-based tutorial here: http://lukeplant.me.uk/blog.php?id=1107301643, and I feel I’m making progress toward understanding, so thanks! I’m looking forward to trying out the monad library sometime soon.

    I would like to put in an enthusiastic vote for the probability monad as a case study in a more advanced part. I decided I should put in the time to learn about monads after reading about how much people like working with it.

    Keep up the great work!

    Comment by Anand Patil — March 9, 2009 @ 8:27 pm

    • I suppose that what you call the probability monad is the monad dist-m implemented in clojure.contrib.probabilities.dist, right? It’s a monad that represents finite probability distributions. It resembles Haskell’s PFP library, but it is fact simpler because it uses maps rather than lists for representing distributions.

      Comment by khinsen — March 12, 2009 @ 9:57 am

      • Not sure, honestly. I just know that if I google ‘probability monad’, there are a bunch of interesting-looking papers that I can’t follow past the introduction. :)

        Comment by Anand Patil — March 13, 2009 @ 9:46 am

        • I did a quick search and noted that the probability monad is indeed the one implemented in clojure.contrib.probabilities.dist. But I believe that it is much simpler than some of those discussions make it seem. I’ll put it on my to-do list for part 3 or 4 of the tutorial!

          Comment by khinsen — March 13, 2009 @ 10:22 am

    • Thank you for the Python tutorial. It is the best monad introduction I came across so far.

      Comment by RosenK — September 1, 2010 @ 9:19 pm

  5. This is great! I’m new to functional programming and this tutorial actually works for me (so far). Looking forward to part 3 and more ways to apply this to real-world situations.

    Comment by Radu Floricica — March 11, 2009 @ 10:29 pm

  6. [...] on to the more advanced aspects of monads, let’s recapitulate what defines a monad (see part 1 and part 2 for [...]

    Pingback by A monad tutorial for Clojure programmers (part 3) « On Clojure — March 23, 2009 @ 2:10 pm

  7. Jim Duey has published another monad tutorial for Clojure, which takes quite a different approach. Check it out at http://intensivesystems.net/tutorials/monads_101.html

    Comment by khinsen — April 16, 2009 @ 8:04 am

  8. [...] are way too many tutorials on monads on the web, though not many that are specific to Clojure (Konrad Hinsen’s tutorial being an obvious exception.) The argument as I’ve seen it described is that too many people [...]

    Pingback by Monads in Clojure: Monadic Tree Labelling with the State monad | Tim Martin's blog — November 11, 2009 @ 10:59 am

  9. [...] Good Monad Tutorials By gongli2000 These two tutorials on monads are pretty good. Tutorial 1 Tutorial 2 [...]

    Pingback by Good Monad Tutorials « My Year of Learning Functional Programming With Haskell — December 21, 2009 @ 4:42 pm

  10. [...] A monad tutorial for Clojure programmers (part 1) [...]

    Pingback by Clojure – Destillat #1 | duetsch.info - Open Source, Wet-, Web-, Software — January 27, 2010 @ 2:55 pm

  11. [...] Haskell. But the Clojure community is fortunate to have some very good monad tutorials. Check out Konrad Hinsen’s and Jim Duey’s [...]

    Pingback by bind, unit, and all that | Halfbaked Ideas — September 5, 2010 @ 11:37 pm

  12. Monads have moved in Clojure 1.3! Could you maybe update this post?

    One must import algo.monads via `lein deps`

    (defproject monads-test “1.0.0-SNAPSHOT”
    :description “Monads for fun”

    :dependencies [[org.clojure/clojure "1.3.0"]
    [org.clojure/algo.monads "0.1.0"]])

    Then, the use command is (use ‘clojure.algo.monads)

    Thank you!

    Comment by Tim Harper — March 19, 2012 @ 8:50 am

    • Right, Clojure has made some progress since I wrote this post. I just updated part 1 and I will continue with the remaining parts – thanks for the reminder!

      Comment by khinsen — March 20, 2012 @ 5:26 pm

  13. Read it again and it all makes a better sense to me now. Thanks.

    Comment by Jacek Laskowski — March 22, 2012 @ 10:47 pm

  14. [...] an email that A monad tutorial for Clojure programmers (part 1) was corrected with the latest changes around clojure.algo.monads. I almost immediately began [...]

    Pingback by Anonymous functions inside other function definitions for Clojure and monads nirvana | Japila :: verba docent, exempla trahunt — March 23, 2012 @ 9:10 pm

  15. [...] monad tutorial for Clojure programmers Part 1, Part 2, Part 3, Part [...]

    Pingback by Monad Monad Monad … | 따라쟁이 — September 1, 2012 @ 2:22 pm

  16. [...] even reported an issue to Konrad Hinsen (the author of the library), but when I read the article A Monad Tutorial For Clojure Programmers (Part 1) I knew I was [...]

    Pingback by Erroneous behavior of m-lift in clojure.algo.monads?! No, it’s only me…again! | Japila :: verba docent, exempla trahunt — December 12, 2012 @ 11:11 pm

  17. [...] can implement the Maybe monad in Clojure, but there’s less motivation to do so without the support of a static type checker. You could [...]

    Pingback by Affordance and Concision | Digital Digressions by Stuart Sierra — February 4, 2013 @ 1:29 pm

  18. […] 1.A Monad Tutorial For Clojure Programmers Part1  […]

    Pingback by Clojure Monad Resources — May 9, 2013 @ 2:29 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: