Представление списков в ФП
Jun. 19th, 2010 06:44 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
alexey_romВозник такой вопрос. Как устроены cons-списки, большей части читающих известно :) А мне сейчас пригодилось бы неизменяемое представление списков в неленивом функциональном языке с хвостовой рекурсией, которое хорошо поддерживает две операции:
1) Конкатенацию (и как частный случай добавление элементов в начало и конец списка). Желательно хотя бы амортизированное O(1), O(log N) тоже сойдёт.
2) Итерацию от начала к концу. Без переполнения стека, независимо от того, как строился список.
Вот из-за второго условия простые conc-списки меня не устраивают, нужно какое-то балансирование. И чем проще, тем лучше.
Благодаря наличию хвостовой рекурсии направо деревья могут расти спокойно, главное, чтобы не росли налево.
Известные мне варианты:
1) Vector в Clojure и Scala. Хорошо добавляет элементы в конец, плохо в начало.
2) 2-3 finger tree (например, Data.Sequence в Haskell). Сложная схема балансирования и, как результат, великоваты постоянные множители у асимптотик (хотя жить можно).
UPDATE: Simple Confluently Persistent Catenable Lists и Purely Functional, Real-Time Deques with Catenation.
1) Конкатенацию (и как частный случай добавление элементов в начало и конец списка). Желательно хотя бы амортизированное O(1), O(log N) тоже сойдёт.
2) Итерацию от начала к концу. Без переполнения стека, независимо от того, как строился список.
Вот из-за второго условия простые conc-списки меня не устраивают, нужно какое-то балансирование. И чем проще, тем лучше.
Благодаря наличию хвостовой рекурсии направо деревья могут расти спокойно, главное, чтобы не росли налево.
Известные мне варианты:
1) Vector в Clojure и Scala. Хорошо добавляет элементы в конец, плохо в начало.
2) 2-3 finger tree (например, Data.Sequence в Haskell). Сложная схема балансирования и, как результат, великоваты постоянные множители у асимптотик (хотя жить можно).
UPDATE: Simple Confluently Persistent Catenable Lists и Purely Functional, Real-Time Deques with Catenation.
