Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

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

Download

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

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 1 of a 2 part series.
 
See Part 2 here.

Included with this interview is a .zip file containing all of the code and diagrams Brian shows us (including both Haskell and C#). To understand the State Monad program, it may be best to start with Main, seeing how the various facilities are used, then backtrack through the code learning first the non-monadic tree labeler, starting with the function Label, then finally the monadic tree labeler, starting with the function MLabel.  

Below, you will find several exercises for generalizing the constructions further. Brian will monitor this thread so start your coding engines!!

Exercise 1: generalize over the type of the state, from int$0 to <S>, say, so that the SM type can handle any kind of$0 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$0 container computation, as in WPF. Give everything a$0 bounding box, and size subtrees to fit inside their$0 parents, recursively.

Exercise 3: promote @return and @bind into an abstract$0 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$0 state monad in LINQ.

Exercise 7: Verify the Monad laws, either abstractly$0 (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.

Tags:

Follow the Discussion

  • I was thinking that when Visual Studio 2010 finally ships it would be incredibly useful if all these recent C9 parallelism videos (including related theory ones like Brian's) could be pulled together somehow and bundled with the package. If not actually on the DVD then certainly permanently archived online in one, easily navigatable, place.
  • CharlesCharles Welcome Change
    Excellent idea. And it's totally possible by pulling in the content to VS using our tagged RSS feeds. The home page of VS today does exactly this. Putting the content on the DVD is an interesting notion. Not sure how feasible it is given the size constraints (all of C9's videos and screencasts related to Parallel Computing would fill up up a DVD or two Smiley

    Something that would be really cool would be launching a C9 screencast in VS and having the code in the video automatically written to your VS text editor. So, your text editor extensibly replaces the one in the video stream...

    C
  • Duncan MackenzieDuncanma "yeah that's awful close, but that's not why I'm so hard done by"
    Charles said:

    Something that would be really cool would be launching a C9 screencast in VS and having the code in the video automatically written to your VS text editor. So, your text editor extensibly replaces the one in the video stream...


    I think Erik already wrote something like this about a year ago... you should bug him about it
  • Allan LindqvistaL_ Kinect ftw

    man, its been a while since briain tied my brain in a knot, ive missed that Smiley

  • Allan LindqvistaL_ Kinect ftw
    still watching but i gotta ask, is the secret stuff brian's working with oslo? or is it something else? Smiley


    --edit--

    great stuff :O this interview ranks among the best ones ive seen on channel9 but the wmvhigh version (and possibly the others, havent looked yet) end 1:00:47 real abruptly, is there a part two coming?
  • My guess would be the deep type system and associated libraries support for notions of mutability and functional purity. David Callahan, Anders et al dropped serious hints about this at the PDC.
  • LostInSpacebarAdityaG OMG VISTA FTW LOLZ!!1one
    I am sorry... but is that  a wall of patent cubes on his window sill? O_o
  • CharlesCharles Welcome Change
    Oh man... Looks like I missed the last part. Dammit. Sometimes my camera creates a second file when interviews last too long... I'll need to find the ending and patch it on and re-upload the files. Thanks for catching this. Sorry for the troubles.
    C
  • CharlesCharles Welcome Change
    Fixed. Broken in two parts now. Sorry about that....

    Part 2.

    C
  • CharlesCharles Welcome Change
    Don't forget to download the samples and start working on the exercises! Brian is lurking....

    Here are the source files you need for playing with these algorithms in visual studio or your favorite Haskell environment.

    C
  • Allan LindqvistaL_ Kinect ftw
    hey dont worry about it charles, just haappy to be of help Smiley
    i'll watch part two before doing the excercises, some of them didnt make alot of sense to me even after watching part 1 Big Smile (but that might be because of me Wink )

    @AdityaG
    sure looks like patent cubes to me :O if you dont stop inventing awsome stuff you'll be walled in brian Wink


    (sorry for the spelling, im in belgum and their keyboards are all diffrent)
  • Best way to attack the exercises is to open up the code samples and go through the C# code line-by-line, letter-by-letter, and compare it to the visio drawings. The transcription (modulo mistakes of course) is supposed to be faithful, one-to-one. The drawings are supposed to support the fundamental ideas that will help you crack the exercises. You may want to start each exercise by producing a new drawing from a copy of the old ones that reflects your ideas about how to proceed, then go over and write the code, maybe with a little back-and-forth to converge to a refined solution. Always keep copies of "where you started" because you will likely have some false starts.

    Yes, those are cubes, but my collection is tiny compared to Erik Meijer's!

  • Daniel Earwickerdanielearwi​cker I used to be language agnostic, now I'm language atheist

    I have a question. I had assumed that the definition of "bad" would be "a function that has side effects". But Brian gives the key definition as of a mathematical function, which is one that returns the same value given the same arguments. This is much neater because it means that you don't have to decide what "side effect" means (could mean a lot of things). But then I realised that this means that a mathematical function CAN have side effects! It just mustn't allow anything to affect what IT returns for a given set of arguments - but it is okay for it to affect what other functions will return. Those other functions would not be mathematical, because they reveal the side effects. So a mathematical function doesn't reveal side effects via its return - this says nothing about causing them.

    So my question is, as long as "printf" returns the same value for a given argument, what does it matter if it has the side effect of printing text out to the console? Why can't I add it to my program harmlessly? Previously I was using all mathematical functions, now I'm adding a printf call somewhere, that's also a mathematical function, so nothing has changed.

    (Or can I deduce from this that haskell's equivalent of printf returns a new modified instance of the console every time you call it...? Semi-serious question!)

  • Very astute Smiley  So long as the side-effects on other things are absolutely unobservable inside your program, then, yes, you can "get away with" printf'ing to the console. The "however" arises when you want to use the same functions for IO to the console that you use for IO to files, where the side effects are absolutely observable in your program, and you want them to be observable. Haskell puts all side-effecting IO functions in the IO monad for conceptual hygiene, even the relatively benign ones that print to the console, because you might use the same ones to print to files. You might even want to repurpose your program to printf to a file, as with a pipe command, without rewriting your program, and now you will wish you had been careful Smiley

    The IO monad threads around a conceptual "State Of The IO Universe" in just the way the State Monad threads around whatever states you want to play with. Of course, under the covers, the IO Monad implementation keeps track of what's observable and what's not observable, keeping up the efficiency. But you get the benefit of just one kind of IO functions, and the usual help of the type system to keep you "mathematical." The downside is that even to printf to the console for debugging, you must put your program in the IO monad at the outset, sigh.
  • I (think) I solved exercise 1 & 2. These are really ugly in C# - so much nicer in Haskell. Exercise #2 was terrible, until I realized I needed to change my state updating function depending on if I was going "left" or "right." The single code file is below but I have all the code on github:

      http://github.com/m4dc4p/statemonad/tree/master


    If I continue to work on the exercises, commits will show up there. 

    Exercise1.cs:

        namespace Exercise1
        {
            // 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".

            public class Scp<State, Contents> // State-Content Pair
            {
                public State label { get; set; }
                public Contents lcpContents { get; set; } // New name; don't confuse
                // with the old "contents"
                public override string ToString()
                {
                    return String.Format("Label: {0}, Contents: {1}", label, lcpContents);
                }
            }

            public delegate Scp<State, Contents> S2Scp<State, Contents>(State state);

            public delegate SM<State, Contents2> Maker<State, Contents1, Contents2>(Contents1 input);

            public class SM<State, Contents>
            {
                public S2Scp<State, Contents> s2scp { get; set; }

                public static SM<State, Contents> @return(Contents contents)
                {
                    return new SM<State, Contents>
                    {
                        s2scp = (st => new Scp<State, Contents>
                        {
                            label = st,
                            lcpContents = contents
                        })
                    };
                }

                public static SM<State, Contents2> @bind<Contents2>(SM<State, Contents> inputMonad, Maker<State, Contents, Contents2> inputMaker)
                {
                    return new SM<State, Contents2>
                    {
                        // The new instance of the state monad is a
                        // function from state to state-contents pair,
                        // here realized as a C# lambda expression:

                        s2scp = (st0 =>
                        {
                            // Deconstruct the result of calling the input
                            // monad on the state parameter (done by
                            // pattern-matching in Haskell, by hand here):

                            var lcp1 = inputMonad.s2scp(st0);
                            var state1 = lcp1.label;
                            var contents1 = lcp1.lcpContents;

                            // Call the input maker on the contents from
                            // above and apply the resulting monad
                            // instance on the state from above:

                            return inputMaker(contents1).s2scp(state1);
                        })
                    };
                }
            }
        }

    Exercise2.cs:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace StateMonad
    {
        namespace Exercise2
        {
            // 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.

            /// <summary>
            /// A container to fit nodes within. Assume nodes fill their
            /// container.
            /// </summary>
            public class Size
            {
                public Size(int w, int h) { Height = h; Width = w; }

                public int Width { get; private set; }
                public int Height { get; private set; }

                public override string ToString()
                {
                    return Width.ToString() + ", " + Height.ToString();
                }
            }

            public class Point
            {
                public Point(int x, int y) { X = x; Y = y; }

                public int X { get; private set; }
                public int Y { get; private set; }

                public override string ToString()
                {
                    return X.ToString() + ", " + Y.ToString();
                }
            }

            /// <summary>
            /// Given root a tree and a container size, find the rectangles for each
            /// node in the tree such that all nodes will fit in the container. Only leafs
            /// actually get sizes - branches represent depth only. It is assumed that leaves
            /// will fill all available space.
            /// </summary>
            public class ConstrainTree
            {
                public delegate Exercise1.SM<Size, Size> Updater();

                public static Exercise1.SM<Size, Size> RightUpdateState()
                {
                    return new Exercise1.SM<Size, Size>
                    {
                        s2scp = (size => new Exercise1.Scp<Size, Size>
                        {
                            label = new Size(size.Width * 2, size.Height * 2),
                            lcpContents = size
                        })
                    };
                }

                public static Exercise1.SM<Size, Size> LeftUpdateState()
                {
                    return new Exercise1.SM<Size, Size>
                    {
                        s2scp = (size => new Exercise1.Scp<Size, Size>
                        {
                            label = new Size(size.Width / 2, size.Height / 2),
                            lcpContents = new Size(size.Width / 2, size.Height / 2)
                        })
                    };
                }

                public static Exercise1.SM<Size, Program.Tr<Exercise1.Scp<Size, Size>>> Mk<A>(Program.Tr<A> tree, Updater update)
                {
                    if (tree is Program.Lf<A>)
                    {
                        var leaf = (Program.Lf<A>)tree;
                        return Exercise1.SM<Size, Size>.bind<Program.Tr<Exercise1.Scp<Size, Size>>>(update(),
                            (contents1 =>
                                Exercise1.SM<Size, Program.Tr<Exercise1.Scp<Size, Size>>>.@return(
                                new Program.Lf<Exercise1.Scp<Size, Size>>
                                {
                                    contents = new Exercise1.Scp<Size, Size>
                                    {
                                        label = contents1,
                                        lcpContents = contents1
                                    }
                                })));
                    }
                    else
                    {
                        var branch = (Program.Br<A>)tree;
                        var left = branch.left;
                        var right = branch.right;

                        return Exercise1.SM<Size, Program.Tr<Exercise1.Scp<Size, Size>>>.bind<Program.Tr<Exercise1.Scp<Size, Size>>>(
                            Mk<A>(left, new Updater(LeftUpdateState)),
                            (newLeft => Exercise1.SM<Size, Program.Tr<Exercise1.Scp<Size, Size>>>.bind<Program.Tr<Exercise1.Scp<Size, Size>>>(
                                Mk<A>(right, new Updater(RightUpdateState)),
                                (newRight => Exercise1.SM<Size, Program.Tr<Exercise1.Scp<Size, Size>>>.@return(
                                    new Program.Br<Exercise1.Scp<Size, Size>>
                                    {
                                        left = newLeft,
                                        right = newRight
                                    }
                                    ))
                                    )));
                    }
                }

                /// <summary>
                /// After traversal the width and height on each node will represent the maximum
                /// bounding box size necessary to cover all children of the node, assuming a binary
                /// tree laid out "down". A bounding box of 1 x 1 will over the node itself.
                /// </summary>
                /// <typeparam name="Contents1"></typeparam>
                /// <param name="tree"></param>
                /// <returns></returns>
                public static Program.Tr<Exercise1.Scp<Size, Size>> Bound<A>(Program.Tr<A> tree, Size containerSize)
                {
                    return Mk<A>(tree, new Updater(LeftUpdateState)).s2scp(containerSize).lcpContents;
                }
            }

        }
    }

  • I don't quite understand what "state" means and what is being done with it.  Passing along state and incrementing it makes sense conceptually, but what mechanism is providing the benefit? The haskell compiler?

    TIA
    Ben Lipman

  • // F# Monadic tree labeller (using State Monad from http://cs.hubfs.net/forums/thread/7472.aspx)
    let rec private mNode (x) = match x with | Leaf(c) -> state { let! x = GetState do! SetState (x + 1) return Leaf(c,x) } | Node(l,r) -> state { let! l = mNode(l) let! r = mNode(r) return Node(l,r) } let mLabel x = Exec(mNode(x)) // F# Non-Monadic manual state passing tree labeller let Label a s = let rec Lab' a s =
    match a with
    |Leaf(c) -> (Leaf(c,s), s + 1)

    |Node(l,r) -> let l'
    = Lab' l s
    let r'
    = Lab' r (snd l') (Node(fst l', fst r'), (snd r'))
    fst (Lab'
    a s)
  • CharlesCharles Welcome Change
    Keep the answers coming! Smiley Great to see!
    C

  • //F# State Monad
    type State<'state, 'a> = State of ('state ->'a * 'state) type StateMonad() = member b.Bind(m, f) = State (fun s -> let r = match m with | State f -> f s match r with | (v,s) -> match f v with | State f -> f s) member b.Return(x) = State (fun s -> x, s) let state = StateMonad() let GetState = State (fun s -> s, s) let SetState s = State (fun _ -> (), s) let Execute m s = match m with | State f -> let r = f s match r with |(x,_) -> x
  • +100 Smiley very nice
  • beautiful!
  • Here is Exercise 3. All the code is available for download at

    http://github.com/m4dc4p/statemonad/tree/exercise3

    I added some tags so I can push updates and not break the exercises. 

    The M class is abstracted over the contents of the monad, but it feels like it should be abstracted over the specific monad AND the contents. In Haskell the monad class is declared as:

      class Monad m where
        (>>=) :: m a -> (a -> m b) -> m b -- bind
        return :: a -> m a

    where "m" is abstractd, but I could not get that working in C#. I think that is because C# lacks "higher-kinded" types but I'm not sure. This shows up in my implementation as casts in the overriden bind and @return methods.

    First my M class:

    namespace StateMonad
    {
        namespace Exercise3
        {
            public abstract class M<Contents1>
            {
                public delegate M<Contents2> Maker<Contents2>(Contents1 c);

                public abstract M<Contents2> @bind<Contents2>(M<Contents1> input, Maker<Contents2> maker);

                public abstract M<Contents1> @return(Contents1 contents);
            }

            public class Scp<State, Contents> // State-Content Pair
            {
                public State label { get; set; }
                public Contents lcpContents { get; set; } // New name; don't confuse
                // with the old "contents"
                public override string ToString()
                {
                    return String.Format("Label: {0}, Contents: {1}", label, lcpContents);
                }
            }

            public delegate Scp<State, Contents> S2Scp<State, Contents>(State state);

            public class SM<State, Contents1> : M<Contents1>
            {
                public S2Scp<State, Contents1> s2scp { get; set; }

                public override M<Contents2> bind<Contents2>(M<Contents1> input, Maker<Contents2> maker)
                {
                    // These casts are UGLY but I can't seem to get
                    // rid of them ...
                    return (M<Contents2>) new SM<State, Contents2>
                    {
                        // The new instance of the state monad is a
                        // function from state to state-contents pair,
                        // here realized as a C# lambda expression:

                        s2scp = (st0 =>
                        {
                            // Deconstruct the result of calling the input
                            // monad on the state parameter (done by
                            // pattern-matching in Haskell, by hand here):

                            Scp<State, Contents1> lcp1 = ((SM<State, Contents1>) input).s2scp(st0);
                            State state1 = lcp1.label;
                            Contents1 contents1 = lcp1.lcpContents;

                            // Call the input maker on the contents from
                            // above and apply the resulting monad
                            // instance on the state from above:
                            var m = maker(contents1);
                            var r = ((SM<State, Contents2>)m).s2scp(state1);
                            return r;
                        })
                    };
                }

                public override M<Contents1> @return(Contents1 contents)
                {
                    return new SM<State, Contents1>
                    {
                        s2scp = (st => new Scp<State, Contents1>
                        {
                            label = st,
                            lcpContents = contents
                        })
                    };
                }
            }
       }
    }

    and the ConstrainedTree example I implemetned in Excercise2 (exactly the same except I added some casts). This is about the most painful C# I've ever had to write!  Fortunately teh compiler helps a lot by telling me which types don't match:

    namespace StateMonad
    {
        namespace Exercise3
        {
            public class Size
            {
                public Size(int w, int h) { Height = h; Width = w; }

                public int Width { get; private set; }
                public int Height { get; private set; }

                public override string ToString()
                {
                    return Width.ToString() + ", " + Height.ToString();
                }
            }

            public class ConstrainTree
            {
                public delegate Exercise3.SM<Size, Size> Updater();

                public static Exercise3.SM<Size, Size> RightUpdateState()
                {
                    return new Exercise3.SM<Size, Size>
                    {
                        s2scp = (size => new Exercise3.Scp<Size, Size>
                        {
                            label = new Size(size.Width * 2, size.Height * 2),
                            lcpContents = size
                        })
                    };
                }

                public static Exercise3.SM<Size, Size> LeftUpdateState()
                {
                    return new Exercise3.SM<Size, Size>
                    {
                        s2scp = (size => new Exercise3.Scp<Size, Size>
                        {
                            label = new Size(size.Width / 2, size.Height / 2),
                            lcpContents = new Size(size.Width / 2, size.Height / 2)
                        })
                    };
                }

                public static Exercise3.SM<Size, Program.Tr<Exercise3.Scp<Size, Size>>> Mk<A>(Program.Tr<A> tree, Updater update)
                {
                    if (tree is Program.Lf<A>)
                    {
                        var leaf = (Program.Lf<A>)tree;
                        return (Exercise3.SM<Size, Program.Tr<Exercise3.Scp<Size, Size>>>)
                            (new Exercise3.SM<Size, Size>()).bind<Program.Tr<Exercise3.Scp<Size, Size>>>(update(),
                            (contents1 =>
                                (new Exercise3.SM<Size, Program.Tr<Exercise3.Scp<Size, Size>>>()).@return(
                                new Program.Lf<Exercise3.Scp<Size, Size>>
                                {
                                    contents = new Exercise3.Scp<Size, Size>
                                    {
                                        label = contents1,
                                        lcpContents = contents1
                                    }
                                })));
                    }
                    else
                    {
                        var branch = (Program.Br<A>)tree;
                        var left = branch.left;
                        var right = branch.right;

                        return (Exercise3.SM<Size, Program.Tr<Exercise3.Scp<Size, Size>>>)
                            (new Exercise3.SM<Size, Program.Tr<Exercise3.Scp<Size, Size>>>()).bind<Program.Tr<Exercise3.Scp<Size, Size>>>(
                            Mk<A>(left, new Updater(LeftUpdateState)),
                            (newLeft => (new Exercise3.SM<Size, Program.Tr<Exercise3.Scp<Size, Size>>>()).bind<Program.Tr<Exercise3.Scp<Size, Size>>>(
                                Mk<A>(right, new Updater(RightUpdateState)),
                                (newRight => (new Exercise3.SM<Size, Program.Tr<Exercise3.Scp<Size, Size>>>()).@return(
                                    new Program.Br<Exercise3.Scp<Size, Size>>
                                    {
                                        left = newLeft,
                                        right = newRight
                                    }
                                    ))
                                    )));
                    }
                }

                /// <summary>
                /// After traversal the width and height on each node will represent the maximum
                /// bounding box size necessary to cover all children of the node, assuming a binary
                /// tree laid out "down". A bounding box of 1 x 1 will over the node itself.
                /// </summary>
                /// <typeparam name="Contents1"></typeparam>
                /// <param name="tree"></param>
                /// <returns></returns>
                public static Program.Tr<Exercise3.Scp<Size, Size>> Bound<A>(Program.Tr<A> tree, Size containerSize)
                {
                    return Mk<A>(tree, new Updater(LeftUpdateState)).s2scp(containerSize).lcpContents;
                }
            }

        }
    }


  • 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#.
  • 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.
  • HINT for Ex 4: look up "mapM" in the Haskell libraries (www.haskell.org)
  • Daniel Earwickerdanielearwi​cker I used to be language agnostic, now I'm language atheist

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

  • // 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))
  • //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;
    }
  • //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);
        }
    }
  • holoed, this is fantastic! +1000 pts Smiley
  • 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
  • 
    // 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()
    
  • // 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 })
  • //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 
                                        
  • CharlesCharles Welcome Change
    Nice work (all around)! Thanks for sharing.
    C
  • 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 Smiley  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.)
  • Absolutely heroic!
  • CharlesCharles Welcome Change
    Indeed! Hey, holoed. Who are you, man? Smiley
    C
  • Thank you Brian Smiley

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

    HoloEd

  • Thank you Charles Smiley

    I've updated my profile:

    Edmondo Pentangelo
    Deutsche Bank 
    London, UK
  • // 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
    
  • Allan LindqvistaL_ Kinect ftw
    woah holoed you Are the man Perplexed i havent had time to write out the excercises yet(but ive tried to solve them in my head Smiley ), 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 Perplexed nut no more excuses Smiley i really really enjoyed this interview+excercises Smiley

    please pretty please charles and brian,  do intervies like this about the other monads as well Smiley
  • CharlesCharles Welcome Change
    Indeed. I bet Brian's excited to dig into the Continuation monad... Smiley
    C
  • "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!

  • 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(

                       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.

  • 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 Smiley

  • Bent Rasmussenexoteric stuck in a loop, for a while

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

  • Does the style of logic/flow diagraming (ie. in Visio) have a special name? It seems like a good way to reason about the problem and was hopinh to find out more information about it?

Remove this comment

Remove this thread

close

Comments Closed

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.