Map and Reduce Monad for Clojure... What about a Juxt Monad?

Question

Whilst learning Clojure, I've spent ages trying to make sense of monads - what they are and how we can use them.... with not too much success. However, I found an excellent 'Monads for Dummies' Video Series - http://vimeo.com/20717301 - by Brian Marik for Clojure

So far, my understanding of monads is that it is sort of like a macro in that it allows a set of statements to be written in a form that is easy to read - but monads are much more formalised. My observations are limited to two examples:

1. The Identity Monad (or the 'let' monad) taken from http://onclojure.com/2009/03/05/a-monad-tutorial-for-clojure-programmers-part-1/

The form that we wish to write is:

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

and the corresponding monad is

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

2. The Sequence Monad (or the 'for' monad) taken from http://onclojure.com/2009/03/06/a-monad-tutorial-for-clojure-programmers-part-2/

The form we wish to write is:

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

and the corresponding monad is

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

Monad Definitions in Clojure

Looking at the source, using clojure monads library - https://github.com/clojure/algo.monads:

user=>(use 'clojure.algo.monads)
nil

indentity monad:

user=> (source identity-m)
(defmonad identity-m
  [m-result identity
   m-bind   (fn m-result-id [mv f]
              (f mv))
  ])

sequence monad:

user=> (source sequence-m)
(defmonad sequence-m
   [m-result (fn m-result-sequence [v]
               (list v))
    m-bind   (fn m-bind-sequence [mv f]
               (flatten* (map f mv)))
    m-zero   (list)
    m-plus   (fn m-plus-sequence [& mvs]
               (flatten* mvs))
    ])

So my conclusion is that a monad is some sort of a generalised higher-order function that takes in an input-function and input-values, adds its own control logic and spits out a 'thing' that can be used in a 'domonad' block.

Question 1

So finally, to the questions: I want to learn how to write a monad and say I want to write a 'map monad' that imitates the 'map' form in clojure:

(domonad map-m
  [a [1 2 3 4 5]
   b [5 6 7 8 9]]
  (+ a b))

Should be equivalent to

(map + [1 2 3 4 5] [5 6 7 8 9])

and return the values

[6 8 10 12 14]

If I look at the source, it should give me something similar to identity-m and sequence-m:

user=> (source map-m)
(defmonad map-m
   [m-result ...
    m-bind   ...
    m-zero   ...
    m-plus   ...
    ])

Question 2

I also want to be able to define 'reduce-m' such that I can write:

(domonad reduce-m
  [a [1 2 3 4 5]]
  (* a))

this could potentially give me 1 x 2 x 3 x 4 x 5 = 120 or

(domonad reduce-m
  [a [1 2 3 4 5]
   b [1 2 3 4 5]]
  (+ a b))

will give me (1+2+3+4+5) + (1+2+3+4+5) = 30

Finally Would I also be able to write a 'juxt monad' that imitates the juxt function but instead of passing in values for binding, I pass in a set of functions. :

(domonad juxt-m
  [a #(+ % 1)
   b #(* % 2)]
  '([1 2 3 4 5] b a) )

gives

[ [2 2] [4 3] [6 4] [8 5] [9 6] ] 

Potentially, I could do all of those things with macros so I don't really know how useful these 'monads' will be or if they are even considered 'monads'... With all the resources on the internet, It seems to me that if I wanted to learn Monads properly, I have to learn Haskell and right now, learning another syntactic form is just too hard. I think I found some links that maybe relevant but it is too cryptic for me

Please can someone shed some light!

Answer 1

Your examples are not monads. A monad represents composable computational steps. In the trivial identity monad, the computational step is just an expression evaluation.

In the maybe monad, a step is an expression that may succeed or fail.

In the sequence monad, a step is an expression that produces a variable number of results (the elements of the sequence).

In the writer monad, a computational step is a combination of expression evaluation and log output. In the state monad, a computational step involves accessing and/or modifying a piece of mutable state.

In all these cases, the monad plumbery takes care of correctly combining steps. The m-result function packages a "plain" value to fit into the monadic computation scheme, and the m-bind function feeds the result of one computational step into the next computational step.

In (map + a b), there are no computational steps to be combined. There is no notion of order. It's just nested expression evaluation. Same for reduce.

Answer 2

Your questions are not a type of monads. They seems more like a syntactic sugar and that you can accomplish using macros and I won't even suggest you do that because map, reduce etc are simple functions and there is no need to make their interface complex.

The reason these cases are not monads because moands are sort of amplified values which wrap normal values. In map and reduce case the vector that you use doesn't needs to be amplified to allow it to work in map or reduce.

It would be helpful for you to try macroexpand on the domoand expressions. For ex: the sequence monad example should expand to something like:

(bind (result (range 5)) 
   (fn [a] 
      (bind (result (range a))
        (fn [b] (* a b))
   )))

Where the bind and result are functions defined in the sequence monad m-bind and m-result. So basically the vector expression(s) after the domand get nested and the expression(s) after the vector are used as it is in above case the (* a b) is called as it is (just that the a and b values are provided by the monad). In your example of map monad the vector expressions are supposed to be as it is and the last expression (+ a b) should somehow mean (map + a b) which is not what a monad is supposed to do.

Answer 3

I found some really good monads resources:

• http://www.clojure.net/tags.html#monads-ref (Jim Duey's Monads Guide, which really goes into the nitty gritty monad definitions)
• http://homepages.inf.ed.ac.uk/wadler/topics/monads.html#marktoberdorf (A whole load of papers on monads)
• http://vimeo.com/17207564 (A talk on category theory, which I half followed)

So from Jim's Guide - http://www.clojure.net/2012/02/06/Legalities/ - he gives three axioms for definition of 'bind-m' and 'reduce-m' functions:

Identity The first Monad Law can be written as

(m-bind (m-result x) f) is equal to (f x)

What this means is that whatever m-result does to x to make it into a monadic value, m-bind undoes before applying f to x. So with regards to m-bind, m-result is sort of like an identity function. Or in category theory terminology, its unit. Which is why sometimes you’ll see it named ‘unit’.

Reverse Identity The second Monad Law can be written as

(m-bind mv m-result) is equal to mv where mv is a monadic value.

This law is something like a complement to the first law. It basically ensures that m-result is a monadic function and that whatever m-bind does to a monadic value to extract a value, m-result undoes to create a monadic value.

Associativity The third Monad Law can be written as

(m-bind (m-bind mv f) g) is equal to (m-bind mv (fn [x] (m-bind (f x) g))) where f and g are monadic functions and mv is a monadic value.

What this law is saying is that it doesnt matter whether the f is applied to mv and then g is applied to the result, or whether a new monadic function is created out of a composition of f and g which is then applied to mv. In either order, the resulting value is the same monadic value. Stated another way, m-bind is left and right associative.

In http://www.clojure.net/2012/02/04/Sets-not-lists/ he gives an monad that takes sets as inputs instead of taking lists. Will work through all the examples...