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

Sign in to queue

The Discussion

  • User profile image
    tomkirbygre​en
    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.
  • User profile image
    aL_
    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 Smiley )

    http://en.wikipedia.org/wiki/Monad_(category_theory) and http://en.wikipedia.org/wiki/Monads_in_functional_programming are pretty good too Smiley
  • User profile image
    Paul555

     

    // 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)

     

     

  • User profile image
    ProtoBytes

    Look on YouTube.  Category theory is used in Linear Algebra and most importantly quantum mechanics.  You I suggest the Stanford University Open Course ware on Quantum Mechanics, there is also probability some good Linear Algebra open course wear at Stanford as well.  Quantum Mechanics II Lecture series starts with a good opener on linear algebra, as it pertains to QED.  All linear algebra operations are function operations of observable events.  It does get much into category theory and complex math, but it is the 'real' stuff that is observable and that is what the course shows how to design mathematical proofs of.  Here is the link to the courses:

     

    Lecture 1 | Modern Physics: Quantum Mechanics (Stanford) 

     

     

    General Link:

    http://www.youtube.com/user/StanfordUniversity

     

    Linerar Algerbra:

    Lecture 1 | Introduction to Linear Dynamical Systems 

     

     

    ~Proto-Bytes

Add Your 2 Cents