Tuesday, June 28, 2011

WTF is a Monad by Robert C. Martin in F#

I have read some material describing Computation Expressions and knew computation expressions are the F# implementation of monads, but I did know why one should use a monad.

A few days ago saw the video of presentation by Robert C. Martin (Uncle Bob) at the Norwegian Developers Conference called “WTF is a Monad” and now it makes sense to me.

It is a proven way of solving problems. If you:

  • have a problem in one domain
  • you can transform it to another domain
  • solve the problem in the other domain
  • and can transform it back

you have a solution.

I have translated some of the code of the presentation to F#. I tried to stay as close to the original code as possible and did not do much refactoring. I skipped the last two examples (distributions an state).

Update: I did not implement the examples that required lift. I have not figured out how to do that. I have created the lift myself (details: http://bugsquash.blogspot.com/2010/12/notes-on-haskell-functors-and-f.html)

I like to thank Robert for the permission to share the code. Feel free to add improvements in the comments.

//Non-Monadic dots

let dotsToN (d:string) =

let result1 = dotsToN "....."

let nToDots (n:int) =
new string('.', n)

let result2 = nToDots 5

let addDots da db =
let a = dotsToN da
let b = dotsToN db
nToDots (a+b)

let result3 = addDots "..." "..."

//Monadic dots

let dotResult = nToDots

let dotBind d (f:int -> string) =
d |> dotsToN |> f

let addDots' da db =
dotBind da (fun a ->
dotBind db (fun b ->
dotResult (a + b)))

let result4= addDots' "..." "..."

type dotBuilder()=
member x.Bind(d,(f:int -> string)) = d |> dotsToN |> f
member x.Return(n) = new string('.', n)

let dot = new dotBuilder()

let addDots'' da db =
dot { let! x = da
let! y = db
return x + y

let result5= addDots'' "..." "..."

let multiplyDots da db =
dot { let! x = da
let! y = db
return x*y

let result6= multiplyDots "..." "..."

let dcd dt du =
dot { let! tens = dt
let! units = du
return (10 * tens + units)

let result7= dcd "..." "....."

// In Clojure the monad gets the lift for free
// In F# we have to create it ourselves
// More info: http://bugsquash.blogspot.com/2010/12/notes-on-haskell-functors-and-f.html --

let liftDots_1 f a1 =
dot {
let! x1 = a1
return f x1

let liftDots_2 f a1 a2 =
dot {
let! x1 = a1
let! x2 = a2
return f x1 x2

let liftDots_4 f a1 a2 a3 a4 =
dot {
let! x1 = a1
let! x2 = a2
let! x3 = a3
let! x4 = a4
return f x1 x2 x3 x4

let substractDots = liftDots_2 (-)

let result7a= substractDots "....." ".."

let mean4 a b c d = (a+b+c+d)/4

let dmean4 = liftDots_4 mean4

let result7b= dmean4 "..." ".." "..." "...."

//complex number (inspection)

open System.Numerics

let c_0 = Complex.Zero
let c_1 = Complex.One
let c_i = Complex.ImaginaryOne

type complexBuilder()=
member b.Return(x:float) = new Complex(x,0.0)
member b.Bind((c:Complex),(f:float -> Complex)) =
if c.Imaginary = 0.0 then
f c.Real
failwithf "Imaginary"

let complex = new complexBuilder()

let addComplex c1 c2 =
complex { let! x = c1
let! y = c2
return x + y

let result8= addComplex c_1 c_1;;
let result9= addComplex c_1 c_i;; //System.Exception: Imaginary
let result10= addComplex c_i c_i;; //System.Exception: Imaginary


type noNullBuilder()=
member b.Return(mv) = mv
member b.Bind(mv,f) = if (mv = null) then null else f mv

let nuNull = new noNullBuilder()

// int can not be null in .Net

let fragile (a:string) (b:string) (c:string) =
if (a= null||b=null||c=null)
a + b + c

let result11 = fragile "a" "b" "c"
let result12 = fragile "a" null "c" //"CRASH"

let safeFragile (a:string) (b:string) (c:string) =
nuNull { let! x = a
let! y = b
let! z = c
return x + y + z

let result13 = safeFragile "a" "b" "c"
let result14 = safeFragile "a" null "c" //val result14 : string = null

let l_a = [1;2;3]
let l_b = [4;5;6]

let addList = seq {for a in l_a do
b in l_b do
}|> Seq.toList

let multList = seq {for a in l_a do
b in l_b do
}|> Seq.toList

//helper for the demo
let flatten l =
let rec flatten' l result =
match l with
|[] -> result
|h::t -> flatten' t (h@result)
flatten' (l|>List.rev) []

let result15 = flatten [[1;2;3];[7;8;9]]

type listBuilder()=
member b.Return(v) = [v]
member b.Bind(mv,f) = mv |> List.map f |> flatten

let list = new listBuilder()

let addList' a b = list {
let! x = a
let! y = b
return x + y

let result16 = addList' l_a l_b

let multList' a b = list {
let! x = a
let! y = b
return x * y

let result17 = multList' l_a l_b

//distribution example see Expert F# of Don Syme page 239..244
//state http://fsharpcode.blogspot.com/2008/12/f-state-monad-type-state-state-state-of.html


Mauricio Scheffer said...

I haven't seen the presentation so I don't know what Robert does with lift, but I can tell you that lift (liftM when restricted to monads) is just a 'map' function. You can trivially translate the Haskell definition of liftM and use it in F# ... you can't define it generically as in Haskell though.

Mauricio Scheffer said...

BTW the link to by blog post isn't right... and now that I re-read it I noticed I already defined lift there :-)
If you have trouble with this I recommend posting a question on stackoverflow...

Piet Amersfoort said...

Thanks Mauricio for the comments.
I have updated the code and the link.

Total Pageviews