为什么FParsec使用列表？

Question

我想我应该尝试使用FParsec编写一个快速解析器，很快我就意识到many返回列表是一个严重的性能问题。然后，我发现了一个在文档中使用ResizeArray的替代方法：

let manyA2 p1 p =
    Inline.Many(firstElementParser = p1,
                elementParser = p,
                stateFromFirstElement = (fun x0 ->
                                             let ra = ResizeArray<_>()
                                             ra.Add(x0)
                                             ra),
                foldState = (fun ra x -> ra.Add(x); ra),
                resultFromState = (fun ra -> ra.ToArray()),
                resultForEmptySequence = (fun () -> [||]))

let manyA p = manyA2 p p

相反，在我的代码中使用它可以使其运行速度提高几倍。那么，为什么FParsec默认使用列表而不是ResizeArray？

Answer 1

使用内置的F#列表类型作为序列组合器的结果类型，可以使组合器更方便地在F#中使用，并可能导致更加惯用的客户端代码。由于大多数F#开发人员重视简单和优雅，而不是性能(至少在我的经验中是这样)，所以在我设计API时，使用列表作为默认选项似乎是正确的选择。同时，我试图让用户更容易地定义他们自己的专用序列组合器。

当前，返回列表的序列组合器也使用内部列表来构建序列。对于超过2个元素的序列，这是次优的，因为列表在返回之前必须反转。但是，我不确定更改实现是否值得，因为如果解析器对性能敏感，并且解析长序列，那么最好不要使用列表。

我可能应该在关于性能的用户指南一章中添加一个关于使用数组而不是列表的部分。