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

- Posted: Nov 20, 2008 at 1:38PM
- 4 comments

Loading user information from Channel 9

Something went wrong getting user information from Channel 9

Loading user information from MSDN

Something went wrong getting user information from MSDN

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

- Posted: Nov 20, 2008 at 1:38PM
- 4 comments

- To download, right click the file type you would like and pick “Save target as…” or “Save link as…”

- It's an easy way to save the videos you like locally.
- You can save the videos in order to watch them offline.
- If all you want is to hear the audio, you can download the MP3!

- If you want to view the video on your PC, Xbox or Media Center, download the High Quality MP4 file (this is the highest quality version we have available).
- If you'd like a lower bitrate version, to reduce the download time or cost, then choose the Medium Quality MP4 file.
- If you have a Windows Phone, iPhone, iPad, or Android device, choose the low or medium MP4 file.
- If you just want to hear the audio of the video, choose the MP3 file.

Right click “Save as…”

Concurrency is a problem that faces all developers as we move to the age of ManyCore processor architectures. Managing state is an important aspect of programming generally and for parallel programming especially. The great Brian
Beckman demonstrates three ways of labeling a binary tree with unique integer node numbers: (1) by hand, (2) non-monadically, but functionally, by threading an updating counter state variable through function arguments, and (3) monadically, by using a
partially generalized state-monad implementation to handle the threading via composition. Of course during this lesson from one of the masters of mathematical programming, we wind through various conversational contexts, but always stay true to the default
topic in a stateful monadic way (watch/listen to this piece to understand what this actually means )

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

"label-content pair" to "state-content pair".

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.

Below, you will find several exercises for generalizing the constructions further.

to <S>, say, so that the SM type can handle any kind of

state object. Start with Scp<T> --> Scp<S, T>, from

"label-content pair" to "state-content 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 n-ary tree.

**Exercise 5**: Abstract from n-ary 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.

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums, or Contact Us and let us know.

## Follow the discussion

Oops, something didn't work.

## What does this mean?

Subscriptions allow us send you email notifications when new content is added. You need to be signed in to Channel 9 to use this feature.## What does this mean?

Subscriptions allow us send you email notifications when new content is added.sign up for email notifications?

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

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

## Remove this comment

## Remove this thread

Close