Skip to content

Instantly share code, notes, and snippets.

@simoneb
Last active December 15, 2015 22:19

Revisions

  1. simoneb revised this gist Apr 16, 2013. 1 changed file with 61 additions and 0 deletions.
    61 changes: 61 additions & 0 deletions monadic-labeling.cs
    Original file line number Diff line number Diff line change
    @@ -15,6 +15,10 @@ void Main()
    Console.WriteLine();

    MLabel(tree).Show();

    Console.WriteLine();

    MConstrainedBox(tree, new Box(200, 400)).Show();
    }

    public abstract class Tree<T>
    @@ -142,4 +146,61 @@ public S<int, Tree<StateContent<int, T>>> MLabel1<T>(Tree<T> tree)
    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))))));
    }
    }
  2. simoneb revised this gist Apr 14, 2013. 1 changed file with 11 additions and 11 deletions.
    22 changes: 11 additions & 11 deletions monadic-labeling.cs
    Original file line number Diff line number Diff line change
    @@ -89,27 +89,27 @@ public StateContent<TState, T> stateContent<TState, T>(TState state, T value)
    return new StateContent<TState, T>(state, value);
    }

    public class S<T>
    public class S<TState, T>
    {
    public Func<int, Tuple<int, T>> RunWithState;
    public Func<TState, Tuple<TState, T>> RunWithState;
    }

    public static S<U> Bind<T, U>(S<T> m, Func<T, S<U>> k)
    public static S<TState, U> Bind<TState, T, U>(S<TState, T> m, Func<T, S<TState, U>> k)
    {
    return new S<U>
    return new S<TState, U>
    {
    RunWithState = s0 =>
    {
    Tuple<int, T> mResult = m.RunWithState(s0);
    Tuple<TState, T> mResult = m.RunWithState(s0);

    return k(mResult.Item2).RunWithState(mResult.Item1);
    }
    };
    }

    public static S<T> Return<T>(T value)
    public static S<TState, T> Return<TState, T>(T value)
    {
    return new S<T>
    return new S<TState, T>
    {
    RunWithState = s => Tuple.Create(s, value)
    };
    @@ -120,26 +120,26 @@ public Tree<StateContent<int, T>> MLabel<T>(Tree<T> tree)
    return MLabel1(tree).RunWithState(0).Item2;
    }

    public S<Tree<StateContent<int, T>>> MLabel1<T>(Tree<T> tree)
    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>
    var updateState = new S<int, int>
    {
    RunWithState = s0 => Tuple.Create(s0 + 1, s0)
    };

    return Bind(updateState,
    label => Return(leaf(stateContent(label, lf.Value))));
    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(branch(left, right))));
    right => Return<int, Tree<StateContent<int, T>>>(branch(left, right))));
    }
    }
  3. simoneb revised this gist Apr 7, 2013. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions monadic-labeling.cs
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,5 @@
    <Query Kind="Program" />

    void Main()
    {
    var tree = branch(
  4. simoneb revised this gist Apr 7, 2013. 1 changed file with 10 additions and 12 deletions.
    22 changes: 10 additions & 12 deletions monadic-labeling.cs
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,3 @@
    <Query Kind="Program" />

    void Main()
    {
    var tree = branch(
    @@ -57,20 +55,20 @@ public override void Show(int indent)
    }
    }

    public class Labeled<T>
    public class StateContent<TState, T>
    {
    public int Label { get; private set; }
    public TState State { get; private set; }
    public T Value { get; private set; }

    public Labeled(int label, T value)
    public StateContent(TState state, T value)
    {
    Label = label;
    State = state;
    Value = value;
    }

    public override string ToString()
    {
    return new { Label, Value }.ToString();
    return new { State, Value }.ToString();
    }
    }

    @@ -84,9 +82,9 @@ 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)
    public StateContent<TState, T> stateContent<TState, T>(TState state, T value)
    {
    return new Labeled<T>(label, value);
    return new StateContent<TState, T>(state, value);
    }

    public class S<T>
    @@ -115,12 +113,12 @@ public static S<T> Return<T>(T value)
    };
    }

    public Tree<Labeled<T>> MLabel<T>(Tree<T> tree)
    public Tree<StateContent<int, T>> MLabel<T>(Tree<T> tree)
    {
    return MLabel1(tree).RunWithState(0).Item2;
    }

    public S<Tree<Labeled<T>>> MLabel1<T>(Tree<T> tree)
    public S<Tree<StateContent<int, T>>> MLabel1<T>(Tree<T> tree)
    {
    if(tree is Leaf<T>)
    {
    @@ -132,7 +130,7 @@ public S<Tree<Labeled<T>>> MLabel1<T>(Tree<T> tree)
    };

    return Bind(updateState,
    label => Return(leaf(labeled(label, lf.Value))));
    label => Return(leaf(stateContent(label, lf.Value))));
    }
    else
    {
  5. simoneb renamed this gist Apr 7, 2013. 1 changed file with 0 additions and 0 deletions.
    File renamed without changes.
  6. simoneb renamed this gist Apr 7, 2013. 1 changed file with 0 additions and 0 deletions.
    File renamed without changes.
  7. simoneb created this gist Apr 7, 2013.
    145 changes: 145 additions & 0 deletions gistfile1.cs
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,145 @@
    <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))));
    }
    }