Brian Beckman: The Zen of Stateless State  The State Monad  Part 2
Description
This is another great conversation with astrophysicist and programming master Brian Beckman. Brian is one of the true human treasures of Microsoft. If you don't get mondas, this is a great primer. Even if you don't care about monadic data types, this is worth your time, especially if you write code for a living. This is part 2 of a 2 part series.
See part 1 here.
Below, you will find several exercises for generalizing the constructions further. Here are the source files you need for playing with these algorithms in visual studio or your favorite Haskell environment. Brian will monitor this thread so start your coding engines!!
Exercise 1: generalize over the type of the state, from int
to <S>, say, so that the SM type can handle any kind of
state object. Start with Scp<T> > Scp<S, T>, from
"labelcontent pair" to "statecontent pair".
Exercise 2: go from labeling a tree to doing a constrained
container computation, as in WPF. Give everything a
bounding box, and size subtrees to fit inside their
parents, recursively.
Exercise 3: promote @return and @bind into an abstract
class "M" and make "SM" a subclass of that.
Exercise 4 (HARD): go from binary tree to nary tree.
Exercise 5: Abstract from nary tree to IEnumerable; do
everything in LINQ! (Hint: SelectMany).
Exercise 6: Go look up monadic parser combinators and
implement an elegant parser library on top of your new
state monad in LINQ.
Exercise 7: Verify the Monad laws, either abstractly
(pencil and paper), or mechnically, via a program, for the
state monad.
Exercise 8: Design an interface for the operators @return
and @bind and rewrite the state monad so that it implements
this interface. See if you can enforce the monad laws
(associativity of @bind, left identity of @return, right
identity of @return) in the interface implementation.
Exercise 9: Look up the List Monad and implement it so that it implements the same interface.
Exercise 10: deconstruct this entire example by using
destructive updates (assignment) in a discipline way that
treats the entire CLR and heap memory as an "ambient
monad." Identify the @return and @bind operators in this
monad, implement them explicitly both as virtual methods
and as interface methods.
Download
Right click or Alt+Enter to download this episode
 High Quality MP4 (353.8 MB)
 Mid Quality MP4 (562.4 MB)
 High Quality WMV (442.9 MB)
 MP3 (11.3 MB)
 Low Quality MP4 (80.3 MB)
 Mid Quality WMV (89.9 MB)
 WMV (224.0 B)
The Discussion

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.

perhaps somewhat offtopic 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 
// F# code
#light
open System
open System.Text
// State Monad
// label a binary tree to demonstrate statemonad
// implement nonmonadically 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)
//nonmonad 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) 
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
~ProtoBytes