C# state monad implementation

Question

I want to know whether this thing I wrote in C# is a correct implementation of the state monad.

I've used it in code and it does what I expect it to do, but I'm still not quite sure if I'm doing this right, or if I just pulled something out of my ear and called it a state monad.

I would have made an IMonad<T> interface and used that to help test this, but that's not possible.

Anyway, here's the code:

// State a
class State<TResult>
{
    // State a t
    public struct StateData<TState>
    {
        public TResult result;
        public TState state;
    }

    // return :: t -> m t
    public static StateData<TState> Return<TState>(TState state) 
    {
        StateData<TState> monadicValue = new StateData<TState>();

        monadicValue.result = default(TResult);
        monadicValue.state = state;

        return monadicValue;
    }

    // (>>=) :: m t -> (t -> m u) -> m u
    public static StateData<TNewState> Bind<TState, TNewState>(StateData<TState> monadicValue, Func<TState, StateData<TNewState>> func)
    {
        StateData<TNewState> newMonadicValue = func(monadicValue.state);

        return newMonadicValue;
    }

    // liftM :: (t -> u) -> m t -> m u
    // liftM :: m t -> (t -> u) -> m u -- looks more similar to bind this way
    public static StateData<TNewState> Lift<TState, TNewState>(StateData<TState> monadicValue, Func<TState, TNewState> func)
    {
        StateData<TNewState> newMonadicValue = new StateData<TNewState>();

        newMonadicValue.result = monadicValue.result;
        newMonadicValue.state = func(monadicValue.state);

        return newMonadicValue;
    }
}

EDIT: You're not supposed to use mutable structs. Here in particular it's helpful to adhere to that, because the state object in the state monad isn't supposed to be mutable either. Ironically, I had to change StateData from a struct to a class to get the compiler to quit complaining about the constructor. Nonetheless, it is now immutable.

Also, I changed the Lift function so that it no longer passes through stale TResults.

Based on the type signatures and how quaint the code has become, I'm pretty sure this thing is indeed a state monad.

// State a
class State<TResult>
{
    // State a t
    public class StateData<TState>
    {
        public TResult Result { get; private set; }
        public TState State { get; private set; }

        public StateData(TResult result, TState state)
        {
            this.Result = result;
            this.State = state;
        }
    }

    // return :: a -> m a
    public static StateData<TState> Return<TState>(TState state)
    {
        return new StateData<TState>(default(TResult), state);
    }

    // (>>=) :: m t -> (t -> m u) -> m u
    public static StateData<TNewState> Bind<TState, TNewState>(StateData<TState> monadicValue, Func<TState, StateData<TNewState>> func)
    {
        return func(monadicValue.State);
    }

    // liftM :: (t -> u) -> m t -> m u
    // liftM :: m t -> (t -> u) -> m u -- looks more similar to bind this way
    public static StateData<TNewState> Lift<TState, TNewState>(StateData<TState> monadicValue, Func<TState, TNewState> func)
    {
        return Return(func(monadicValue.State));
    }
}

I tested this thing by making tic tac toe. The type of TResult is enum Player { Nobody, X, O } and the type of TState is GameState, which knows the board state and the next player. Here's the Main function for your enjoyment:

static void Main(string[] args)
{
    Console.WriteLine("Use the number pad to select a location.");
    State<Player>.StateData<GameState> game = State<Player>.Return<GameState>(new GameState());

    while (game.Result == Player.Nobody)
    {
        game = State<Player>.Lift<GameState, GameState>(game, nextPlayerMove);
        game = State<Player>.Lift<GameState, GameState>(game, drawBoard);
        game = State<Player>.Bind<GameState, GameState>(game, findWinner);
    }

    Console.WriteLine(game.Result.ToString() + " won.");
}

Answer 1

• You cannot have something named "X" theoretically does not mean you cannot have anything anyone at sometime thought to be "X". See my answer to another question for a feeling of what you can expect to get in the way of a monad pattern in an object oriented language.

• What really concerns me is this:

  // liftM :: m t -> (t -> u) -> m u -- looks more similar to bind this way
  

  Why is it called lift? Because it takes a function in and gives a function out, but in another domain. (t -> u) -> m t -> m u should be read as (t -> u) -> (m t -> m u), which translates to something like Func<Func<T, U>, Func<M<T>, M<U>>> in C#.

• You should not overwrite local variables, let alone repetitively, let alone in functional-style aspirant code:

  game = State<Player>.Lift<GameState, GameState>(game, nextPlayerMove);
  game = State<Player>.Lift<GameState, GameState>(game, drawBoard);
  game = State<Player>.Bind<GameState, GameState>(game, findWinner);
  

• You don't do Monad and while loop. You should use a foldM.

• Also noticed nextPlayerMove may do IO. In Haskell you would not have a function interleaved with a monad, unless it is a deterministic mathematical function. For example if it used Random numbers or IO you would need a monadic transformer, see StateT here.

In adopting functional paradigms, you should start with the low hanging fruits. Avoiding mutable state and preferring expressions over statements, etc. And look for opportunities for reification. Aim for making implicit patterns explicit (for example using applicative alternatives from IEnumerable/IQueryable instead of loops) , composability and as much compile time guarantees as possible.

Answer 2

Mutable structs in C#/.NET are evil for many reasons you can Google. Rewrite as such:

internal class State<TResult>
{
    // State a t
    public struct StateData<TState>
    {
        public StateData(TResult result, TState state)
        {
            this.Result = result;
            this.State = state;
        }

        public TResult Result { get; }

        public TState State { get; }
    }

    // return :: t -> m t
    public static StateData<TState> Return<TState>(TState state) => new StateData<TState>(default(TResult), state);

    // (>>=) :: m t -> (t -> m u) -> m u
    public static StateData<TNewState> Bind<TState, TNewState>(
        StateData<TState> monadicValue,
        Func<TState, StateData<TNewState>> func) => func(monadicValue.State);

    // liftM :: (t -> u) -> m t -> m u
    // liftM :: m t -> (t -> u) -> m u -- looks more similar to bind this way
    public static StateData<TNewState> Lift<TState, TNewState>(
        StateData<TState> monadicValue,
        Func<TState, TNewState> func) => new StateData<TNewState>(monadicValue.Result, func(monadicValue.State));
}