OCaml中的反向状态monad

Question

你如何在OCaml中实现反向状态monad？(因为它很大程度上依赖于懒惰,我想必须使用标准库中的Lazy模块).

Answer 1

我提出了一个解决方案的要点.

棘手的一点是:

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

因为这会过早地迫使外部的thunk.相反,它必须是:

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

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