using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace StateMonad
{
    public class Unit
    {
        public static readonly Unit Value = new Unit();

        private Unit() { }
    }

    /// <summary>
    /// State-content pair
    /// </summary>
    /// <typeparam name="S">Type of State</typeparam>
    /// <typeparam name="C">Type of Content</typeparam>
    public class Scp<S,C>
    {
        public Scp(S state, C content)
        {
            State = state;
            Content = content;
        }

        public S State { get; private set; }
        public C Content { get; private set; }

        public override string ToString()
        {
            return "{" + State + ", " + Content + "}";
        }
    }

    /// <summary>
    /// State monad
    /// </summary>
    /// <typeparam name="S">Type of State</typeparam>
    /// <typeparam name="C">Type of Content</typeparam>
    public class StateMonad<S, C>
    {
        public StateMonad(Func<S, Scp<S, C>> s2Scp)
        {
            S2Scp = s2Scp;
        }

        /// <summary>
        /// State to state-content pair
        /// </summary>
        public Func<S,Scp<S,C>> S2Scp { get; private set; }

    }

    /// <summary>
    /// State monad operations
    /// </summary>
    public static class StateMonad
    {
        /// <summary>
        /// "return" monadic operator
        /// </summary>
        /// <typeparam name="S">Type of State</typeparam>
        /// <typeparam name="C">Type of Content</typeparam>
        /// <param name="content">Content</param>
        /// <returns>State monad</returns>
        public static StateMonad<S, C> Return<S, C>(C content)
        {
            return new StateMonad<S, C>(s => new Scp<S, C>(s, content));
        }

        /// <summary>
        /// "return" monadic operator
        /// </summary>
        /// <typeparam name="S">Type of State</typeparam>
        /// <typeparam name="C">Type of Content</typeparam>
        /// <param name="dummy">Dummy argument for type inference</param>
        /// <param name="content">Content</param>
        /// <returns>State monad</returns>
        public static StateMonad<S, C> Return<S, C>(S dummy, C content)
        {
            return new StateMonad<S, C>(s => new Scp<S, C>(s, content));
        }

        /// <summary>
        /// "bind" monadic operator
        /// </summary>
        /// <param name="m">State monad</param>
        /// <param name="selector">Selector function</param>
        /// <returns>State monad</returns>
        public static StateMonad<S, C2> SelectMany<S, C1, C2>(this StateMonad<S, C1> m, Func<C1, StateMonad<S, C2>> selector)
        {
            return new StateMonad<S, C2>(s =>
                {
                    var scp = m.S2Scp(s);
                    return selector(scp.Content).S2Scp(scp.State);
                });
        }

        /// <summary>
        /// "bind" monadic operator
        /// </summary>
        /// <param name="m">State monad</param>
        /// <param name="selector">Selector function</param>
        /// <param name="result">Map result function</param>
        /// <returns>State monad</returns>
        public static StateMonad<S, C2> SelectMany<S, C1, C2, K>(this StateMonad<S, C1> m, Func<C1, StateMonad<S, K>> selector, Func<C1, K, C2> result)
        {
            return m.SelectMany(x => selector(x).SelectMany(y => Return<S,C2>(result(x, y))));
        }

        /// <summary>
        /// Select method for Query Pattern
        /// </summary>
        /// <param name="m">State monad</param>
        /// <param name="selector">Selector function</param>
        /// <returns>State monad</returns>
        public static StateMonad<S, C2> Select<S, C1, C2>(this StateMonad<S, C1> m, Func<C1, C2> selector)
        {
            return new StateMonad<S, C2>(s => 
            {
                var scp = m.S2Scp(s);
                return new Scp<S, C2>(scp.State, selector(scp.Content));
            });
        }

        /// <summary>
        /// State monad "get state" function
        /// </summary>
        /// <typeparam name="S">Type of state</typeparam>
        public static StateMonad<S, S> Get<S>()
        {
            return new StateMonad<S, S>(s => new Scp<S, S>(s, s));
        }

        /// <summary>
        /// State monad "put state" function
        /// </summary>
        /// <typeparam name="S">Type of state</typeparam>
        /// <param name="s">New state</param>
        public static StateMonad<S, Unit> Put<S>(S s)
        {
            return new StateMonad<S, Unit>(_ => new Scp<S, Unit>(s, Unit.Value));
        }
    }

    /// <summary>
    /// Tree constructor
    /// </summary>
    public static class Tr
    {
        /// <summary>
        /// Creates new Leaf
        /// </summary>
        /// <typeparam name="T">Type of content</typeparam>
        /// <param name="content">Content of Leaf</param>
        /// <returns>Binary tree</returns>
        public static Tr<T> Lf<T>(T content)
        {
            return new Lf<T>(content);
        }

        /// <summary>
        /// Creates new Branch
        /// </summary>
        /// <typeparam name="T">Type of content</typeparam>
        /// <param name="left">Left subtree</param>
        /// <param name="right">Right subtree</param>
        /// <returns>Binary tree</returns>
        public static Tr<T> Br<T>(Tr<T> left, Tr<T> right)
        {
            return new Br<T>(left, right);
        }
    }

    /// <summary>
    /// Base class for binary tree node
    /// </summary>
    /// <typeparam name="T">Type of content</typeparam>
    public abstract class Tr<T>
    {
        protected const int Ident = 2;

        /// <summary>
        /// Print node
        /// </summary>
        /// <param name="level"></param>
        public abstract void Show(int level);
    }

    /// <summary>
    /// Branch of binary tree
    /// </summary>
    /// <typeparam name="T">Type of content</typeparam>
    public class Br<T> : Tr<T>
    {
        public Br(Tr<T> left, Tr<T> right)
        {
            Left = left;
            Right = right;
        }

        /// <summary>
        /// Left subtree
        /// </summary>
        public Tr<T> Left { get; private set; }

        /// <summary>
        /// Right subtree
        /// </summary>
        public Tr<T> Right { get; private set; }

        public override void Show(int level)
        {
            Console.Write(new String(' ', level * Ident));
            Console.WriteLine("Branch:");
            Left.Show(level + 1);
            Right.Show(level + 1);
        }
    }

    /// <summary>
    /// Leaf of binary tree
    /// </summary>
    /// <typeparam name="T">Type of content</typeparam>
    public class Lf<T> : Tr<T>
    {
        public Lf(T content)
        {
            Content = content;
        }

        /// <summary>
        /// Content
        /// </summary>
        public T Content { get; private set; }

        public override void Show(int level)
        {
            Console.Write(new String(' ', level * Ident));
            Console.Write("Leaf: ");
            Console.Write(Content);
            Console.WriteLine();
        }
    }

    class Program
    {
        /// <summary>
        /// Monadic tree labeling
        /// </summary>
        /// <typeparam name="T">Type of content</typeparam>
        /// <param name="tree">Binary tree</param>
        /// <returns>State monad with binary tree with label-contents pair</returns>
        static StateMonad<int, Tr<Scp<int,T>>> GetLabelMonad<T>(Tr<T> tree)
        {
            if (tree is Lf<T>)
            {
                var leaf = tree as Lf<T>;
                var m = from s in StateMonad.Get<int>()
                        from _ in StateMonad.Put(s + 1)
                        from r in StateMonad.Return(0 /*dummy arg*/, Tr.Lf(new Scp<int, T>(s, leaf.Content)))
                        select r;
                return m;
            }
            else if(tree is Br<T>)
            {
                var br = tree as Br<T>;
                var m = from l in GetLabelMonad(br.Left)
                        from r in GetLabelMonad(br.Right)
                        from res in StateMonad.Return(0 /*dummy arg*/, Tr.Br(l, r))
                        select res;
                return m;
            }
            else
            {
                throw new Exception("Invalid object type");
            }
        }

        static void Main(string[] args)
        {
            var tree = 
                Tr.Br
                (
                    Tr.Br(
                        Tr.Lf(1),
                        Tr.Br(Tr.Lf(2), Tr.Lf(3))
                         ),
                    Tr.Lf(4)
                );
            tree.Show(0);
            Console.WriteLine();

            var m = GetLabelMonad(tree);

            var res = m.S2Scp(0);
            
            Console.WriteLine(res.State);
            res.Content.Show(0);

            Console.ReadLine();
        }
    }
}

G>Кто-нибудь может объяснить как оно работает?

      static StateMonad<int, Node<StateM<int, T>>> GetLabelMonad<T>(Node<T> tree)
        {
            if (tree is Leaf<T>)
            {
                var leaf = tree as Leaf<T>;
    
                var m = from s in StateMonad.Get<int>() // получили текучее значение счетчика листьев из монады
                        from _ in StateMonad.Put(s + 1) // инкрементировали его
                        from r in StateMonad.Return(0,Node.Leaf(new StateM<int, T>(s, leaf.Content))) // в листе ноды теперь нода с индексом
                        select r;
                return m;
            }

            else if (tree is Branch<T>)
            {
//  а эта ветка просто рекурсивный спуск. ничего интересного               
            }
            else
            {
                throw new Exception("Invalid object type");
            }
        }

using(int counter =0)
{
   foreach(var leaf in tree.Leaves)
   {
      leaf = new Pair<int, Leaf>(counter++, leaf)
   }
}

interface IHaveContext<T>
{
     T GetCurrentContext();
     SetCurrentContext(T val);
}

    static context:IHaveContext<int>

   foreach(var leaf in tree.Leaves)
   {
      var currentContext = context.GetCurrentConext();
      context.SetCurrentContext(currentContext.Value +1);

      leaf = new Pair<int, Leaf>(currentContext.Value, leaf)
   }

context1 : IHaveContext<bool>
context2 : IHaveContext<bool>
context3 : IHaveContext<bool>

context1 = SomeWierdOperationThatSucceeds();
if(context1)
    context2 = AnotherUgluSuccessOperation();
       if(context2) 
           context3 = AndThisOperaiontFails();
                if(context3)
                    return true;
else
   return false;

//простецкий интерфейс.
//Метод принимает на входе значение текущего контекста, функцию которую надо выполнить 
interface Joiner<T> : where T is IHaveContext<T>
{
     IHaveContext<T> Join(IHaveContext<T> currentContext, Action step);
}
// реализация интерфейса. Тоже тупа до безобразия
class ТруЪJoinier<T> : Joiner<T>
{
    IHaveContext<T> Join(currentContext, step)
   {
     if(currentContext == true)
      // намек на то, что функция, может получить текущий контекст
       var res = step(first)
       return res;
     else
       return false as IHaveContext;
   }
}

// А теперь наш код из предыдущего примера в более пригодном для употребления виде
var joiner = new ТруЪJoiner();

// Да, я в курсе, что тут напутано с типами, и количеством параметров. Важна описываемая идея, а не код
joiner.Join(true,SomeWierdOperationThatSucceeds).Join(AnotherUgluSuccessOperation).Join(AndThisOperaiontFails);

var joiner = new ТруЪJoiner();

var joiner = new FalseJoiner();

G>                var m = from s in StateMonad.Get<int>()
G>                        from _ in StateMonad.Put(s + 1)
G>                        from r in StateMonad.Return(0 /*dummy arg*/, Tr.Lf(new Scp<int, T>(s, leaf.Content)))
G>                        select r;

G>        public static StateMonad<S, C2> SelectMany<S, C1, C2>(this StateMonad<S, C1> m, Func<C1, StateMonad<S, C2>> selector)
G>        {
G>            return new StateMonad<S, C2>(s =>
G>                {
G>                    var scp = m.S2Scp(s);
G>                    return selector(scp.Content).S2Scp(scp.State);
G>                });
G>        }

G>            return new StateMonad<S, C2>(s =>
G>                {
G>                    var scp = m.S2Scp(s);
G>                    return selector(scp.Content).S2Scp(scp.State);
G>                });

open System

type State<'a,'s> = State of ('s -> 'a * 's)

type StateBuilder() =

     (*  'a -> M<'a>  *)
     member b.Return(a) =
        State (fun s -> a, s)

     (*  M<'a> * ('a -> M<'b>) -> M<'b>  *)
     member b.Bind((State m), g) =
        State (fun s ->
        let (a, s') = m s in
        let (State f') = g a in f' s')


let getState   = State (fun s ->  s, s)
let setState s = State (fun _ -> (), s)

let Execute (State f) s = let x,_ = f s in x

let state = StateBuilder()

(*******************************************)

type Node<'a> =
   | Branch of 'a Node * 'a Node
   | Leaf   of 'a

   member node.Show(ident) =
     String(' ', ident) |> printf "%s"
     match node with
     | Leaf(x)     -> printfn "Leaf: %A" x
     | Branch(a,b) -> printfn "Branch:"
                      a.Show(ident+2)
                      b.Show(ident+2)

let rec labelMonad = function
  | Leaf(x) ->
    state { let! s = getState
            do! setState (s+1)
            return Leaf(x,s) }
  | Branch(a,b) ->
    state { let! l = labelMonad a
            let! r = labelMonad b
            return Branch(l,r) }

let tree =
    Branch(
      Branch(
        Leaf 1,
        Branch(Leaf 2, Leaf 3)),
      Leaf 4);

tree.Show(0)

let m   = labelMonad tree
let res = Execute m 0

res.Show(0)

                var m = from s in StateMonad.Get<int>()
                        from _ in StateMonad.Put(s + 1) // игнорируется значение
                        from r in StateMonad.Return(0 /*dummy arg*/, Tr.Lf(new Scp<int, T>(s, leaf.Content)))
                        select r;

П>>let setState s = State (fun _ -> (), s)
П>>let rec labelMonad = function
П>>  | Leaf(x) ->
П>>    state { let! s = getState
П>>            do! setState (s+1) // тут мы игнорим значение этой функции.
П>>            return Leaf(x,s) }
П>>  | Branch(a,b) ->
П>>    state { let! l = labelMonad a
П>>            let! r = labelMonad b
П>>            return Branch(l,r) }
П>>

do! expr in cexpr

b.Bind(expr,(fun () -> «cexpr»))

J>                var m = from s in StateMonad.Get<int>()
J>                        from _ in StateMonad.Put(s + 1) // игнорируется значение
J>                        from r in StateMonad.Return(0 /*dummy arg*/, Tr.Lf(new Scp<int, T>(s, leaf.Content)))
J>                        select r;
J>

from s in StateMonad.Get<int>()

let rec labelMonad = function
  | Leaf(x) ->
    state.Bind(getState, fun s ->
     state.Bind(setState(s+1), fun () ->
      state.Return(Leaf(x,s))))
  | Branch(a,b) ->
    state.Bind(labelMonad a, fun l ->
     state.Bind(labelMonad b, fun r ->
      state.Return(Branch(l,r))))

static StateMonad<int, Tr<Scp<int,T>>> GetLabelMonad<T>(Tr<T> tree)
{
    if (tree is Lf<T>)
    {
        var leaf = tree as Lf<T>;
        var m =
            StateMonad.Get<int>().SelectMany(s =>
              StateMonad.Put(s + 1).SelectMany(_ =>
                StateMonad.Return(0, Tr.Lf(new Scp<int, T>(s, leaf.Content)))));

        return m;
    }
    else if(tree is Br<T>)
    {
        var br = tree as Br<T>;

      var m =
          GetLabelMonad(br.Left).SelectMany(l =>
            GetLabelMonad(br.Right).SelectMany(r =>
              StateMonad.Return(0, Tr.Br(l, r))));

        return m;
    }
    else
    {
        throw new Exception("Invalid object type");
    }
}