严格语言中的MonadFix

Question

我正在为Ocaml中类似haskell的do符号开发camlp4扩展，并试图弄清楚GHC是如何编译递归do绑定的(通过-XDoRec实现的)。

我想知道是否有可能在严格的语言(如Ocaml/F#/SML/...)中存在一元定点组合器？

如果是，它看起来是什么样子的？它会非常有用吗？

Answer 1

Haskell计算表达式语法(与F# do相关)支持递归：

let rec ones = seq {
  yield 1
  yield! ones }

这是因为计算构建器除了支持其他一元(或MonadPlus)操作之外，还必须支持Delay操作。代码被翻译成类似如下的代码：

let rec ones = 
  seq.Combine
    ( seq.Yield(1),
      seq.Delay(fun () -> seq.YieldFrom(ones)) )

Delay的类型通常是(unit -> M<'T>) -> M<'T>，其诀窍在于它将具有效果的计算(或直接递归引用)包装到按需计算的延迟计算中。

如果您想更多地了解F#中的机制是如何工作的，那么以下两篇文章是相关的：

• Syntax Matters: Writing abstract computations in F#
• Initializing Mutually Referential Abstract Objects: The Value Recursion Challenge

第一个描述了如何对F#计算表达式语法进行去糖化(以及如何插入Delay -以及F#如何将延迟和急切的计算与效果相结合)，第二个描述了F#如何处理带有值的let rec声明-比如上面的ones值。