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