In the previous post of this series we did a small improvement to the state monad implementation by generalizing it over the type of the state.
This is not exactly a requirement for labeling trees as the state can be simply an integer, but it’s a more natural choice now that we tackle the second exercise.
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.
As you know the exercises come without any solution, so let’s try to understand what we need to do here.
Because we’re talking about binary trees let’s assume that the requirement is to perform the constrained container computation based on containers with two children,
where each child can either be another container or a terminal element, like a text block.
By translating it to WPF as suggested in the assignment we can represent a branch as a Grid with two rows and a single column.
Each row’s unique cell can contain either another grid with the same characteristics or a TextBlock.
The layout features of a grid match exactly the solution to the problem we’re asked to solve, as child elements of grid cells expand to match the size of their parent.
Starting with the same simple tree we used as a sample throughout the series:
The result of this markup, along with some additional styling and a bit of logic to outline the bounds of each cell and display its box size, is shown below.
The full code of this example is available as a ready-to-run LINQPad query here.
As you can see the children of grid cells automatically expand to fit their parent’s size.
More precisely, each grid row gets 50% of the height of its parent, regardless of the contents.
We’ll now try to do the same monadically by adapting our data structures and labeling logic to this new case.
First of all we need to decide what is the type of the state we’ll be carrying around.
Intuitively, each time we branch a grid into its two rows we allocate 50% of the available height to each of them, therefore the state will certainly include the available height.
Although not strictly needed in this scenario let’s make it a little more realistic by including the width as well, and we’ll call a structure containing two such values a Box.
With this little piece of information we can already define the signature of our function which, similarly to the previous MLabel, will represent the entry point for the constrained box computation.
The function takes a tree, which in this case we can imagine being a visual tree of graphic elements, and an initial box size (our initial state), representing the size of the root element.
The return value is a tree whose generic argument is a tuple of state-content values.
The state is the Box representing the size allocated to that tree and the value is the generic parameter T that we’re currently filling with characters to distinguish a leaf from another leaf.
As we did with the labeling problem the entry function will finally delegate to a helper function that will call itself recursively. We can thus define the body of the previous function as follows:
No big surprises here as the juice is actually in the body of the MConstrainedBox1 function, in the same way as it previously was in MLabel1. Let’s start by defining its signature, which we can infer from above.
Not much else to do except reasoning about how to solve the problem of assigning box sizes to tree leaves according to the rules described earlier. The process is overall simple, let’s outline the steps.
If the current tree is a leaf then extract the state value using a proper getState function similar to what we used in the labeling scenario. The main difference here is that when we encounter leaves we do not need to update any state but only extract it from the monad and attach it to the new leaf we create.
If the current tree is a branch then:
update the state by halving the height of the current box
recurse over the left branch
recurse over the right branch
update the state by doubling the height of the current box
return an instance of the state monad whose value is a branch with the results of steps 2 and 3 as the left and right trees, respectively
Let’s go through a simple example to understand better.
Assuming to start with a box of size 200 x 400 (W x H) and that the root element of the tree we want to process is a branch,
we halve the available height and process the left and right trees using 200 as the available height for each of them.
If at some point we come across a leaf we use whatever current value of the state we have at that point during the computation
(if both left and right trees are leaves then each of them will get a height of 200). When we’re done with the two trees we restore the original height by multiplying it by two.
This leads exactly to the solution we’re looking for.
The full source code is as usual available as a gist containing a LINQPad query that you can download an run right away.
In the next post we’ll do a step forward in defining a self-contained monad type before moving on to more interesting and challenging exercises.
In the last post of this series we learned how to label a binary tree monadically, and in doing so we discovered the state monad. I’ve collected the pieces we built incrementally last time into this gist containing the whole monadic label implementation as a LINQPad query that you can simply copy and run. I’ll keep making changes to that gist and create links which point to specific revisions from now on.
As I mentioned in the introduction I decided to write this series as a result of watching some years ago Brian Beckman talking about monads and not being able to grasp the topic at that time. Going through it again and explaining what it took me to understand it will hopefully help someone else follow the same path. Up until now we’ve rediscovered what Brian explained in his interviews, but the accompanying source code (that I’ve copied in this gist for convenience) also gave 10 assignments to the reader - without solutions - which I’m going to tackle in the remainder of this series.
The exercises are of varying difficulties, basically expanding on the topic of the state monad with tasks which require generalizing the pattern and applying it to solve problems other than labeling binary trees. So, without further ado, let’s move on to the first exercise.
Exercise 1
generalize over the type of the state, from int
to <TState>, say, so that the S type can handle any kind of
state object. Start with Labeled<T> –> StateContent<TState, T>, from
“label-content pair” to “state-content pair”.
I rephrased the original text of the exercise a little bit so it matches our own implementation rather than Brian’s. Some type names are different as well as some design choices, but the overall concept is the same. Let’s see what this exercise is about.
So far we used a Labeled<T> class to represent the contents of a labeled tree - leaves, specifically. This class is a simple container of label and value pairs, where only the latter is generically parameterized via the T generic parameter. This exercise requires to parameterize the type of the label/state too, which is currently fixed to be an integer. It doesn’t sound very difficult, does it? We simply come up with a new type StateContent<TState, T> which does just that, and then adapt the usages of Labeled<T> to match the new type.
In addition to that we’ll also have to make some changes to the S<T> class, because it’s hardcoding the type of the state to be an integer. This will in turn require some changes to the MLabel1 function, mainly to cope with limited type inference capabilities of the C# compiler. The end result is shown in the diff below.
@@ -59,10 +59,10 @@ public class Branch<T> : Tree<T>-public class Labeled<T>+public class StateContent<TState, T> {
- public int Label { get; private set; }+ public TState State { get; private set; } public T Value { get; private set; }
- public Labeled(int label, T value)+ public StateContent(TState state, T value) {
- Label = label;+ State = state; Value = value;
@@ -72,3 +72,3 @@ public class Labeled<T> {
- return new { Label, Value }.ToString();+ return new { State, Value }.ToString(); }
@@ -86,15 +86,15 @@ public Tree<T> branch<T>(Tree<T> left, Tree<T> right)-public Labeled<T> labeled<T>(int label, T value)+public StateContent<TState, T> stateContent<TState, T>(TState state, T value) {
- return new Labeled<T>(label, value);+ return new StateContent<TState, T>(state, value); }
-public class S<T>+public class S<TState, T> {
- public Func<int, Tuple<int, T>> RunWithState;+ public Func<TState, Tuple<TState, T>> RunWithState; }
-public static S<U> Bind<T, U>(S<T> m, Func<T, S<U>> k)+public static S<TState, U> Bind<TState, T, U>(S<TState, T> m, Func<T, S<TState, U>> k) {
- return new S<U> + return new S<TState, U> {
@@ -102,3 +102,3 @@ public static S<U> Bind<T, U>(S<T> m, Func<T, S<U>> k) {
- Tuple<int, T> mResult = m.RunWithState(s0);+ Tuple<TState, T> mResult = m.RunWithState(s0);@@ -109,5 +109,5 @@ public static S<U> Bind<T, U>(S<T> m, Func<T, S<U>> k)-public static S<T> Return<T>(T value)+public static S<TState, T> Return<TState, T>(T value) {
- return new S<T> + return new S<TState, T> {
@@ -117,3 +117,3 @@ public static S<T> Return<T>(T value)-public Tree<Labeled<T>> MLabel<T>(Tree<T> tree)+public Tree<StateContent<int, T>> MLabel<T>(Tree<T> tree) {
@@ -122,3 +122,3 @@ public Tree<Labeled<T>> MLabel<T>(Tree<T> tree)-public S<Tree<Labeled<T>>> MLabel1<T>(Tree<T> tree)+public S<int, Tree<StateContent<int, T>>> MLabel1<T>(Tree<T> tree) {
@@ -128,3 +128,3 @@ public S<Tree<Labeled<T>>> MLabel1<T>(Tree<T> tree)- var updateState = new S<int> + var updateState = new S<int, int> {
@@ -134,3 +134,3 @@ public S<Tree<Labeled<T>>> MLabel1<T>(Tree<T> tree) return Bind(updateState,
- label => Return(leaf(labeled(label, lf.Value))));+ label => Return<int, Tree<StateContent<int, T>>>(leaf(stateContent(label, lf.Value)))); }
@@ -142,3 +142,3 @@ public S<Tree<Labeled<T>>> MLabel1<T>(Tree<T> tree) left => Bind(MLabel1(br.Right),
- right => Return(branch(left, right))));+ right => Return<int, Tree<StateContent<int, T>>>(branch(left, right)))); }
It was an easy one this time, which sets the foundation for the next exercise, but we’ll come to it in the next post. The source code after this change is in the same old gist at this revision.
This is the second post of a series about labeling trees. In the previous post we saw how to mark leaves of a binary tree with integer, incrementing labels, first manually and then functionally without relying on mutable state. We achieved it by writing a recursive Label1 function which threaded the value of the label, the state, via function arguments and return value, incrementing it every time it came across a leaf of the tree.
Let’s review the signature of the Label1 function and then move one step forward towards a different, less explicit way to pass the state around.
As the signature clearly shows the state passing is visible both in the arguments and the return value of the function. There is certainly a good reason for that: if we need to increment the label and use the new value whenever we come across the next leaf would it be possible to do otherwise? Let’s as well review the part of the function which took care of applying labels to the leaves.
This simple code mixes together two concerns: creating a labeled leaf and incrementing the value of the label, squeezing them into a tuple. Let’s try to abstract and extract these two responsibilities and then apply a series of simple transformations over them, while keeping the behavior unchanged.
First transformation: from integer to tuple
Label1 first transformation (label1-leaves-transformation-1.cs)download
Here we extracted the increment concern as a standalone operation. newAndOldLabel is a tuple whose first item contains the new value of the label and the second item contains the previous, unchanged value. The second statement simply uses it to create the final tuple.
Second transformation: from tuple to functions returning tuples
Label1 second transformation (label1-leaves-transformation-2.cs)download
Here we wrap the last statement from the previous step into a function which accesses newAndOldLabel via its arguments (rather than via local variables) and returns the result of invoking the function itself with newAndOldLabel.
Third transformation: from anything to functions
Label1 third transformation (label1-leaves-transformation-3.cs)download
123456789101112
// previous: Tuple<int, int>// current: int => Tuple<int, int>Func<int,Tuple<int,int>>bumpLabel=s=>Tuple.Create(s+1,s);// previous: Tuple<int, int> => Tuple<int, Tree<Labeled<T>>>// current: int => int => Tuple<int, Tree<Labeled<T>>>Func<int,Func<int,Tuple<int,Tree<Labeled<T>>>>>labelLeafCurried=labelValue=>s=>Tuple.Create(s,leaf(labeled(labelValue,lf.Value)));Tuple<int,int>bumpResult=bumpLabel(label);returnlabelLeafCurried(bumpResult.Item2)(bumpResult.Item1);
Here we apply a transformation to both the label increment and the leaf-labeling logic. In the first case we wrap the creation of the newAndOldLabel tuple into a function which rather than grabbing the value of the label from the integer label argument of the containing function accesses it via its own argument.
In the second case we curry the already existing function so that instead of accepting a tuple argument it accepts a single integer argument and returns a function which accepts another integer argument and finally returns our output tuple. The external function takes care of fixing the current value used to apply a label to the leaf, while the inner function fixes the new, incremented label value as the first item of the resulting tuple.
The rest of the code binds together these two functions in a way which preserves the overall behavior.
Fourth transformation: Bind
As we just mentioned binding, let’s finally abstract this concept into its own Bind generic function. This function basically encapsulates the logic of composing bumpLabel and labelLeafCurried from the previous transformation.
Before looking at its definition let’s observe some of the characteristics of this function. It takes two functions as its arguments and returns a third function, which is then executed passing label as its only argument. Knowing both the signatures of the input functions and the return type of the containing Label1 function implies that we also know the signature of the Bind function. Furthermore, being a replacement for the last few lines of code from the previous step means that the body will encapsulate the same logic in some form.
The important thing to note is that we’ve come here by applying some simple and logical transformations to the initial code, and if you try to follow what this code is doing you can realize that the behavior is unchanged. One final step to abstract this even more is to make it generic over the second item of the tuples involved, thus leading to a new signature (the body is unchanged).
The signature of our Bind function is a mouthful, but we can see that there’s a recurring pattern in there. Specifically, we can see occurrences of Func<int, Tuple<int, X>> again and again. Let’s encapsulate this into a generic type S<T> which will have a single member of that function type, arbitrarily named RunWithState.
We can finally observe one more pattern in how the labelLeafS function creates an instance of the S type. You can see that the only value this instance depends on is the labeled leaf created inside its RunWithState function, which is of exactly the same type as the generic argument of the instance S<Tree<Labeled<T>>>. Not that we benefit much from it now, but let’s extract this pattern into a Return method, which given a T, returns an instance of S<T>.
Before we move on and formalize the outcome of this long sequence of transformations in a new, named pattern let’s observe one important thing in the final version of our code. The final statement returns a value of type Tuple<int, Tree<Labeled<T>>> simply because we execute the RunWithState function of the S<Tree<Labeled<T>>> instance returned by Bind. Executing this function is also the only occasion in which we use the integer label argument of the containing function Label1.
The observation is therefore: if rather than returning a Tuple<int, Tree<Labeled<T>>> we returned S<Tree<Labeled<T>>> then we wouldn’t need the label argument in Label1 and shift to the caller the responsibility of executing RunWithState with the initial label value. In fact Label, the caller, is already doing that, just more explicitly via function arguments, but we can see that we have an opportunity to change the pattern of providing the initial state by moving from a function with this signature:
pseudo old signature
1
int,Tree<T>=>Tuple<int,Tree<Labeled<T>>>
To a function with this signature:
pseudo new signature
1
Tree<T>=>int=>Tuple<int,Tree<Labeled<T>>>
Those familiar with functional programming will find that this is vaguely similar to currying, where a function of n arguments is transformed into n functions of 1 argument each.
We now have all the building blocks for rewriting our whole labeling functions Label and Label1 from a completely new perspective, where the final outcome is the same but the means by which we get there are completely different. This also justifies creating two new functions called MLabel and MLabel1, respectively.
MLabel and MLabel1 (mlabel-and-mlabel1.cs)download
Together with Bind, Return and the type S<T> this is the bulk of the code required to label trees in this new way.
Now, although we have gone to great lengths talking about leaves, you might wonder why branches did not deserve their own considerations as I’ve included them in the code above already.
The reason is that as soon as you understand what we did with leaves it should be easy, even easier, to figure out what is happening with branches, as there is no state change involved. Before we try to understand the similarities I suggest you lookup the final version of the code from the previous post.
The analogy should be more visible than it is for leaves, let’s explain in words. We bind a recursive call to MLabel1 fed with the left tree of the branch to a function which takes the left labeled tree and binds another recursive call, this time fed with the right tree, to a function which takes the right labeled tree and returns an instance of the state monad created from a branch whose left tree is accessed via a closure and the right is the argument of the function itself.
Besides the mouthful, did I just say state monad? Ah right, the state monad is the triplet represented by S<T>, Bind and Return, while MLabel and MLabel1 are just our logic to label a tree in a third way besides manually and functionally: monadically.
As for the state monad, we just invented it, but more on this in the next post.
