Sets Not Lists

Another flavor

Last time, I started looking at monads in Clojure using the sequence monad. I introduced m-result and m-bind for the sequence monad and mentioned the idea that a list can be thought of as a container. So what other containers might we base a monad on? The most obvious one is the set.

So what would the set monad look like?

Using the same functions as last time, except return sets rather than lists:

(defn half-double [n]
   #{(/ n 2) (* 2 n)})

(half-double 10)
=> #{5 20}

(defn inc-int [n]
   #{(+ 5 n) (+ 10 n)})

(inc-int 3)
=> #{8 13}

Now write do-both. It should take an integer, call half-double with it, then pass each item of the result to inc-int. Then it should collect all the return values from inc-int and flatten them into a single set.

Copying from last time and making a tweak, you should get:

(require 'clojure.set)
(defn do-both [n]
   (apply clojure.set/union
      (map inc-int
         (half-double n))))

(do-both 8)
=> #{9 14 21 26}

The structure m-bind for sequence-m and set-m are identical. In fact, m-bind for all monads follow that same pattern. That’s why in some monad tutorials, you’ll see monads explained in terms of three functions; result (or unit), map and flatten. I prefer the result and bind formulation myself.

Binding sets

So, copying m-bind for the sequence monad but tweaking to use union instead of concat, we get:

(defn m-bind [ns int-fn]
   (apply clojure.set/union
      (map int-fn ns)))

(defn do-both [n]
   (m-bind (half-double n) inc-int))

(do-both 8)
=> #{9 14 21 26}

And there we have m-bind for the set monad. The difference between sequence-m and set-m is that set-m will remove duplicates in its monadic values. For instance, with the m-bind from last time:

(m-bind (half-double 16) half-double)
=> (64 16 4 16)

But, using the m-bind defined above:

(m-bind (half-double 16) half-double)
=> #{64 4 16}

Result sets

With the container of the set-m being the set, the definition of m-result for set-m is very straightforward:

(defn m-result [x]
   #{x})

And there you have the set monad. It’s almost identical to the sequence monad, but not quite. Next time, I’ll show you how m-result and m-bind have to work together in order to be called a monad.

Jim Duey 04 February 2012
blog comments powered by Disqus