List.traverseResultA and friends have x @ y on the error branch, this could potentially blow up

[abelbraaksma]

Describe the bug The List.traverseResultA function and similar ones have this critical path:

            match state, fR with
            | Ok ys, Ok y -> traverseResultA' (Ok(y :: ys)) f xs
            | Error errs, Error e -> traverseResultA' (Error(errs @ e)) f xs
            | Ok _, Error e
            | Error e, Ok _ -> traverseResultA' (Error e) f xs

Namely: Error(errs @ e).

If you have many errors (in my situation is was importing an Excel file and all cells in a column were bad), the performance is exponential.

To solve this, one way would be a simple fix to just e :: errs the errors and do a List.rev at the end.

[TheAngryByrd]

Ouch, yeah that's bad. I mentioned the error path needs to be considered as well in https://github.com/demystifyfp/FsToolkit.ErrorHandling/issues/167 when doing a performance pass at it.

[TheAngryByrd]

I looked into this briefly and errs @ e are two lists so your recommended fix wouldn't work exactly. So I think this would be better changed to be some type of while loop semantics to get performance.

[abelbraaksma]

Oh, yeah, you're right. Though, arguably, the new lists will be shorter than the tally, so a quick rec with e::errs would be nice. But that would, perhaps, invert the order of errors? Hmm, tricky. Yet, such loops are quite common, and with a List.rev at the end, should work.

[TheAngryByrd]

I did benchmark this a bit ago: https://github.com/demystifyfp/FsToolkit.ErrorHandling/issues/167, various tradeoffs

Yeah idk why it's currently implemented with the @ after looking at it now.

[abelbraaksma]

Change looks good, thanks!