Skip to content

Instantly share code, notes, and snippets.

Embed
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
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.