Monadically labeling a binary tree

monadic-labeling.cs

<Query Kind="Program" />

void Main()
{
    var tree = branch(     
                   leaf("a"), 
                   branch(    
                       branch(
                           leaf("b"),
                           leaf("c")),
                   leaf("d")));

    tree.Show();
    
    Console.WriteLine();
    
    MLabel(tree).Show();
    
    Console.WriteLine();
    
    MConstrainedBox(tree, new Box(200, 400)).Show();
}

public abstract class Tree<T> 
{
    public abstract void Show(int indent = 0);
}

public class Leaf<T> : Tree<T>
{
    public T Value { get; private set; }
    
    public Leaf(T value) 
    {
        Value = value;
    }
    
    public override void Show(int indent)
    {
        Console.Write(new string(' ', indent * 2) + "Leaf: ");
        Console.WriteLine(Value.ToString());
    }
}

public class Branch<T> : Tree<T>
{
    public Tree<T> Left { get; private set; }
    public Tree<T> Right { get; private set; }

    public Branch(Tree<T> left, Tree<T> right)
    {
        Left = left;
        Right = right;
    }
    
    public override void Show(int indent)
    {
        Console.WriteLine(new string(' ', indent * 2) + "Branch:");
        Left.Show(indent + 1);
        Right.Show(indent + 1);
    }
}

public class StateContent<TState, T>
{
    public TState State { get; private set; }
    public T Value { get; private set; }
    
    public StateContent(TState state, T value)
    {
        State = state;
        Value = value;
    }
        
    public override string ToString()
    {
        return new { State, Value }.ToString();
    }
}

public Tree<T> leaf<T>(T value)
{
    return new Leaf<T>(value);
}

public Tree<T> branch<T>(Tree<T> left, Tree<T> right)
{
    return new Branch<T>(left, right);
}

public StateContent<TState, T> stateContent<TState, T>(TState state, T value)
{
    return new StateContent<TState, T>(state, value);
}

public class S<TState, T>
{
    public Func<TState, Tuple<TState, T>> RunWithState;
}

public static S<TState, U> Bind<TState, T, U>(S<TState, T> m, Func<T, S<TState, U>> k)
{
    return new S<TState, U> 
    {
        RunWithState = s0 =>
        {
            Tuple<TState, T> mResult = m.RunWithState(s0);
            
            return k(mResult.Item2).RunWithState(mResult.Item1);
        }
    };
}

public static S<TState, T> Return<TState, T>(T value)
{
    return new S<TState, T> 
    {
        RunWithState = s => Tuple.Create(s, value)
    };
}

public Tree<StateContent<int, T>> MLabel<T>(Tree<T> tree)
{
    return MLabel1(tree).RunWithState(0).Item2;
}

public S<int, Tree<StateContent<int, T>>> MLabel1<T>(Tree<T> tree)
{
    if(tree is Leaf<T>)
    {
        var lf = tree as Leaf<T>;
        
        var updateState = new S<int, int> 
        {
            RunWithState = s0 => Tuple.Create(s0 + 1, s0)
        };
        
        return Bind(updateState, 
                    label => Return<int, Tree<StateContent<int, T>>>(leaf(stateContent(label, lf.Value))));
    }
    else
    {
        var br = tree as Branch<T>;
        
        return Bind(MLabel1(br.Left), 
                    left => Bind(MLabel1(br.Right), 
                                 right => Return<int, Tree<StateContent<int, T>>>(branch(left, right))));
    }
}

public class Box
{
    public readonly int Width;
    public readonly int Height;
    
    public Box(int width, int height)
    {
        Width = width;
        Height = height;
    }
    
    public override string ToString()
    {
        return new { Width, Height }.ToString();
    }
}

public Tree<StateContent<Box, T>> MConstrainedBox<T>(Tree<T> tree, Box box)
{
    return MConstrainedBox1(tree).RunWithState(box).Item2;
}

public S<Box, Tree<StateContent<Box, T>>> MConstrainedBox1<T>(Tree<T> tree)
{
    if(tree is Leaf<T>)
    {
        var lf = tree as Leaf<T>;
        
        var getState = new S<Box, Box>
        {
            RunWithState = b0 => Tuple.Create(b0, b0)
        };
        
        return Bind(getState,  b0 => 
                    Return<Box, Tree<StateContent<Box, T>>>(leaf(stateContent(b0, lf.Value))));
    }
    else
    {
        var br = tree as Branch<T>;
        
        var halveHeight = new S<Box, Box>
        {
            RunWithState = b0 => Tuple.Create(new Box(b0.Width, b0.Height/2), b0)
        };
        
        var doubleHeight = new S<Box, Box>
        {
            RunWithState = b0 => Tuple.Create(new Box(b0.Width, b0.Height*2), b0)
        };
        
        return Bind(halveHeight, _ => Bind(MConstrainedBox1(br.Left),
                    left => Bind(MConstrainedBox1(br.Right),
                    right => Bind(doubleHeight,  __ => 
                    Return<Box, Tree<StateContent<Box, T>>>(branch(left, right))))));
    }
}