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 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))));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment