Почему 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 элементами, так как список должен быть обращен, прежде чем он будет возвращен. Однако я не уверен, стоит ли менять реализацию, так как если ваш парсер чувствителен к производительности и вы анализируете длинную последовательность, вам лучше вообще не использовать списки.

Я, вероятно, должен добавить раздел об использовании массивов вместо списков в главе руководства по производительности.