def sum(list: List of int)
    summa = 0

    for (item in list)
        summa += item

    return summa

def foo
    x = 0
    y = bar(x)
    x = zzz(x, y)
    ...

def sum(list: List of int, accum: int)
    if list.empty
        then return accum
        else return sum(tail(list), accum + head(list))

let (x1,s1) = f0(x0, s0)
    (x2,s2) = f1(x1, s1)
    (x3,s3) = f2(x2, s2)
 in x3

global s

x1 = f0(x0)
x2 = f1(x1)
x3 = f2(x2)

return x3

f0(x0) THEN (x1 => f1(x1)) THEN (x2 => f2(x2)) THEN (x3 => RETURN x3)

fN :: a -> s -> (r,s)

THEN :: (s -> (r,s)) -> (r -> s -> (new_r, s)) -> (s -> (new_r, s))

type State<s, t> = s -> (t,s)

THEN :: State<s,r> -> (r -> State<s, new_r>) -> State<s, new_r>

def THEN(calc1: s => (r,s), calc2: r,s => (new_r,s), state0: s): (new_r, s)
    // у нас две функции и одна нормальная переменная
    // Пока применить эту переменную мы можем только к одной функции
    (res, state1) = calc1(state0)
    // у нас есть аргументы для второй функции
    (new_res, state2) = calc2(res, state1)
    // этот результат мы и возвращаем
    return (new_res, state2)

def RESULT(val: a, state: s): (a,s)
    // ну что мы ещё можем вернуть?
    return (val, state)

f0(x0)  THEN (x1 =>
f1(x1)) THEN (x2 =>
f2(x2)) THEN (x3 =>
RETURN x3)

def GET(state: s): (s,s)
    return (state, state)

def PUT(newState: s, state: s): ((),s)
    // забываем про state, у нас есть новое состояние
    return ((), newState)

// отличие! calc2 не принимает аргумент типа r
def THEN_(calc1: s => (r,s), calc2: s => (new_r,s), state0: s): (new_r, s)
    // объединяем вычисления, не использую результат первого во втором
    calc = calc1 THEN (_ => calc2)
    // запускаем вычисление с состоянием
    return calc(state0)

def TICK: State<int, ()>
    GET THEN (state =>
    PUT (state + 1))

def TICK3: State<int, ()>
    TICK THEN_
    TICK THEN_
    TICK

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))))

type List() = 
    static member Instance = List()
    member x.Return(v) = [v]
    member x.Bind(m, f) = List.collect f m    
let list = List()

type Maybe() = 
    static member Instance = Maybe()
    member x.Return(v) = Some(v)
    member x.Bind(m, f) = match m with | Some(v) -> f v | None -> None
let maybe = Maybe()
    
let inline ret b v = 
    (^b :  (member Return : ^v -> ^mv) (b, v))
    
let inline bind b m f = 
    (^b :  (member Bind : ^v * ^f -> ^mv) (b, m, f)) 

let inline lift2 b f x y =
    bind b x (fun x1 -> 
        bind b y (fun y1 -> ret b (f x1 y1))
    )

// None
let r = maybe {
        let (++) = lift2 maybe (+)
        return! Some(5) ++ None
    }    

// [0;2;1;3]    
let r2 = list {
        let (++) = lift2 list (+)
        return! [0;1] ++ [0;2]
    }

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();
        }
    }
}

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>Кто-нибудь может объяснить как оно работает?

      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");
            }
        }

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>()

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");
    }
}

let f () = 1

let f (() as x) = x

type MayBe<'a> = 
  | Just of 'a
  | None

type MayBeBuilder() = 
     (*  'a -> M<'a>  *)
     member b.Return(a) =
        Just a

     (*  M<'a> * ('a -> M<'b>) -> M<'b>  *)
     member b.Bind(m, g) =
        match m with
            | Just a -> g a
            | None   -> None

let mayBe = MayBeBuilder()

let getNone() = None

let result = mayBe {
    let! tmp = Just 10
    let! noneValue = None
    return tmp + noneValue    
 }
 
printf "%A" result

let getNone() = None
let getTen() = Just 10

let result = mayBe {
   let! ten = getTen()
   let! none = getNone()
   return ten + none
}

let result = mayBe {
    return getTen() + getNone()
 }

let liftToMaybe f x y = maybe {
    let! vx = x
    let! vy = y
    return f vx vy
    }
    
let res = 
    maybe {
        let (++) = liftToMaybe (+)
        return! get10() ++ get1()
    }

type Record1 = { age: int MayBe }
type Record2 = { rec1: Record1 MayBe }


let getRec2() = Just { rec1 = Just { age = Just 10 } }

let age = mayBe {
    let! rec2 = getRec2()
    let! rec1 = rec2.rec1
    let! age = rec1.age
    return age
}