延续传递样式计算表达式

Question

您可以使用 F# 中的计算表达式实现 CPS 吗？

Brian McNamara的博客给出了这个解决方案：

type ContinuationBuilder() = 
  member this.Return(x) = (fun k -> k x) 
  member this.ReturnFrom(x) = x 
  member this.Bind(m,f) = (fun k -> m (fun a -> f a k)) 
  member this.Delay(f) = f() 
let cps = ContinuationBuilder()

看起来不错。我可以在 CPS 中编写List.map：

let rec mapk f xs = cps {
  match xs with
  | [] -> return []
  | x::xs ->
      let! xs = mapk f xs
      return f x::xs
}

但它堆叠溢出：

mapk ((+) 1) [1..1000000] id

我做错了什么？

Answer 1

问题是计算生成器中的Delay函数会立即调用该函数 - 这意味着当您调用 mapk 时，它将立即运行模式匹配，然后递归调用mapk(在将其结果传递给 Bind 操作之前(。

您可以通过使用 Delay 的实现来解决此问题，该实现返回一个函数，该函数仅在给定最终延续后调用f - 这样，递归调用将只返回一个函数(不执行导致堆栈溢出的更多递归调用(：

member this.Delay(f) = (fun k -> f () k)

有了这个版本的Delay，你的代码对我来说是按预期工作的。