Monads in Clojure

One of my hobby projects over the last months has been the exploration of monads. Monads are packages consisting of a data structure and associated control structures that are used as abstractions in functional programming. They were popularized by the Haskell language, where they play a central role in introducing side effects (such as I/O) in a controlled way into a language that is otherwise purely functional.

Since I was also exploring Clojure, an interesting new dialect of Lisp that strongly encourages a purely functional programming style (but doesn’t enforce it), I decided to explore monads by writing a monad library for Clojure. My experience is that monads are quite useful in Clojure as well, and that once you get used to monads, you see occasions for using them almost everywhere. If you have been hesitating to tackle monads seriously, I can only encourage you to go on!

I have also written a monad tutorial for Clojure programmers, which I published on the OnClojure blog. It consists of four parts:

  1. Part 1 introduces the concept of monads and illustrates it with the identity and maybe monads.
  2. Part 2 explains the importance of m-result using the sequence monad as an example. It also covers the monad laws.
  3. Part 3 is about m-zero and m-plus, and explains the state monad.
  4. Part 4 covers the probability monad and monad transformers.

I hope that this tutorial facilitates a first contact with monads for those who are more familiar with Lisp syntax than with Haskell syntax.

About these ads
Explore posts in the same categories: Programming

5 Comments on “Monads in Clojure”

  1. Nathan Says:

    Hi Konrad,

    I’ve been using your excellent Monad library. Firstly thank you for putting it together and making it available, much appreciated. I have a question regarding Monad use.

    I have a list (or more generally a sequence) of things. I need to parse this sequence into another sequence. Depending on context three item in the input sequence might translate to one item in the output, subsequently the next two items might translate to another output item. The amount consumed depends on context and the items in question. Also as I transverse the input sequence I accrue state which is used in subsequent parsing operations.

    This seems like a candidate for the state-m Monad. The issue is that all examples I’ve seen so far consume a fixed number of items from the state and return them. I want to consume ALL the input sequence and return a sequence of the results.

    In other words I want to recursively re-apply the same state-m Monad to its own result building a sequence of outputs. Is there an idiomatic way to do this? I’m relatively new to Monads so apologies for my clumsy definitions.

    Any help appreciated,

    Regards,

    Nathan

    • khinsen Says:

      Monads are all about composing computational steps. So the questions you should ask yourself are: What are the steps I want to compose? Do I need composition sufficiently often that it’s worth using a monad? What the is specificity of the composition that lets me pick one monad over another?

      As an example, consider standard monadic text parsing. You have basic parsing steps that recognize single characters, which you compose to make parsers that recognize words, which in turn you can compose to get a parser for phrases. It’s clear that composition is important here, so it’s worth looking at monads. The composition of several steps implies handling the input stream of the parser and combining their outputs. That’s not any of the standard monads, but it’s one worth defining.

      Did you read this blog post about monadic parsing in Clojure? It discusses the right kind of monad, which may be all you need. If not, it may point you in the right direction.

      • Nathan Says:

        Hi Konrad,

        Thanks for your prompt reply. I actually read the blog post you referred to before I posted here, but I couldn’t see that it answered my question, maybe I didn’t look hard enough.

        I understand you can compose Monads together to build more complex Monads. Lets say you’ve built your Monad to retrieve a phrase from a text block.Lets also assume that the Monad returns a data structure containing a phrase and the unconsumed remainder of the text block.

        My question is how would you use that Monad to pull ALL the phrases from a book. To do this you would need repeated application of the Phrases Monad. Naively I would probably use the Monad with the iterate function, but is there a better way to do this? It must be a common idiom to repeatedly apply the same Monad to a sequence and collect up the results as they’re produced.

        Regards,

        Nathan

  2. khinsen Says:

    The answer is provided by the functions many and many1 in Andrew Brehaut’s post. The idea is to call the phrase matcher recursively until it fails. It is bound to fail at the end of the input, so it does what you want – except that it can fail earlier, of course. Note that in Andrew’s code, failure is handled by the monad’s m-bind function behind the scenes, so you don’t see it explicitly in the definitions of many and many1.

    A plain iterate won’t work because it applies a function to the result of an earlier call to the same function. You could of course implement an iterative parser application using iterate, but it takes a bit more code to work correctly.

    • Nathan Says:

      Hi Konrad,

      Right you are! Thanks, you’ve answered my question. Thanks for taking the time out to reply. Hopefully in time I’ll be able to help others out as well :)

      Regards,

      Nathan


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


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: