Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.");
}
share|improve this question
    
Could you add an example of how would you use it? –  svick Mar 7 '13 at 18:28
    
Thanks for the tags, whoever that was –  jcarpenter Mar 8 '13 at 1:26
    
I find putting bind in a static extension or directly on the type in C# gives the fluency that feels more like the bind's infix operator, think about State 42 >>= return vs new State(0, 42).Bind(Return) –  Jimmy Hoffa Mar 28 '13 at 6:49
add comment

2 Answers

  • 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.

share|improve this answer
add comment

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

// State a
internal class State<TResult>
{
    // State a t
    public struct StateData<TState>
    {
        private readonly TResult result;

        private readonly TState state;

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

        public TResult Result
        {
            get
            {
                return this.result;
            }
        }

        public TState State
        {
            get
            {
                return this.state;
            }
        }
    }

    // return :: t -> m t
    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 new StateData<TNewState>(monadicValue.Result, func(monadicValue.State));
    }
}
share|improve this answer
    
That's convenient. –  jcarpenter Mar 8 '13 at 1:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.