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

Question

我有代码在等着炸毁潜伏的东西。使用 F# 4.1Result它类似于以下内容：

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

Answer 1

我相信以您建议的方式折叠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"

但是，如果序列太大而无法在内存中实现，则这可能不适用于生产方案。