The reverse state monad in OCaml

Question

How would you implement the reverse state monad in OCaml? (Since it relies heavily on laziness, I guess one has to use the Lazy module from the standard library).

Answer 1

I put up a Gist of a solution.

The tricky bit is:

type 's l = 's Lazy.t
type ('a, 's) st = 's -> ('a * 's l)

let bind (mx : ('a, 's) st) (f : ('a -> ('b, 's) st)) (s : 's l) : ('b * 's l) =
  (* conceptually we want

         let rec (lazy (y, s'')) = lazy (mx s')
             and (lazy (z, s')) = lazy (f y s)
         in (force z, s'')

     but that's not legal Caml.

     So instead we get back lazy pairs of type ('a * 's l) l and we
     lazily project out the pieces that we need.
   *)
  let rec ys'' = lazy (mx (LazyUtils.join (LazyUtils.snd zs')))
    and (zs' : ('b * 's l) l) = lazy (f (Lazy.force (LazyUtils.fst ys'')) s)
  in (Lazy.force (LazyUtils.fst zs'), LazyUtils.join (LazyUtils.snd ys''))

As I mentioned in the comment, the somewhat tricky bit is that you don't want to accidentally force the computation of the state too soon. Unfortunately to get the mutual recursion right, you're also forced to temporarily make the computation's answers (which are flowing forward) lazy as well. So the basic rule of thumbs are:

1. Do what the types tell you to do.
2. Never force the state except under a lazy e construct.

In particular, LazyUtils.join : 'a Lazy.t Lazy.t -> 'a Lazy.t cannot be:

let join xll = Lazy.force xll

Because that would force the outer thunk too early. Instead it must be:

let join xll = lazy (Lazy.force (Lazy.force xll))

Which looks like stuttering, but in fact correctly delays all computation.