StackOverflow在continuation monad中

Question

使用以下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()

我不明白为什么以下给我一个堆栈溢出:

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)

Answer 1

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

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

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

需要注意的是你的第二个版本提出的递归调用map背后另有let!其desugars到Bind和一个额外的拉姆达,实际上推迟到递归调用map.

在得出这个结论之前,我不得不追求一些虚假的痕迹.除非递归呼叫被延迟,否则观察到的StackOverflow情况OCaml也是如此(尽管处于更高的位置N).虽然F#TCO有一些怪癖,但OCaml更为成熟,所以这使我确信问题确实存在于代码中,而不是编译器:

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)