意外递归，使用Seq.append炸毁堆栈，而不使用`rec`

Question

我有正在等待炸毁潜伏的代码。使用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，我使用了一个simple来修复此功能try-catch-reraise，但感觉也很差。关于如何在不强制评估序列或炸毁堆栈的情况下更惯用此方法的任何想法？

不太完美的展开（它也会强制执行result-fail类型），但至少没有对序列进行预先评估：

let unwindSeqWith throwArgument (sourceSeq: #seq<Result<_, 'a -> 'b>>) =
    try 
        sourceSeq
        |> Seq.map (throwOrReturnWith throwArgument)
        |> Ok
    with
    | e -> 
        (fun _ -> raise e)
        |> Error

Answer 1

我相信以Result您建议的方式折叠s 序列的惯用方式是：

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"

但是，如果序列太大而无法在内存中实现，那么这在您的生产方案中可能行不通。