使用以下延续单子:
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)
要修复您的示例,请将此方法添加到 monad 的定义中:
member this.Delay(mk) = fun c -> mk () c
显然,溢出的部分是递归调用中对大输入列表的破坏map
。拖延一下就能解决问题。
请注意,您的第二个版本将递归调用map
在另一个后面let!
脱糖到Bind
和一个额外的 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)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)