延续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的递归调用放在另一个对Bind减半的let!和一个额外的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.

在得出这个结论之前，我不得不走一些错误的道路.有助于观察的是，除非递归调用被延迟，否则StackOverflow也会被OCaml抛出(尽管是更高的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屋！