连续传递样式计算表达式

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

看起来不错。我可以用List.mapCPS 编写：

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，您的代码可以正常工作。