延续 monad 中的 StackOverflow [英] StackOverflow in continuation monad

问题描述

使用以下延续单子:

type ContinuationMonad() =
    member this.Bind (m, f) = fun c -> m (fun a -> f a c)
    member this.Return x = fun k -> k x

let cont = ContinuationMonad()

我不明白为什么以下内容会导致堆栈溢出:

I fail to see why the following gives me a stack overflow:

let map f xs =
    let rec map xs =
        cont {
            match xs with
            | [] -> return []
            | x :: xs ->
                let! xs = map xs
                return f x :: xs
        }
    map xs id;;

let q = [1..100000] |> map ((+) 1)

虽然以下没有:

let map f xs =
    let rec map xs =
        cont {
            match xs with
            | [] -> return []
            | x :: xs ->
                let! v = fun g -> g(f x)
                let! xs = map xs
                return v :: xs
        }
    map xs id;;

let q = [1..100000] |> map ((+) 1)

推荐答案

要修复您的示例，请将此方法添加到您的 monad 定义中:

To fix your example, add this method to your definition of the monad:

member this.Delay(mk) = fun c -> mk () c

显然溢出的部分是map递归调用中大输入列表的破坏.延迟它可以解决问题.

Apparently the part that overflows is the destruction of the large input list in the recursive call of map. Delaying it solves the problem.

请注意，您的第二个版本将对 map 的递归调用放在另一个 let! 后面，后者实际上对 Bind 和额外的 lambda 进行了脱糖延迟对 map 的递归调用.

Note that your second version puts the recursive call to map behind another let! which desugars to Bind and an extra lambda, in effect delaying the recursive call to map.

在得出这个结论之前，我不得不寻找一些错误的线索.观察到 OCaml 也抛出 StackOverflow 有帮助(尽管在更高的 N 处)，除非递归调用被延迟.虽然 F# TCO 有一些怪癖，但 OCaml 得到了更多证明，所以这让我确信问题确实出在代码上，而不是编译器:

I had to pursue a few false trails before reaching this conclusion. What helped was observing that StackOverflow is thrown by OCaml as well (albeit at a higher N) unless the recursive call is delayed. While F# TCO has some quirks, OCaml is more proven, so this convinced me that the problem is indeed with the code and not the compiler:

let cReturn x = fun k -> k x
let cBind m f = fun c -> m (fun a -> f a c)

let map f xs =
  (* inner map loop overflows trying to pattern-match long lists *)
  let rec map xs =
    match xs with
      | [] -> cReturn []
      | x :: xs ->
        cBind (map xs) (fun xs -> cReturn (f x :: xs)) in
  map xs (fun x -> x)

let map_fixed f xs =
  (* works without overflowing by delaying the recursive call *)
  let rec map xs =
    match xs with
      | [] -> cReturn []
      | x :: xs ->
        cBind (fun c -> map xs c) (fun xs -> cReturn (f x :: xs)) in
  map xs (fun x -> x)

let map_fused f xs =
  (* manually fused version avoids the problem by tail-calling `map` *)
  let rec map xs k =
    match xs with
      | [] -> k []
      | x :: xs ->
        map xs (fun xs -> k (f x :: xs)) in
  map xs (fun x -> x)

这篇关于延续 monad 中的 StackOverflow的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！