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

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

Bent Rasmussen — Wed, 26 Aug 2009 19:12:58 GMT

Thanks for including the visio diagrams. Will print them and look at the code...

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

brianbec — Mon, 24 Aug 2009 02:05:05 GMT

This looks very nice. I don't see any ways right off the top of my head to make it shorter (shorter is almost always better :)

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

Ryan Riley — Sun, 23 Aug 2009 22:49:13 GMT

Here's my solution to exercise 2 using F#:

The type defs:

type Rect =

{ Height: float;

Width: float;

Top: float;

Left: float }

with override r.ToString() = String.Format("Height: {0}, Width: {1}, Top: {2}, Left: {3}", r.Height, r.Width, r.Top, r.Left)

(* StateBuilder Bounder *)

let boundTree tree seed leftUpdater rightUpdater =

let rec labelTree t updater =

match t with

| Leaf(c) -> state { let! s = getState

let (next, curr) = updater s

do! setState next

return Leaf(curr, c) }

| Branch(l, r) -> state { let! l = labelTree l leftUpdater

let! r = labelTree r rightUpdater

return Branch(l, r) }

exec (labelTree tree leftUpdater) seed

type Rect =

{ Height: float;

Width: float;

Top: float;

Left: float }

with override r.ToString() = String.Format("Height: {0}, Width: {1}, Top: {2}, Left: {3}", r.Height, r.Width, r.Top, r.Left)

type Tree<'a> =

| Leaf of 'a

| Branch of Tree<'a> * Tree<'a>

// The show method already takes into account the tuples,

// unlike the show method that is overloaded in the C# version.

let show tree =

let rec printTree tree level =

let spacing = new string(' ', level * indentation)

printf "%A" spacing

match tree with

| Leaf(label, contents) ->

let labelString = label.ToString()

printfn "Leaf: %s, Contents: %A" labelString contents

| Branch(left, right) ->

printfn "Branch: "

printTree left (level + 1)

printTree right (level + 1)

printTree tree 0

The state monad builder:

(* StateMonad *)

type State<'S, 'a> = State of ('S -> 'S * 'a)

(* StateBuilder Bounder *)

let boundTree tree seed leftUpdater rightUpdater =

let rec labelTree t updater =

match t with

| Leaf(c) -> state { let! s = getState

let (next, curr) = updater s

do! setState next

return Leaf(curr, c) }

| Branch(l, r) -> state { let! l = labelTree l leftUpdater

let! r = labelTree r rightUpdater

return Branch(l, r) }

exec (labelTree tree leftUpdater) seed

let eval sm s =

match sm with

| State f -> f s |> fst

let exec sm s =

match sm with

| State f -> f s |> snd

The demo tree:

let demoTree = Branch(

Leaf("A"),

Branch(

Leaf("B"),

Leaf("C")),

Leaf("D")))

The updaters and execution code:

let leftBounder =

fun (depth, rect) -> let newDepth = depth + 1.0

let multiplier = 2.0 * newDepth

( (newDepth,

{ Height = rect.Height

Width = rect.Width / multiplier

Top = rect.Top

Left = rect.Left + rect.Width / multiplier }),

{ Height = rect.Height

Width = rect.Width / multiplier

Top = rect.Top

Left = rect.Left } )

let rightBounder =

fun (depth, rect) -> let newDepth = depth - 1.0

( (newDepth,

{ Height = rect.Height

Width = rect.Width * 2.0

Top = rect.Top

Left = rect.Left + rect.Width }),

rect )

let initialDepth = 0.0

let initialRect = { Height = 100.0

Width = 100.0

Top = 0.0

Left = 0.0 }

let ex2Seed = (initialDepth, initialRect)

printfn "Bound tree to rects"

let bTree = boundTree demoTree ex2Seed leftBounder rightBounder

show bTree

This works, but I imagine there must be a better way. I'm open to suggestions.

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

Ryan Riley — Fri, 31 Jul 2009 22:57:34 GMT

"So... any solutions available for the exercises above?" <| Geez! Maybe I should look to see if pages of comments exist before displaying my stupidity to the world. Great work holoed!

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

Charles — Mon, 15 Dec 2008 23:53:55 GMT

Indeed. I bet Brian's excited to dig into the Continuation monad... :)
C

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

Allan Lindqvist — Mon, 15 Dec 2008 22:48:10 GMT

woah holoed you Are the man :S i havent had time to write out the excercises yet(but ive tried to solve them in my head :) ), 8 people (out of 35) are beeling let go from where i work and i have to take over like 2 positions plus my own :S nut no more excuses :) i really really enjoyed this interview+excercises :)

please pretty please charles and brian, do intervies like this about the other monads as well :)

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

Edmondo Pentangelo — Sat, 13 Dec 2008 19:58:36 GMT

// The List Monad in F#

#light

type List<'a> = List of ('a -> 'a list)

type ListMonad() =
    member o.Bind(  (m:'a list), (f: 'a -> 'b list) ) = List.concat( List.map (fun x -> f x) m )
    member o.Return(x) = [x]

let list = ListMonad()

let cartesian = list { let! x = [1..3]
                       let! y = [4..6]
                       return (x,y) }

printf "%A" cartesian

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

Edmondo Pentangelo — Sat, 06 Dec 2008 19:47:04 GMT

Thank you Charles :)

I've updated my profile:

http://channel9.msdn.com/Niners/holoed/

Edmondo Pentangelo

Deutsche Bank

London, UK

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

Edmondo Pentangelo — Sat, 06 Dec 2008 19:43:06 GMT

Thank you Brian :)

I love this stuff. I've been an OO developer for a long time and it is only thank to F# and videos like yours that I started appreciating the beauty of functional ideas. I think my coding at work is improving as a result of this exposure.

I plan to have exercise 10 ready before the end of the year ;)))

HoloEd

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

Charles — Fri, 05 Dec 2008 05:31:22 GMT

Indeed! Hey, holoed. Who are you, man? :)
C

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

brianbec — Fri, 05 Dec 2008 01:34:13 GMT

Absolutely heroic!

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

brianbec — Fri, 05 Dec 2008 01:33:44 GMT

This is true, Ben, but suppose you could think of the entire state of the CLR & heap memory as being the State that gets passed around inside monads of type s -> (s, v)? Could you build up your whole program as "@bind" compositions of things that take "the state of the entire CLR" as argument and return pairs of ("state of the entire CLR", "some values I care about")? This isn't a rhetorical question, I'm not sure I know how to do it :) But it is the question I'm posing to niners in Exercise 10. Of course, that "state of the entire CLR" is just a fictional state object, so not heavyweight to "pass around." It's the ambient monad, I think. But not sure how to guarantee that nothing but the function active at a given moment can modify that state, even if it is possible.

(btw, in my Caltech days, exams and homework problem sets routinely contained questions the professors didn't know how to answer: open research questions i.o.w.)

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

Charles — Wed, 03 Dec 2008 04:33:47 GMT

Nice work (all around)! Thanks for sharing.
C

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

Edmondo Pentangelo — Wed, 03 Dec 2008 02:54:02 GMT

//F# Monadic Parser - Calculator Example :))) 

// Grammar
//expr ::= expr addop term j term
//term ::= term mulop factor j factor
//factor ::= digit j ( expr )
//digit ::= 0 j 1 j : : : j 9
//addop ::= + j -
//mulop ::= * j /

let addOp = parser { let! _ = symb "+" 
                     return (+) } +++ parser { let! _ = symb "-" 
                                               return (-) } 
let mulOp = parser { let! _ = symb "*" 
                     return (*) } +++ parser { let! _ = symb "/" 
                                               return (/) }  
let digit = parser { let! x = token (sat (fun ch -> Char.IsDigit(ch)))
                     return Char.GetNumericValue(x) - Char.GetNumericValue('0') }

let rec expr   = chainl1 term addOp
and     term   = chainl1 factor mulOp
and     factor = digit +++ parser { let! _ = symb "("
                                    let! n = expr
                                    let! _ = symb ")"
                                    return n }
                                    
let parse s = match apply expr s  with
              | [] -> failwith "failed to parse"
              | (ret, _)::xs -> ret

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

Edmondo Pentangelo — Wed, 03 Dec 2008 02:51:17 GMT

// F# Parsers combinators :))

//A parser which successfully consumes the first character
//if the argument string is non-empty, and fails otherwise.
let item = Parser (fun cs -> match cs with
                             | "" -> []
                             | cs -> [cs.[0], cs.Substring(1)])
                            
//A combinator sat that takes a predicate, and yields a parser that
//consumes a single character if it satisfies the predicate, and fails otherwise.
let sat p = parser { let! c = item
                     if p c then
                      return c }
                      
//A parser for specific characters
let char c = sat (fun s -> c = s)
                                            
//Parse a specific string
let rec stringp s = match s with
                    | "" -> parser { return [] }
                    | xs -> parser { let! c = char xs.[0]
                                     let! cs = stringp (xs.Substring(1))
                                     return c::cs }                        
                                                          
//The many combinator permits zero
//or more applications of p, while many1 permits one or more.
let rec many1 p = parser { let! x = p
                           let! xs = many p
                           return (x::xs) }
and many p = (many1 p) +++ parser { return [] }

                            
//Parse repeated applications of a parser p, separated by applications of a parser
//op whose result value is an operator that is assumed to associate to the left,
//and which is used to combine the results from the p parsers.
and chainl1 p op = 
    let rec rest a = parser { let! f = op
                              let! b = p
                              return! rest (f a b) } +++ parser { return a }
    parser { let! a = p
             return! rest a } 
           
//Parse a string of spaces.
let space = many (sat (fun s -> Char.IsWhiteSpace s))

//Parse a token using a parser p, throwing away any trailing space.
let token p = parser { let! a = p
                       let! _ = space
                       return a }

//Parse a symbolic token:
let symb cs = token (stringp cs)

//Apply a parser p, throwing away any leading space:
let apply p = extract (parser { let! _ = space
                                let! r = p
                                return r })

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

Edmondo Pentangelo — Wed, 03 Dec 2008 02:48:34 GMT

// F# Parser Monad (http://www.cs.nott.ac.uk/~gmh/pearl.pdf)

type Parser<'a> = Parser of (string ->('a * string) list)

let extract(Parser(f)) = f

type ParserMonad() = 
        member b.Bind(p, f) = Parser (fun cs -> 
                                                let r = extract(p) cs
                                                let r' = List.map (fun (a,cs') -> extract(f a) cs') r
                                                List.concat r')
        member b.Return(x) = Parser (fun cs -> [x,cs])
        member b.Zero() = Parser (fun cs -> [])


let (++) p q = Parser(fun cs -> List.append (extract p cs) (extract q cs))
let (+++) p q = Parser(fun cs -> match (extract(p ++ q) cs) with
                                 | [] -> []
                                 | x::xs -> [x])

let parser = ParserMonad()

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

benyaboy — Wed, 03 Dec 2008 00:48:48 GMT

Brian, I think I get it now. I was thrown off by the example. It makes sense that you need to copy the state around to avoid side affects. I guess the my practical (and procedural) side is too worried that the size of the state and the overhead of copying it over and over is too large for the scenarios I deal with.

I also agree with what you said in the video about when the project is intricate enough you end up having to deal with all these nasty problems with state dependency, locking, etc.

Ben

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

brianbec — Mon, 01 Dec 2008 04:27:44 GMT

holoed, this is fantastic! +1000 pts :)

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

Edmondo Pentangelo — Mon, 01 Dec 2008 01:16:13 GMT

//LINQ State Monad implementation

public delegate StateContentPair<T> StateMonad<T>(int state);

public static class LinqStateMonad
{
    public static StateMonad<U> Select<T, U>(this StateMonad<T> p, Func<T, U> selector)
    {
        return state => new StateContentPair<U>(selector(p(state).Content), state);
    }
    public static StateMonad<V> SelectMany<T, U, V>(this StateMonad<T> p, Func<T, StateMonad<U>> selector, Func<T, U, V> projector)
    {
        return state =>
        {
            var first = p(state);
            var second = selector(first.Content)(first.State);
            var content = projector(first.Content, second.Content);
            return new StateContentPair<V>(content, second.State);
        };
    }

    public static StateMonad<int> GetState()
    {
        return s => new StateContentPair<int>(s, s);
    }

    public static StateMonad<T> SetState<T>(int s1)
    {
        return s => new StateContentPair<T>(default(T), s1);
    }
}

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

Edmondo Pentangelo — Mon, 01 Dec 2008 01:05:36 GMT

//LINQ Monadic Labelling of a Binary Tree

public static StateMonad<BTree> MLabel(BTree tree)
{
    var branch = tree as BBranch;
    var leaf = tree as BLeaf;

    StateMonad<BTree> ret = null;

    if (leaf != null)
    {
        var q = from x in LinqStateMonad.GetState()
                from f in LinqStateMonad.SetState<int>(x + 1)
                select new BLeaf { Content = leaf.Content, State = x };
        ret = s => { var r = q(s); return new StateContentPair<BTree>(r.Content, r.State); };
    }

    if (branch != null)
    {
        var q = from l in MLabel(branch.Left)
                from r in MLabel(branch.Right)
                select new BBranch() { Left = l, Right = r };
        ret = s => { var r = q(s); return new StateContentPair<BTree>(r.Content, r.State); };
    }

    return ret;
}

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

Edmondo Pentangelo — Fri, 28 Nov 2008 00:47:59 GMT

// F# Monadically label n-ary tree

let MMap f xs = 
            let rec MMap' (f, xs', out) = 
                state {
                        match xs' with
                        | h :: t -> let! h' = f(h)
                                    return! MMap'(f, t, List.append out [h'])
                        | [] -> return out
                      }
            MMap' (f, xs, [])


let rec private MNNode (x) =
    match x with
    | NLeaf(c) -> state { let! x = GetState
                          do! SetState (x + 1)
                          return NLeaf(c,x) }
                         
    | NNode(xs) -> state { let! xs' = MMap MNNode xs
                           return NNode(xs')  } 
                    
let MNLabel x = Execute(MNNode(x))

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

Daniel Earwicker — Thu, 27 Nov 2008 18:35:48 GMT

I see - so Haskell says "trust me, this won't last" and Haskell is undoubtedly correct!

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

brianbec — Thu, 27 Nov 2008 15:55:56 GMT

HINT for Ex 4: look up "mapM" in the Haskell libraries (www.haskell.org)

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

brianbec — Thu, 27 Nov 2008 00:57:28 GMT

Ben, the State is "anything you like," and that's the point of some of the exercises: to package, say, layout information in the State. The mechanism doing the threading is the particular pattern of capturing values in closed-over variables (free variables inside functions from state to state-value pairs) and then doing the state threading by composition of "functions from state to state-value pairs." This pattern is so common as to deserve its own library, and, it just so happens that it satisfies the monad laws (associativity and right-left unit). So, as they used to say, don't you love it when a plan comes together?

The result is conceptually small code that happens to be completely safe in a parallel, concurrent environment, but can do all kinds of stateful things like laying out visualizables. The code is syntactically a bit big in C#, but I'm really liking the way the F# rendition of holoed is looking.

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

brianbec — Thu, 27 Nov 2008 00:52:18 GMT

Yes, this is a big brain workout, but just think nothing will ever scare you again! The underlying concepts are clean, it just takes a lot of syntax to write them out.

I think you're right about abstracting out by M: no higher-kinded types in C# makes it hard to mimic them. Perhaps it's easier to do this in F#? Not sure, but there is a parallel thread on doing the exercises in F#.