Монада обратного состояния в OCaml

Я выложил суть решения.

Сложный момент:

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''))

Как я уже упоминал в комментарии, несколько хитрость заключается в том, что вы не хотите случайно принудительно вычислить состояние слишком рано. К сожалению, чтобы получить правильную взаимную рекурсию, вы также вынуждены временно сделать ответы вычислений (которые текут вперед) ленивыми. Итак, основные правила игры таковы:

1. Делайте то, что типы говорят вам делать.
2. Никогда не форсируйте состояние, кроме как в конструкции lazy e.

В частности, LazyUtils.join : 'a Lazy.t Lazy.t -> 'a Lazy.t не может быть:

let join xll = Lazy.force xll

Потому что это заставит внешний преобразователь слишком рано. Вместо этого должно быть:

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

Что выглядит как заикание, но на самом деле корректно задерживает все вычисления.