Category Theory via C# (19) More Monad: State< , > Monad

Thursday, December 20, 2018

[LINQ via C# series]

[Category Theory via C# series]

Latest version: https://weblogs.asp.net/dixin/category-theory-via-csharp-8-more-linq-to-monads

C#/.NET state machines

State machine (or finite state machine) represents a abstract machine with one state or a number of state. C# use state machine a lot. For example:

C# yield keyword compiles to a state machine that implements IEnumerable<T>
C# await keyword compiles to a state machine that implements IAsyncStateMachine

.NET has a lot of built-in state machines too:

System.Activities.Statements.StateMachine
System.Web.Razor.StateMachine<TReturn>
System.Xml.Xsl.XsltOld.StateMachine
Microsoft.Transactions.Bridge.Dtc.StateMachine, and its 6 derived classes
Microsoft.Transactions.Wsat.StateMachines.StateMachine, and its 9 derived classes

etc.

State pattern in object-oriented programming

State pattern is a typical way to implement state machine. The following picture is stolen from Wikipedia:

Traffic light state machine

A very simple example of (finite) state machine is traffic light. Assume a traffic light state machine has 3 state:

It starts with green state, and stays green for 3 seconds
Then it mutates to yellow state for 1 second
Then it mutates to red state, for 2 seconds

The code will just follow above diagram. Here are the states’ definitions:

public interface ITrafficLightState // State
{
    Task Handle(TrafficLightStateMachine light);
}

public class GreenState : ITrafficLightState // ConcreteStateA
{
    public async Task Handle(TrafficLightStateMachine light)
    {
        TraceHelper.TypeName(typeof(GreenState));
        await Task.Delay(3000);
        await light.MoveNext(new YellowState());
    }
}

public class YellowState : ITrafficLightState // ConcreteStateB
{
    public async Task Handle(TrafficLightStateMachine light)
    {
        TraceHelper.TypeName(typeof(YellowState));
        await Task.Delay(1000);
        await light.MoveNext(new RedState());
    }
}

public class RedState : ITrafficLightState // ConcreteStateC
{
    public async Task Handle(TrafficLightStateMachine light)
    {
        TraceHelper.TypeName(typeof(RedState));
        await Task.Delay(2000);
        // await light.MoveNext(new GreenState());
    }
}

where TraceHelper.TypeName is just:

public static partial class TraceHelper
{
    public static Unit TypeName(Type type)
    {
        Trace.WriteLine($"{DateTime.Now.ToString("o", CultureInfo.InvariantCulture)}: {type.Name}");
        return null;
    }
}

Notice Trace.TypeName and all Handle method implementations have side effects (write trace messages). And, in typical C# programming and OOP, side effect is not specially managed.

The state machine will be:

public class TrafficLightStateMachine
{
    public ITrafficLightState State { get; private set; }

    public async Task MoveNext(ITrafficLightState state = null)
    {
        this.State = state ?? new GreenState();
        await this.State.Handle(this);
    }
}

Notice the state machine is mutable. The underlined code updates the state of the state machine.

Running the state machine:

new TrafficLightStateMachine().MoveNext().Wait();

can result the following trace message:

2015-05-24T16:19:08.2431705-07:00 - GreenState
2015-05-24T16:19:11.2530920-07:00 - YellowState
2015-05-24T16:19:12.2549302-07:00 - RedState

State<> monad

In purely functional programming, objects are immutable, state cannot just be updated when changing. State monad can be used to thread a state parameter through a sequence of functions to represent the state updating.

This is the definition of state monad:

// State<T, TState> is alias of Func<TState, Lazy<T, TState>>
public delegate Lazy<T, TState> State<T, TState>(TState state);

As usual, its SelectMany will be defined firstly:

[Pure]
public static partial class StateExtensions
{
    // Required by LINQ.
    public static State<TResult, TState> SelectMany<TSource, TState, TSelector, TResult>
        (this State<TSource, TState> source,
         Func<TSource, State<TSelector, TState>> selector,
         Func<TSource, TSelector, TResult> resultSelector) =>
            state => new Lazy<TResult, TState>(() =>
                {
                    Lazy<TSource, TState> sourceResult = source(state);
                    Lazy<TSelector, TState> selectorResult = selector(sourceResult.Value1)(sourceResult.Value2);
                    return Tuple.Create(
                        resultSelector(sourceResult.Value1, selectorResult.Value1),
                        selectorResult.Value2);
                });

    // Not required, just for convenience.
    public static State<TResult, TState> SelectMany<TSource, TState, TResult>
        (this State<TSource, TState> source, Func<TSource, State<TResult, TState>> selector) =>
            source.SelectMany(selector, Functions.False);
}

so that:

// [Pure]
public static partial class StateExtensions
{
    // η: T -> State<T, TState>
    public static State<T, TState> State<T, TState>
        (this T value) => state => new Lazy<T, TState>(value, state);

    // η: T -> State<T, TState>
    public static State<T, TState> State<T, TState>
        (this T value, Func<TState, TState> newState) =>
            oldState => new Lazy<T, TState>(value, newState(oldState));

    // φ: Lazy<State<T1, TState>, State<T2, TState>> => State<Defer<T1, T2>, TState>
    public static State<Lazy<T1, T2>, TState> Binary<T1, T2, TState>
        (this Lazy<State<T1, TState>, State<T2, TState>> binaryFunctor) =>
            binaryFunctor.Value1.SelectMany(
                value1 => binaryFunctor.Value2,
                (value1, value2) => new Lazy<T1, T2>(value1, value2));

    // ι: TUnit -> State<TUnit, TState>
    public static State<Unit, TState> Unit<TState>
        (Unit unit) => unit.State<Unit, TState>();

    // Select: (TSource -> TResult) -> (State<TSource, TState> -> State<TResult, TState>)
    public static State<TResult, TState> Select<TSource, TResult, TState>
        (this State<TSource, TState> source, Func<TSource, TResult> selector) =>
            source.SelectMany(value => selector(value).State<TResult, TState>());
}

State<> is monad, monoidal functor, and functor.

Also a few other helper functions:

// [Pure]
public static partial class StateExtensions
{
    public static TSource Value<TSource, TState>
        (this State<TSource, TState> source, TState state) => source(state).Value1;

    public static TState State<T, TState>
        (this State<T, TState> source, TState state) => source(state).Value2;
}

[Pure]
public static class State
{
    public static State<TState, TState> Get<TState>
        () => state => new Lazy<TState, TState>(state, state);

    public static State<TState, TState> Set<TState>
        (TState newState) => oldState => new Lazy<TState, TState>(oldState, newState);

    public static State<TState, TState> Set<TState>
        (Func<TState, TState> newState) => oldState => new Lazy<TState, TState>(oldState, newState(oldState));
}

Traffic light state machine with State<> monad and LINQ

Now everything becomes functions. This is the definition of the traffic light state:

public delegate IO<Task<TrafficLightState>> TrafficLightState();

Not interface any more.

And each state is a pure function of above type:

// Impure.
public static partial class StateQuery
{
    [Pure]
    public static IO<Task<TrafficLightState>> GreenState
        () =>
            from _ in TraceHelper.Log(nameof(GreenState))
            select (from __ in Task.Delay(TimeSpan.FromSeconds(3))
                    select new TrafficLightState(YellowState));

    [Pure]
    public static IO<Task<TrafficLightState>> YellowState
        () =>
            from _ in TraceHelper.Log(nameof(YellowState))
            select (from __ in Task.Delay(TimeSpan.FromSeconds(1))
                    select new TrafficLightState(RedState));

    [Pure]
    public static IO<Task<TrafficLightState>> RedState
        () =>
            from _ in TraceHelper.Log(nameof(RedState))
            select (from __ in Task.Delay(TimeSpan.FromSeconds(2))
                    select default(TrafficLightState));
}

where Trace.Log is a pure function too:

[Pure]
public static partial class TraceHelper
{
    public static IO<Unit> Log
        (string log) =>
            () =>
                {
                    Trace.WriteLine($"{DateTime.Now.ToString("o", CultureInfo.InvariantCulture)} - {log}");
                    return null;
                };
}

Please also notice Task.Delay returns a Task (not Task<>). As mentioned in an earlier part, Task can be viewed as Task<Unit>, a special case of Task<>. So the LINQ syntax works for Task.

The state machine is also pure function:

// Impure.
public static partial class StateQuery
{
    [Pure]
    public static State<Unit, IO<Task<TrafficLightState>>> MoveNext
        () =>
            ((Unit)null).State<Unit, IO<Task<TrafficLightState>>>(state => async () =>
                {
                    TrafficLightState next = await (state ?? GreenState())();
                    return next == null ? null : await next()();
                });

    [Pure]
    public static IO<Task<TrafficLightState>> TrafficLight(IO<Task<TrafficLightState>> state = null)
    {
        State<Unit, IO<Task<TrafficLightState>>> query =
            from green in MoveNext()
            from yellow in MoveNext()
            from red in MoveNext()
            select (Unit)null; // Deferred and lazy.
        return query.State(state); // Final state.
    }
}

Running this state machine with State<> monad:

// Impure.
public static partial class StateQuery
{
    public static async void ExecuteTrafficLight() => await TrafficLight()();
}

will result similar trace message:

04/02/2015 20:44:30 - GreenState
04/02/2015 20:44:33 - YellowState
04/02/2015 20:44:34 - RedState

Immutable IEnumerable<T> stack

An easier example could be using a immutable IEnumerable<T> to simulate a mutable stack. Firstly, a Pop and a Push function can be implemented:

// [Pure]
public static partial class EnumerableExtensions
{
    public static Lazy<T, IEnumerable<T>> Pop<T>
        (this IEnumerable<T> source) =>
            // The execution of First is deferred, so that Pop is still pure.
            new Lazy<T, IEnumerable<T>>(source.First, () => source.Skip(1));

    public static Lazy<T, IEnumerable<T>> Push<T>
        (this IEnumerable<T> source, T value) =>
            new Lazy<T, IEnumerable<T>>(value, source.Concat(value.Enumerable()));
}

So a stateful stack can be implemented as:

// Impure.
public static partial class StateQuery
{
    [Pure]
    public static State<T, IEnumerable<T>> Pop<T>
        () => source => source.Pop();

    [Pure]
    public static State<T, IEnumerable<T>> Push<T>
        (T value) => source => source.Push(value);

    [Pure]
    public static IEnumerable<int> Stack(IEnumerable<int> state = null)
    {
        state = state ?? Enumerable.Empty<int>();
        State<IEnumerable<int>, IEnumerable<int>> query =
            from value1 in Push(1)
            from value2 in Push(2)
            from value3 in Pop<int>()
            from stack1 in State.Set(Enumerable.Range(0, 3))
            from value4 in Push(4)
            from value5 in Pop<int>()
            from stack2 in State.Get<IEnumerable<int>>()
            select stack2;
        return query.Value(state);
    }
}

The above functions are all pure functions, and IEnumerable<int> is immutable. They clearly demonstrated how State<> monad simulates the state updating - after each call of Push, Pop, or Set, a new IEnumerable<T> is created to pass to the next function in the sequence.

[TestClass]
public class StackTests
{
    [TestMethod]
    public void StateMachineTest()
    {
        IEnumerable<int> expected = Enumerable.Range(0, 3).Push(4).Value2.Pop().Value2;
        IEnumerable<int> actual = StateQuery.Stack();
        EnumerableAssert.AreEqual(expected, actual);
    }
}

Monad laws, and unit tests

public partial class MonadTests
{
    [TestMethod]
    public void StateTest()
    {
        bool isExecuted1 = false;
        bool isExecuted2 = false;
        Func<State<int, string>> f1 = () => 1.State<int, string>(
            state => { isExecuted1 = true; return state + "a"; });
        Func<int, Func<int, Func<string, int>>> f2 =
            x => y => z => { isExecuted2 = true; return x + y + z.Length; };
        State<int, string> query1 = from x in f1()
                                    from _ in State.Set(x.ToString(CultureInfo.InvariantCulture))
                                    from y in 2.State<int, string>(state => "b" + state)
                                    from z in State.Get<string>()
                                    select f2(x)(y)(z);
        Assert.IsFalse(isExecuted1); // Deferred and lazy.
        Assert.IsFalse(isExecuted2); // Deferred and lazy.
        Lazy<int, string> result1 = query1("state"); // Execution.
        Assert.AreEqual(1 + 2 + ("b" + "1").Length, result1.Value1);
        Assert.AreEqual("b" + "1", result1.Value2);
        Assert.IsTrue(isExecuted1);
        Assert.IsTrue(isExecuted2);

        // Monad law 1: m.Monad().SelectMany(f) == f(m)
        Func<int, State<int, string>> addOne = x => (x + 1).State<int, string>();
        State<int, string> left = 1.State<int, string>().SelectMany(addOne);
        State<int, string> right = addOne(1);
        Assert.AreEqual(left.Value("a"), right.Value("a"));
        Assert.AreEqual(left.State("a"), right.State("a"));
        // Monad law 2: M.SelectMany(Monad) == M
        State<int, string> M = 1.State<int, string>();
        left = M.SelectMany(StateExtensions.State<int, string>);
        right = M;
        Assert.AreEqual(left.Value("a"), right.Value("a"));
        Assert.AreEqual(left.State("a"), right.State("a"));
        // Monad law 3: M.SelectMany(f1).SelectMany(f2) == M.SelectMany(x => f1(x).SelectMany(f2))
        Func<int, State<int, string>> addTwo = x => (x + 2).State<int, string>();
        left = M.SelectMany(addOne).SelectMany(addTwo);
        right = M.SelectMany(x => addOne(x).SelectMany(addTwo));
        Assert.AreEqual(left.Value("a"), right.Value("a"));
        Assert.AreEqual(left.State("a"), right.State("a"));
    }
}

https://ma-study.blogspot.com/

medicalphd - Monday, December 13, 2021 12:29:27 PM

It's too bad to check your article late. I wonder what it would be if we met a little faster. I want to exchange a little more, but please visit my site Keo nha cai and leave a message!!

Keo nha cai - Wednesday, August 17, 2022 9:01:55 PM

Unfortunately, you checked your article too late. If we met a bit sooner, I wonder what it would be like. Please stop by my website, Keo nha cai, and leave a message if you'd like to continue our conversation.

geometry dash - Thursday, August 18, 2022 12:28:54 AM

I've been troubled for several days with this topic. But by chance looking at your post solved my problem! I will leave my blog, so when would you like to visit it?

totosite - Tuesday, September 27, 2022 7:35:18 PM

I am very impressed with your writing <a href="https://google.je/url?sa=t&url=https%3A%2F%2Fwww.mtclean.blog/">baccaratcommunity</a> I couldn't think of this, but it's amazing! I wrote several posts similar to this one, but please come and see!

baccaratcommunity - Wednesday, November 22, 2023 10:54:09 PM

Hello ! I am the one who writes posts on these topics <a href="https://google.it/url?sa=t&url=https%3A%2F%2Fwww.mtclean.blog/">casinocommunity</a> I would like to write an article based on your article. When can I ask for a review?

casinocommunity - Wednesday, November 22, 2023 10:54:33 PM

I was looking for another article by chance and found your article <a href="https://google.is/url?sa=t&url=https%3A%2F%2Fwww.mtclean.blog/">majorsite</a> I am writing on this topic, so I think it will help a lot. I leave my blog address below. Please visit once.

majorsite - Wednesday, November 22, 2023 10:55:04 PM

I came to this site with the introduction of a friend around me and I was very impressed when I found your writing. I'll come back often after bookmarking! <a href="https://google.iq/url?sa=t&url=https%3A%2F%2Fwww.mtclean.blog/">bitcoincasino</a>

bitcoincasino - Wednesday, November 22, 2023 10:57:11 PM

International students typically face a multitude of new challenges. Language barriers, varying academic norms, and shifts in educational methodologies can make the academic path complex. These factors combined may lead to stress and discomfort as international students adapt to their new environment, affecting their academic performance.

http://www.meeloun.com/ - Wednesday, January 17, 2024 12:45:48 AM

Fantastic work! This really can be the kind of data which needs to really be shared round the internet.

카지노 - Tuesday, May 14, 2024 3:22:24 AM

It is very well written, and your points are well-expressed. I request you warmly, please, don’t ever stop writing.

카지노 - Tuesday, May 14, 2024 3:25:41 AM

Thanks for sharing with us this important Content. I feel strongly about it and really enjoyed learning more about this topic.

바카라 - Tuesday, May 14, 2024 3:29:40 AM

Dixin's Blog