Неизменяемая очередь на F#

[mayorovp]

Сложность извлечения в худшем случае равна сложности разворота списка O(N)

Добавлю: но в среднем она составляет O(1). Более того, амортизированное время извлечения записи равно O(1) даже в худшем случае. Это связано с тем, что любой элемент участвует в операции «разворачивания» только один раз, и перед этим участием должен быть вставлен в очередь.

[petuhov_k]

Это я хотел приберечь для следующей статьи.

[spiff]

Я бы хотел заострить внимание читателей на книге Криса Окасаки, про которую вы упомянули в конце. Так вот. Вещь — уникальная. Читается как роман. Если вы хотите разобраться как в функциональном мире работают классические структуры данных — это то, что вам нужно.

Книга является переизданием диссертации Криса, которую он готовил к получению степени Ph.D в 1996 году. Сама же книга была издана двумя годами позже с добавлением первых двух (или трех) глав. Крис, писал в своем блоге, что его жена, каждый раз удивляется, когда они получают чек от продажи книги, говоря при этом: «О, кто-то это еще покупает».

Книга интересна тем, что там впервые мире функционального программирования описаны некоторые техники. Например, Крис первым придумал полностью функциональную реализацию красно-черного дерева, которая теперь используется и в Haskell и в Scala и в других популярных вещах. Или например, там можно найти идеи по конкатенации двух связных списков за O(1), при этом сохраняя персистентность структур.

К слову, я сам читая книгу, пытаюсь реализовать разобранные структуры на Scala. Вот проект на GitHub: github.com/vkostyukov/scalacaster

[ymn]

Добавлю, что готовится перевод книги на русский язык.