haskell - OCaml 中的反向状态单子(monad)

Question

您将如何实现 reverse state monad在 OCaml ? (由于它严重依赖懒惰，我想必须使用标准库中的 Lazy 模块)。

Answer 1

我贴了Gist of a solution .

棘手的一点是:

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

正如我在评论中提到的，有点棘手的是你不想过早地意外地强制计算状态。不幸的是，为了使相互递归正确，您还被迫暂时使计算的答案(向前流动)变得懒惰。所以基本的经验法则是:

做类型告诉你做的事情。

切勿强制状态，除非在 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))

这看起来像口吃，但实际上正确地延迟了所有计算。