recursion - 意外递归，用 Seq.append 炸毁堆栈，没有使用 `rec`

我的代码正等着炸毁潜伏着的东西。使用 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/