Comments

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;
            }
        }

    }
}

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;
            }
        }

    }
}