State monad in OCaml

Question

I was trying to implement the state monad in OCaml (as an exercise). My implementation looks like this:

module type MONAD_BUILDER =
sig
  type 'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end;;

module MonadBuilder = functor (M: MONAD_BUILDER) ->
struct
  let ( >>= ) = M.bind
  let return = M.return
end;;

module StateM = 
struct
  type 'a state = { state: 's . 's -> ('a * 's) }
  type 'a t = 'a state
  let return x = { state = fun s -> (x, s) }
  let bind m f = 
    let aux s = 
      let (x, s') = m.state s in
      (f x).state s'
    in { state = aux }
  let run m x = fst (m.state x)
end;;

I chose the existential type for the record field since I don't like the idea of using a functor and wrapping the state type in a module. The above implementation works, but I ran into a problem while implementing getState and setState. I tried to implement them like:

let getState = { state = fun s -> (s, s) }

let setState s = { state = fun _ -> ((), s) }

This doesn't work since the inferred field types, e.g. 'a -> ('a * 'a) and 'a -> (unit * 'a), are less generic than the declared type 's . 's -> ('a * 's). I understand why this is happening, but I was wondering if there is another way of making it work using the record approach?

Thanks.

Cheers, Alex

Answer 1

's. 's -> ('a * 's) is an universal type. You're going to have a hard time implementing a state with universal types...

There's no clean way of encapsulating an existential type there without using a module (because existential types is what abstract types are for).

You could, of course, publish the state type instead:

type ('a,'s) state = { state : 's -> ('a * 's) } 

Or even shorter,

type ('a,'s) state = 's -> 'a * 's

With the additional parameter, your code runs. However, you run into the fact that your parameter must be handled by the monad. So, you can either hide it when building the monad:

module Monad = MonadBuilder(struct
  include StateM
  type 'a t = ('a,myStateType) state
end)

Or alter your monad design to incorporate an additional type parameter that is to be used for existential types:

module type MONAD_BUILDER =
sig
  type ('a,'param) t
  val return : 'a -> ('a,'param) t
  val bind : ('a,'param) t -> ('a -> ('b,'param) t) -> ('b,'param) t
end;;