Почему 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. В то же время я попытался упростить пользователям определение собственных специализированных комбинаторов комбинаций.

В настоящее время комбинаторы последовательности, которые возвращают список, также используют внутренний список для создания последовательности. Это субоптимально для последовательностей с более чем двумя элементами, так как список должен быть отменен до его возврата. Тем не менее, я не уверен, будет ли изменение реализации целесообразным, поскольку, если ваш парсер чувствителен к производительности и вы разбираете длинную последовательность, вам лучше не использовать списки вообще.

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