3 September 2014

9 lines that made me learn monads

Some time ago I saw this programing languages comparison based on a small task. The task is to implement evaluation system for simple expressions: addition and multiplication of numbers and variables. Most solutions (regardless of the language) look like the first one:
(use '[clojure.core.match :only [match]])
(defn evaluate [env [sym x y]]
  (match [sym]
    ['Number]   x
    ['Add]      (+ (evaluate env x) (evaluate env y))
    ['Multiply] (* (evaluate env x) (evaluate env y))
    ['Variable] (env x)))

(def environment {"a" 3, "b" 4, "c" 5})
(def expression-tree '(Add (Variable "a") (Multiply (Number 2) (Variable "b"))))
(def result (evaluate environment expression-tree)) 
It boils down to defining 4 types of expressions, each of which receives subexpressions and the environment and later passes the environment to the subexpressions. Easy, right? There are also a few solutions that avoid passing the environment. Instead they have 'evaluate' function that preprocesses the expression tree and later evaluates it without the environment at all. For example they replace variables with their values upfront.

And then I saw this:
import Data.Map
import Control.Monad

number   = return
add      = liftM2 (+)
multiply = liftM2 (*)
variable = findWithDefault 0

environment = fromList [("a",3), ("b",4), ("c",7)]

expressionTree = add (variable "a") (multiply (number 2) (variable "b"))

result = expressionTree environment
And I was wondering how does it work. Where the hell is environment passing or 'evaluate' function?! Can you write such code? If not, it's time to learn monads.