9

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
2
  • What is the question? Use a tuple where? The return type of the function is a tuple.
    – Brian
    Apr 7, 2010 at 20:39
  • No use a tuple instead of the State type and just return a function instead of a State.
    – thr
    Apr 7, 2010 at 20:45

3 Answers 3

15

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.

1
  • Thanks, Yes I have no intention of using the tuple version at all, I we were merely discussing it on IRC (##fsharp @ freenode) and none of us could see a technical reason for the State type.
    – thr
    Apr 8, 2010 at 8:55
7

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
5

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.

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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