Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Monadically labeling a binary tree
<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 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))));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment