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(); | |
Console.WriteLine(); | |
MConstrainedBox(tree, new Box(200, 400)).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)))); | |
} | |
} | |
public class Box | |
{ | |
public readonly int Width; | |
public readonly int Height; | |
public Box(int width, int height) | |
{ | |
Width = width; | |
Height = height; | |
} | |
public override string ToString() | |
{ | |
return new { Width, Height }.ToString(); | |
} | |
} | |
public Tree<StateContent<Box, T>> MConstrainedBox<T>(Tree<T> tree, Box box) | |
{ | |
return MConstrainedBox1(tree).RunWithState(box).Item2; | |
} | |
public S<Box, Tree<StateContent<Box, T>>> MConstrainedBox1<T>(Tree<T> tree) | |
{ | |
if(tree is Leaf<T>) | |
{ | |
var lf = tree as Leaf<T>; | |
var getState = new S<Box, Box> | |
{ | |
RunWithState = b0 => Tuple.Create(b0, b0) | |
}; | |
return Bind(getState, b0 => | |
Return<Box, Tree<StateContent<Box, T>>>(leaf(stateContent(b0, lf.Value)))); | |
} | |
else | |
{ | |
var br = tree as Branch<T>; | |
var halveHeight = new S<Box, Box> | |
{ | |
RunWithState = b0 => Tuple.Create(new Box(b0.Width, b0.Height/2), b0) | |
}; | |
var doubleHeight = new S<Box, Box> | |
{ | |
RunWithState = b0 => Tuple.Create(new Box(b0.Width, b0.Height*2), b0) | |
}; | |
return Bind(halveHeight, _ => Bind(MConstrainedBox1(br.Left), | |
left => Bind(MConstrainedBox1(br.Right), | |
right => Bind(doubleHeight, __ => | |
Return<Box, Tree<StateContent<Box, T>>>(branch(left, right)))))); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment