为什么FParsec使用列表？

Question

我以为我会尝试使用FParsec编写一个快速解析器,并很快意识到many返回列表是一个严重的性能问题.然后我发现了一个ResizeArray在文档中使用a的替代方法:

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个元素的序列,这是次优的,因为列表必须在返回之前被反转.但是,我不确定更改实现是否值得付出努力,因为如果您的解析器对性能敏感并且您正在解析长序列,那么最好不要使用列表.

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