recursion - 意外递归,使用 Seq.append 炸毁堆栈,未使用 `rec`

标签 recursion f# stack-overflow

我有代码正在等待炸毁潜伏的东西。使用 F# 4.1 Result它类似于:

module Result =
    let unwindSeq (sourceSeq: #seq<Result<_, _>>) =
        sourceSeq
        |> Seq.fold (fun state res -> 
            match state with
            | Error e -> Error e
            | Ok innerResult ->
                match res with
                | Ok suc -> 
                    Seq.singleton suc
                    |> Seq.append innerResult
                    |> Ok
                | Error e -> Error e) (Ok Seq.empty)

这里明显的瓶颈是Seq.singleton添加到 Seq.append .我知道这很慢(而且写得不好),但为什么它必须炸毁堆栈? 我不认为 Seq.append本质上是递归的...
// blows up stack, StackOverflowException
Seq.init 1000000 Result.Ok
|> Result.unwindSeq
|> printfn "%A" 

顺便说一句,展开 Result 的序列, 我用一个简单的 try-catch-reraise 修复了这个函数,但感觉也低于标准。关于如何在不强制评估序列或炸毁堆栈的情况下更惯用地执行此操作的任何想法?

不太完美的展开(它也强制结果失败类型),但至少没有对序列进行预评估:
let unwindSeqWith throwArgument (sourceSeq: #seq<Result<_, 'a -> 'b>>) =
    try 
        sourceSeq
        |> Seq.map (throwOrReturnWith throwArgument)
        |> Ok
    with
    | e -> 
        (fun _ -> raise e)
        |> Error

最佳答案

我相信折叠 Result 序列的惯用方式你建议的方式是:

let unwindSeq<'a,'b> =
    Seq.fold<Result<'a,'b>, Result<'a seq, 'b>> 
        (fun acc cur -> acc |> Result.bind (fun a -> cur |> Result.bind (Seq.singleton >> Seq.append a >> Ok))) 
        (Ok Seq.empty)

并不是说这会比您当前的实现更快,它只是利用 Result.bind完成大部分工作。我相信堆栈溢出是因为 F# 库中某处的递归函数,可能在 Seq 中。模块。我对此的最好证据是将序列具体化为 List首先似乎使它起作用,如下例所示:
let results = 
    Seq.init 2000000 (fun i -> if i <= 1000000 then Result.Ok i else Error "too big") 
    |> Seq.toList

results
|> unwindSeq
|> printfn "%A"

但是,如果序列太大而无法在内存中实现,这可能不适用于您的生产场景。

关于recursion - 意外递归,使用 Seq.append 炸毁堆栈,未使用 `rec`,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50748589/

相关文章:

c - 在递归函数中修改二维数组,C

f# - Elmish.WPF类型冲突: unit -> Model expected where Model provided?

c# - F# 内联如何工作?

jsf-2 - JSF : how prevent stackoverflow due to recursion during build phase (despite rendered test)

Java-在递归类中返回字符串的问题

ruby - 如何从 Ruby 中的阶乘方法中排除 float ?

c++ - 没有for或while的构造函数中的无限循环

c# - 你能在 F# 中改进这个 'lines of code algorithm' 吗?

c++ - 为什么这不会在 WSL 中的 Ubuntu 上触发堆栈溢出?

java - 如何测量Java中的堆栈内存?