State Monad, why not a tuple?

Question

I've just wrapped my head around monads (at least I'd like to think I have) and more specifically the state monad, which some people that are way smarter then me figured out, so I'm probably way of with this question.

Anyway, the state monad is usually implemented with a M<'a> as something like this (F#):

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

Now my question: Is there any reason why you couldn't use a tuple here? Other then the possible ambiguity between MonadA<'a, 'b> and MonadB<'a, 'b> which would both become the equivalent ('a * 'b) tuple.

Edit: Added example for clarity

type StateMonad() =
  member m.Return a = (fun s -> a, s)
  member m.Bind(x, f) = (fun s -> let a, s_ = x s in f a s_)

let state = new StateMonad()
let getState = (fun s -> s, s)
let setState s = (fun _ -> (), s) 
let execute m s = m s |> fst

Answer 1

Ah, yes, if the question is: should I use a single-tag Discriminated Union that carries a data value of type T, or should I just use T, then you can use either.

In Haskell, you need to use a data tag with monads, since the Haskell do syntax infers the monad type based on value types (a tuple representation could be an instance of at most a single Monad). Whereas in F#, computation expressions are explicit about the monad type (e.g. state { ... } or async { ... } or whatever) so this restriction is not necessary, the same representation type could be used for multiple monads.

Answer 2

The State monad essentially works with a type 'state -> 'res * 'state, which represents a computation that takes some initial state and produces result (together with a new value of the state).

If you're asking whether it makes any difference whether we give some special name to this type (e.g. State<'state, 'res>) then the answer is it doesn't really matter. The only purpose of giving some special name to the type is that it makes the code more readable. For example, let's look at the two possible type signatures of the following example:

let foo n = state {
  let! m = getState()
  do! setState(m + 1)
  return sprintf "Result: %d" (n * m) }

// Using State<'state, 'res> type:
val foo : int -> State<int, string>

// Using the underlying representation:
val foo : int -> int -> int * state

The first type signature more clearly says that we're writing function in some monad. The second example is just a function that takes two int values. I think the main benefit of the first one is that you can more easily realize that the type can be used from other monadic computation (written using state { ... }).

However, as I already noted, this isn't a technical requirement. People probably use this style, because many monads come from Haskell, where monads are associated with the type (such as State<'state, 'res>) and not a computation builder (such as state), so it sounds like a good idea to define a new type for every monad in Haskell.

Answer 3

The type of the monadic value in your example isn't just a tuple - it is a function returning tuple:

'state -> 'res * 'state

If you're asking whether you can use just 'state * 'res as the type of the monadic computation, then the answer is no. That wouldn't work, because there is no way to (safely) implement the return operation, which would have to have the following type signature:

// how would we get a value of type 'state in the implementation?
val return : 'a -> 'state * 'a