10

使用以下延续单子：

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

2 回答 2

7

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

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

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

请注意，您的第二个版本将递归调用置于map另一个let!desugarsBind和一个额外的 lambda 之后，实际上延迟了对 的递归调用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)
于 2012-06-25T14:47:57.063 回答
4

F# 编译器有时不是很聪明——在第一种情况下，它先计算map xs然后f x将它们连接起来，所以map xs它不在尾部位置。在第二种情况下，它可以map xs轻松地将其重新排序为尾部位置。

于 2012-06-25T12:18:33.520 回答