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

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 Labeled<T>
{
    public int Label { get; private set; }
    public T Value { get; private set; }
    
    public Labeled(int label, T value)
    {
        Label = label;
        Value = value;
    }
        
    public override string ToString()
    {
        return new { Label, 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 Labeled<T> labeled<T>(int label, T value)
{
    return new Labeled<T>(label, value);
}

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

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

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

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

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