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.

1 komentarze :

Bartosz Milewski said...

This becomes much easier to understand if the types are explicit. Then it's obvious that you're dealing with the reader monad.

import Data.Map
import Control.Monad

type Env = Map String Integer

type ReadEnv a = Env -> a

number :: a -> ReadEnv a
number = return

add, multiply :: Num a => ReadEnv a -> ReadEnv a -> ReadEnv a
add = liftM2 (+)
multiply = liftM2 (*)

variable :: String -> ReadEnv Integer
variable = findWithDefault 0

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

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

result :: Integer
result = expressionTree environment

main = print result

Post a Comment