Re: Brian Beckman: The Zen of Stateless State - The State Monad - Part 2

Paul Abraham — Mon, 01 Jun 2009 16:04:54 GMT

// F# code

#light
open System
open System.Text

// State Monad

// label a binary tree to demonstrate state-monad
// implement non-monadically and monadically

type Tree<'a> =
| Leaf of string*'a
| Branch of Tree<'a>*Tree<'a>

// prints binary tree
// val printTree : Tree<'a> -> unit
let printTree(a)=
    let rec print(a,level)=
            let emptyString =new String(' ',level*2)
            printfn "%s" emptyString
            match a with
            |Leaf (sym,e)-> Console.Write(emptyString)
                            Console.Write("Leaf: "+sym+" ")
                            Console.Write(e.ToString())
                            Console.WriteLine()
            |Branch (left,right) -> Console.Write(emptyString)
                                    Console.WriteLine("Branch:");
                                    print(left,level+1)
                                    print(right,level+1)
    print(a,2)

//non-monad version
let rec labelTreeNM(t,s) =
         match t with
         |Leaf(sym,_)-> let l=Leaf(sym,s)
                        (s+1,l)
         |Branch(left,right)-> let(sL,nLeft)=labelTreeNM(left,s)
                               let(sR,nRight)=labelTreeNM(right,sL)
                               (sR+1,Branch(nLeft,nRight))

let demoTree=Branch(Leaf("A",0),Branch(Leaf("B",0),Branch(Leaf("C",0),Leaf("D",0))))

let (_,demoTreeNM)=labelTreeNM(demoTree,0)
//printTree(demoTreeNM)

// monad version
type State<'s,'a> = State of ('s ->'s*'a)

////type StateMonad =
// class
//    new : unit -> StateMonad
//    static member
//      Bind : sm:State<'a,'b> * f:('b -> State<'a,'c>) -> State<'a,'c>
//    static member Return : a:'a -> State<'b,'a>
// end

type StateMonad() =
        static member Return(a) = State (fun s -> s, a)
        static member Bind(sm,f) =
           State (fun s0 ->let (s1,a1)= match sm with
                                        | State h -> h s0
                           let (s2,a2)= match f a1 with
                                        | State h->h s1
                           (s2,a2))


// succinct functors for state monad

//val ( >>= ) : State<'a,'b> -> ('b -> State<'a,'c>) -> State<'a,'c>
let (>>=)m f = StateMonad.Bind( m, f)
//val Return : 'a -> State<'b,'a>
let Return =StateMonad.Return

// Tree<'a> -> State<int,Tree<int>>
let rec mkMonad(t)
          =match t with
           |Leaf(sym,_) -> State(fun s->((s+1),Leaf(sym,s)))
           |Branch(oldL,oldR)-> mkMonad(oldL)>>=
                                  (fun newL->mkMonad(oldR) >>=
                                              fun newR->Return(Branch(newL,newR)))

// monad version
let monadLabel(t,s)= let(nS,nT)= match mkMonad(t) with
                                  | State f-> f(s)
                     nT

let mTree=monadLabel(demoTree,0)
printTree(mTree)

Re: Brian Beckman: The Zen of Stateless State - The State Monad - Part 2

Allan Lindqvist — Mon, 15 Dec 2008 23:01:15 GMT

perhaps somewhat off-topic from what .tom wanted, but the wikipedia pages on monadology:
http://en.wikipedia.org/wiki/Monadology
and monism
http://en.wikipedia.org/wiki/Monism
was helpful to me to get my head around what the heck a monad "is" (it turns out its pretty hard to define :) )

http://en.wikipedia.org/wiki/Monad_(category_theory) and http://en.wikipedia.org/wiki/Monads_in_functional_programming are pretty good too :)

Re: Brian Beckman: The Zen of Stateless State - The State Monad - Part 2

Tom Kirby-Green — Thu, 04 Dec 2008 06:41:17 GMT

Can anyone (Brian?) suggest a good book(s) as a introduction to category theory? I'm really looking for just enough to underpin monad theory.

Comment Feed for Brian Beckman: The Zen of Stateless State - The State Monad - Part 2 (Going Deep on Channel 9)

Re: Brian Beckman: The Zen of Stateless State - The State Monad - Part 2

Re: Brian Beckman: The Zen of Stateless State - The State Monad - Part 2

Re: Brian Beckman: The Zen of Stateless State - The State Monad - Part 2