On Clojure

March 6, 2009

A monad tutorial 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 monad. In this part, I will continue with the sequence monad, which will be the occasion to explain the role of the mysterious m-result function. I will also show a couple of useful generic monad operations.

One of the most frequently used monads is the sequence monad (known in the Haskell world as the list monad). It is in fact so common that it is built into Clojure as well, in the form of the for form. Let's look at an example:

(for [a (range 5)
      b (range a)]
  (* a b))

A for form resembles a let form not only syntactically. It has the same structure: a list of binding expressions, in which each expression can use the bindings from the preceding ones, and a final result expressions that typically depends on all the bindings as well. The difference between let and for is that let binds a single value to each symbol, whereas for binds several values in sequence. The expressions in the binding list must therefore evaluate to sequences, and the result is a sequence as well. The for form can also contain conditions in the form of :when and :while clauses, which I will discuss later. From the monad point of view of composable computations, the sequences are seen as the results of non-deterministic computations, i.e. computations that have more than one result.

Using the monad library, the above loop is written as

(domonad sequence-m
  [a (range 5)
   b (range a)]
  (* a b))

Since we alread know that the domonad macro expands into a chain of m-bind calls ending in an expression that calls m-result, all that remains to be explained is how m-bind and m-result are defined to obtain the desired looping effect.

As we have seen before, m-bind calls a function of one argument that represents the rest of the computation, with the function argument representing the bound variable. To get a loop, we have to call this function repeatedly. A first attempt at such an m-bind function would be

(defn m-bind-first-try [sequence function]
  (map function sequence))

Let's see what this does for our example:

(m-bind-first-try (range 5)  (fn [a]
(m-bind-first-try (range a)  (fn [b]
(* a b)))))

This yields (() (0) (0 2) (0 3 6) (0 4 8 12)), whereas the for form given above yields (0 0 2 0 3 6 0 4 8 12). Something is not yet quite right. We want a single flat result sequence, but what we get is a nested sequence whose nesting level equals the number of m-bind calls. Since m-bind introduces one level of nesting, it must also remove one. That sounds like a job for concat. So let's try again:

(defn m-bind-second-try [sequence function]
  (apply concat (map function sequence)))

(m-bind-second-try (range 5)  (fn [a]
(m-bind-second-try (range a)  (fn [b]
(* a b)))))

This is worse: we get an exception. Clojure tells us:

java.lang.IllegalArgumentException: Don't know how to create ISeq from: Integer

Back to thinking!

Our current m-bind introduces a level of sequence nesting and also takes one away. Its result therefore has as many levels of nesting as the return value of the function that is called. The final result of our expression has as many nesting values as (* a b) - which means none at all. If we want one level of nesting in the result, no matter how many calls to m-bind we have, the only solution is to introduce one level of nesting at the end. Let's try a quick fix:

(m-bind-second-try (range 5)  (fn [a]
(m-bind-second-try (range a)  (fn [b]
(list (* a b))))))

This works! Our (fn [b] ...) always returns a one-element list. The inner m-bind thus creates a sequence of one-element lists, one for each value of b, and concatenates them to make a flat list. The outermost m-bind then creates such a list for each value of a and concatenates them to make another flat list. The result of each m-bind thus is a flat list, as it should be. And that illustrates nicely why we need m-result to make a monad work. The final definition of the sequence monad is thus given by

(defn m-bind [sequence function]
  (apply concat (map function sequence)))

(defn m-result [value]
  (list value))

The role of m-result is to turn a bare value into the expression that, when appearing on the right-hand side in a monadic binding, binds the symbol to that value. This is one of the conditions that a pair of m-bind and m-result functions must fulfill in order to define a monad. Expressed as Clojure code, this condition reads

(= (m-bind (m-result value) function)
   (function value))

There are two more conditions that complete the three monad laws. One of them is

(= (m-bind monadic-expression m-result)
   monadic-expression)

with monadic-expression standing for any expression valid in the monad under consideration, e.g. a sequence expression for the sequence monad. This condition becomes clearer when expressed using the domonad macro:

(= (domonad
     [x monadic-expression]
      x)
   monadic-expression)

The final monad law postulates associativity:

(= (m-bind (m-bind monadic-expression
                   function1)
           function2)
   (m-bind monadic-expression
           (fn [x] (m-bind (function1 x)
                           function2))))

Again this becomes a bit clearer using domonad syntax:

(= (domonad
     [y (domonad
          [x monadic-expression]
          (function1 x))]
     (function2 y))
   (domonad
     [x monadic-expression
      y (m-result (function1 x))]
     (function2 y)))

It is not necessary to remember the monad laws for using monads, they are of importance only when you start to define your own monads. What you should remember about m-result is that (m-result x) represents the monadic computation whose result is x. For the sequence monad, this means a sequence with the single element x. For the identity monad and the maybe monad, which I have presented in the first part of the tutorial, there is no particular structure to monadic expressions, and therefore m-result is just the identity function.

Now it's time to relax: the most difficult material has been covered. I will return to monad theory in the next part, where I will tell you more about the :when clauses in for loops. The rest of this part will be of a more pragmatic nature.

You may have wondered what the point of the identity and sequence monads is, given that Clojure already contains fully equivalent forms. The answer is that there are generic operations on computations that have an interpretation in any monad. Using the monad library, you can write functions that take a monad as an argument and compose computations in the given monad. I will come back to this later with a concrete example. The monad library also contains some useful predefined operations for use with any monad, which I will explain now. They all have names starting with the prefix m-.

Perhaps the most frequently used generic monad function is m-lift. It converts a function of n standard value arguments into a function of n monadic expressions that returns a monadic expression. The new function contains implicit m-bind and m-result calls. As a simple example, take

(def nil-respecting-addition
  (with-monad maybe-m
    (m-lift 2 +)))

This is a function that returns the sum of two arguments, just like + does, except that it automatically returns nil when either of its arguments is nil. Note that m-lift needs to know the number of arguments that the function has, as there is no way to obtain this information by inspecting the function itself.

To illustrate how m-lift works, I will show you an equivalent definition in terms of domonad:

(defn nil-respecting-addition
  [x y]
  (domonad maybe-m
    [a x
     b y]
    (+ a b)))

This shows that m-lift implies one call to m-result and one m-bind call per argument. The same definition using the sequence monad would yield a function that returns a sequence of all possible sums of pairs from the two input sequences.

Exercice: The following function is equivalent to a well-known built-in Clojure function. Which one?

(with-monad sequence-m
  (defn mystery
    [f xs]
    ( (m-lift 1 f) xs )))

Another popular monad operation is m-seq. It takes a sequence of monadic expressions, and returns a sequence of their result values. In terms of domonad, the expression (m-seq [a b c]) becomes

(domonad
  [x a
   y b
   z c]
  '(x y z))

Here is an example of how you might want to use it:

(with-monad sequence-m
   (defn ntuples [n xs]
      (m-seq (replicate n xs))))

Try it out for yourself!

The final monad operation I want to mention is m-chain. It takes a list of one-argument computations, and chains them together by calling each element of this list with the result of the preceding one. For example, (m-chain [a b c]) is equivalent to

(fn [arg]
  (domonad
    [x (a arg)
     y (b x)
     z (c y)]
    z))

A usage example is the traversal of hierarchies. The Clojure function parents yields the parents of a given class or type in the hierarchy used for multimethod dispatch. When given a Java class, it returns its base classes. The following function builds on parents to find the n-th generation ascendants of a class:

(with-monad sequence-m
  (defn n-th-generation
    [n cls]
    ( (m-chain (replicate n parents)) cls )))

(n-th-generation 0 (class []))
(n-th-generation 1 (class []))
(n-th-generation 2 (class []))

You may notice that some classes can occur more than once in the result, because they are the base class of more than one class in the generation below. In fact, we ought to use sets instead of sequences for representing the ascendants at each generation. Well... that's easy. Just replace sequence-m by set-m and run it again!

In part 3, I will come back to the :when clause in for loops, and show how it is implemented and generalized in terms of monads. I will also explain another monad or two. Stay tuned!

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.

March 4, 2009

dorun, doseq, doall

Filed under: General — cosmin @ 4:34 am

It’s about time that I started writing some posts on this blog. I’ll start with something small, by talking about the difference between dorun, doseq and doall and how to easily remember what each one of them does. All of them are supposed to force evaluation of lazy sequences. At least to me it was not obvious from the name of these functions and I had to constantly go back to the docstrings at first.

doall

doall forces the evaluation of the lazy sequence and it retains the head, causing the entire seq to live in memory. Useful when you want to immediately force evaluation of something like map. I use the “all” part of doall to help me remember that it keeps all the items of the seq in memory.

dorun

Use dorun when you just want the side effects of computing the lazy sequence, but you don’t care about the items in the sequence itself. But be careful when you see yourself using (dorun (map ….. )), you should probably use doseq instead. I use the “run” part of dorun to help me remember that it only runs over the seq for side effects, without keeping anything.

doseq

To me doseq has more in common with for than with doall or dorun. Since in Clojure for is used for lazy list-comprehension, doseq fulfills the role of something like “for … in …” or “foreach” from other languages. It takes the same arguments that for does, but it runs immediately and it doesn’t collect the results. I really feel that doseq needs a better name so I don’t have a good way to remember what it does just by looking at its name.


December 16, 2008

New Blog

Filed under: Administrative — cosmin @ 8:30 pm

I’m relatively new to Clojure and my personal blog has been primarily focused on Python, so instead of blogging there about Clojure I decided to start this blog. I also hope to find a couple of other people interested in writing about Clojure since having multiple people writing will make for a more interesting and alive blog. If you’re interested in writing for this blog please send me an email. Also, if you happen to have your own blog about Clojure please let me know so I can add it to the Related section. Most likely readers of this blog will also find your site interesting.

« Newer Posts

The Shocking Blue Green Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.