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".
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
Comments