Что нового в чисто функциональных структурах данных со времен Окасаки?

Со времени выхода книги Криса Окасаки «Чисто функциональные структуры данных» 1998 года я не видел слишком много новых интересных чисто функциональных структур данных; Я могу назвать только несколько:

• IntMap (также изобретен Окасаки в 1998 году, но не представлен в этой книге)
• Пальцевые деревья (и их обобщение над моноидами)

Есть также несколько интересных способов реализации уже известных структур данных, таких как использование «вложенных типов» или «обобщенных алгебраических типов данных» для обеспечения древовидных инвариантов.

Какие еще новые идеи появились с 1998 года в этой области?

Новые чисто функциональные структуры данных, опубликованные с 1998 года:

• 2001: Ideal Hash Trees и его предшественник 2000 года, Fast And Space Efficient Trie Searches , Фил Бэгвелл : Очевидно, используется в качестве фундаментального строительного блока в стандартной библиотеке Clojure.

• 2001: Простая техника реализации для очередей приоритетного поиска , Ральфа Хинце : действительно простая и красивая техника для реализации этой важной структуры данных (полезная, скажем, в алгоритме Дейкстры). Реализация особенно красива и удобочитаема из-за интенсивного использования «шаблонов просмотра».

• 2002: Bootstrapping односторонних гибких массивов , Ralf Hinze : Похож на списки произвольного доступа Okasaki, но они могут быть настроены для изменения компромисса времени consи индексации.

• 2003: новые заказываемые и непатентованные запросы , выполненные Раду Михеску и Робертом Тарьяном : новый взгляд на некоторые более старые работы (Каплан и Тарьян), которые цитирует Окасаки ( самая последняя версия работы Каплана и Тарьяна была опубликована в 2000 году ). Эта версия проще в некоторых отношениях.

• 2005: Maxiphobic heap ( paper and code ), Chris Okasaki : Представлено не как новая, более эффективная структура, а как способ обучения приоритетным очередям.

• 2006: Чисто функциональный в худшем случае отсортированные списки , которые можно катить по времени , Герт Стелтинг Бродал, Кристос Макрис и Костас Цихлас : отвечает на выдающийся вопрос Каплана и Тарьяна, демонстрируя структуру с O (lg n) вставками, поиском, удалением и O (1) Конкат.

• 2008: Элли Д. Демейн, Стефан Лангерман и Эрик Прайс : Конфликтующие настойчивые попытки эффективного управления версиями . Представляет несколько структур данных для попыток, которые имеют эффективную навигацию и модификации вблизи листьев. Некоторые из них являются чисто функциональными. Другие действительно улучшают многолетнюю структуру данных Dietz et al. для полностью постоянных (но не постоянных или чисто функциональных) массивов. В этой статье также представлены чисто функциональные деревья с вырезанными ссылками , которые иногда называют «динамическими деревьями».

• 2010: новый чисто функциональный алгоритм удаления красно-черных деревьев , автор Matt Might : подобно алгоритму вставки красно-черного дерева Окасаки, это не новая структура данных или новая операция над структурой данных, а новый, более простой способ написать известную операцию.

• 2012: RRB-Trees: эффективные неизменяемые векторы , Фил Бэгвелл и Тиарк Ромпф : расширение для попыток с отображением в массиве хэшей , поддерживающих конкатенацию неизменных векторов, вставку в at и разбиение за время O (lg n) при сохранении индекса, обновление и скорости вставки исходного неизменяемого вектора.

Известный в 1997 году, но не обсуждаемый в книге Окасаки:

• Многие другие стили сбалансированного дерева поиска . AVL, брат, ранжированный баланс, ограниченный баланс и многие другие сбалансированные деревья поиска могут быть (и были) реализованы чисто функционально путем копирования пути. Возможно, заслуживают особого упоминания:

  • Деревья предвзятого поиска , Сэмюэл У. Бент, Дэниел Д. Слеатор и Роберт Э. Тарджан : ключевой элемент в статье Бродала и др. 2006 года и в работе Демейна и др. 2008 года.

• Бесконечные множества, допускающие быстрый исчерпывающий поиск , Мартин Эскардо : Возможно, не структура данных как таковая .

• Крис Окасаки (Chris Okasaki) : три алгоритма на деревьях Брауна. Деревья Брауна предлагают множество операций со стеком в худшем случае O (lg n) Эта граница превосходит многие другие структуры данных, но деревья Брауна имеютconsленивую операцию во втором аргументе и поэтому могут использоваться в качестве бесконечных стеков в некоторых отношениях, что другие структуры не могут.

• Расслабленная min-max куча: объединяемая очередь с двусторонним приоритетом и куча KD: эффективная многомерная очередь приоритетов. Автор - Yuzheng Ding и Mark Allen Weiss : они оказываются чисто функциональными, хотя это не обсуждается в статьях. , Я не думаю, что достигнутые временные границы лучше, чем те, которые могут быть достигнуты при использовании деревьев пальцев (Хинце и Патерсона или Каплана и Тарьяна) в качестве очередей с приоритетом k-измерения, но я думаю, что структуры Ding & Weiss используют меньше места ,

• The Zipper , Жерар Юе : Используемый во многих других структурах данных (таких как деревья пальцев Хинце и Патерсона), это способ вывернуть структуру данных наизнанку.

• Списки различий - это O (1) списки, которые можно переписать, с O (n) преобразованием в обычные consсписки. По-видимому, они были известны с древности в сообществе Прологов, где они преобразовали O (1) в обычные consсписки. Преобразование O (1) кажется невозможным в традиционном функциональном программировании, но абстракция дыры Minamide из POPL '98 обсуждает способ разрешения добавления O (1) и преобразования O (1) в чисто функциональном программировании. В отличие от обычных реализаций функционального программирования списков различий, которые основаны на замыканиях функций, абстракции дырок по существу такие же (как в их использовании, так и в их реализации), что и списки различий Prolog. Однако, кажется, что в течение многих лет единственным человеком, который заметил это, былодин из рецензентов Минамиды .

• $O(\sqrt{n})$$\Theta(n \lg n)$$\Theta(\sqrt{n \lg n})$$\Theta(\lg^2 n)$

В основном функциональные структуры данных до, во время и после книги Окасаки:

• $O(m)$$m$$O(\lg \lg n)$

• 1989: рандомизированные деревья поиска Сесилия Р. Арагон и Раймунд Зейдель : они обсуждались в чисто функциональной обстановке Гаем Э. Блеллохом и Маргарет Рейд-Миллер в операциях быстрого набора с использованием Treaps, а также Дэном Блэндфордом и Гаем Блеллохом в операциях функционального набора с Treaps ( код). Они обеспечивают все операции чисто функциональных деревьев и смещенных деревьев поиска, но требуют источника случайности, что делает их не чисто функциональными. Это также может сделать недействительной временную сложность операций с трепами, предполагая, что злоумышленник может синхронизировать операции и повторять длинные. (Это та же самая причина, по которой аргументы обязательной амортизации недопустимы в постоянных настройках, но для этого требуется злоумышленник с секундомером)

• 1997: деревья пропусков, альтернативная структура данных для списков пропусков в параллельном подходе , автор Xavier Messeguer и исследование двойственности между списками пропусков и деревьями двоичного поиска , Брайан К. Дин и Захари Х. Джонс : списки пропусков не являются чисто функционально, но они могут быть функционально реализованы в виде деревьев. Как и трепы, они требуют источника случайных битов. (Можно сделать списки пропусков детерминированными, но после перевода их в дерево я думаю, что это просто еще один способ просмотра 2-3 деревьев.)

• 1998: все амортизированные структуры в книге Окасаки! Окасаки изобрел этот новый метод смешивания амортизации и функциональных структур данных, которые ранее считались несовместимыми. Это зависит от запоминания, которое, как иногда упоминали Каплан и Тарьян, на самом деле является побочным эффектом. В некоторых случаях ( например, PFDS на SSD по соображениям производительности ) это может быть неуместно.

• 1998: Простые Confluently Стойкие Catenable Списки , Хаим Каплан, Крис Окасаки и Роберт Э. Tarjan : Использует модификации под капотом , чтобы дать амортизируется O (1) catenable двусторонних очередей, представляя тот же интерфейс , как ранее (чисто функциональной, но с запоминанием ) версия, появляющаяся в книге Окасаки. Каплан и Тарьян ранее создали чисто функциональную O (1) структуру в худшем случае, но она значительно сложнее.

• 2007: Как уже упоминалось в другом ответе на этой странице, полустойкие структуры данных и постоянный поиск объединений Сильвен Кончон и Жан-Кристоф Филлиатр

Методы проверки функциональных структур данных до, во время и после книги Окасаки:

• Фантомные типы - это старый метод создания API, который не допускает определенных некорректных операций. Сложное их использование можно найти в « Облегченных статических возможностях» Олега Киселева и Чанг-Цзе Шаня .

• Вложенные типы на самом деле не более поздние, чем 1998 год - Окасаки даже использует их в своей книге. Есть много других примеров, которых нет в книге Окасаки; некоторые новые, а некоторые старые. Они включают:

  • Красно-черные деревья Штефана Карса с видами ( код )
  • AVL деревья Росса Патерсона ( зеркало )
  • Крис Окасаки От быстрого возведения в степень до квадратных матриц: приключение в типах
  • Обозначение де Брюйна Ричарда С. Берда и Росса Петерсона как вложенный тип данных
  • Числовые представления Ральфа Хинце как вложенные типы данных высшего порядка .

• ГАДЦ тоже не так уж новы. Они являются недавним дополнением к Haskell и некоторым ML, но, как мне кажется, они присутствуют в различных типизированных лямбда-исчислениях с 1970-х годов .

• 2004-2010: Кок и Изабель за правильность . Несколько человек использовали теоремы для проверки правильности чисто функциональных структур данных. Coq может извлечь эти проверки из рабочего кода в Haskell, OCaml и Scheme; Изабель может извлечь в Haskell, ML и OCaml.

  • Coq:
    • Пьер Летузи и Жан-Кристоф Филлиатр формализовали красно-чёрные и AVL (ish) деревья, обнаружив при этом ошибку в стандартной библиотеке OCaml .
    • Я формализовал асимптотически оптимальные очереди приоритетов Бродала и Окасаки .
    • Артур Шерго формализовал 825 из 1700 строк ОД в книге Окасаки .
  • Isabelle:
    • Тобиас Нипков и Корнелия Пуш формализовали деревья AVL .
    • Виктор Кунчак формализовал несбалансированные бинарные деревья поиска .
    • Питер Ламмич опубликовал платформу Isabelle Collections , которая включает в себя формализации эффективных чисто функциональных структур данных, таких как красно-черные деревья и попытки, а также структуры данных, которые менее эффективны при постоянном использовании, такие как очереди с двумя стеками (без уловки лени Окасаки ) и хеш-таблицы.
    • Питер Ламмич также опубликовал формализации древовидных автоматов , пальчиковых деревьев Хинце и Паттерсона (с Бенедиктом Нордхоффом и Стефаном Кёрнером), а также чисто функциональные очереди приоритетов Бродала и Окасаки (с Рене Мейс и Финном Нильсеном).
    • Рене Нейман формализовал биномиальные очереди с приоритетами .

• 2007: Уточненная проверка типов с помощью Stardust , Джошуа Данфилд : Эта статья использует типы уточнения для ML, чтобы найти ошибки в функции удаления красно-черного дерева SMLNJ.

• 2008: Легкий полуформальный анализ сложности времени для чисто функциональных структур данных. Автор Nils Anders Danielsson : использует Agda с ручной аннотацией, чтобы доказать временные ограничения для некоторых PFDS.

Обязательные структуры данных или анализы, не обсуждаемые в книге Окасаки, но связанные с чисто функциональными структурами данных:

• Мягкая куча: очередь с приблизительным приоритетом с оптимальным коэффициентом ошибок , Бернард Шазель : эта структура данных не использует массивы, поэтому соблазнил сначала IRC-канал #haskell, а затем пользователей переполнения стека , но он включаетdeleteвсебяo (lg n) , что, как правило, невозможно в функциональной обстановке, и императивный амортизированный анализ, который недопустим в чисто функциональной обстановке.

• Сбалансированные двоичные деревья поиска с O (1) обновлениями пальцев . В статье «Обеспечение постоянства структур данных» Джеймс Р. Дрисколл, Нил Сарнак, Дэниел Д. Слеатор и Роберт Э. Тарджан представляют метод группировки узлов в красно-черном дереве, так что для постоянных обновлений требуется только пространство O (1). Чисто функциональные запросы и деревья пальцев, разработанные Тарьяном, Капланом и Михаеску, используют очень похожую технику группировки, чтобы позволить обновления O (1) на обоих концах. AVL-деревья для локализованного поиска Athanasios K. Tsakalidis работает аналогично.

• Более быстрые кучи спаривания или лучшие границы для спаривания кучи : Со времени публикации книги Окасаки появилось несколько новых анализов кучи обязательного спаривания, в том числе связывание кучи с O (log log n) уменьшением стоимости на Amr Elmasry и на пути к окончательному анализу спаривания куч к Сет Петти. Может быть возможно применить некоторые из этой работы к лентам ленивого соединения Окасаки.

• Детерминированные предвзятые палец деревья : В предвзято Пропустить списки , по Амитабхи Bagchi, Адам Л. Бухсбаумом, и Майкл Т. Гудрич, дизайн представлен для детерминированных смещенных списков пропуска. Посредством упомянутого выше преобразования списка пропуска / дерева можно создать детерминированные смещенные деревья поиска. В случае необъективных деревьев пропусков могут быть возможны списки пропущенных смещением пальцев, описанные Джоном Яконо и Озгюром Озканом в Mergeable Dictionaries . Demaine et al. Предлагает смещенное дерево пальцев. в их статье о чисто функциональных попытках (см. выше) как способ уменьшить временные и пространственные границы при обновлении пальцев в попытках.

• Струнное B-дерево: новая структура данных для поиска строк во внешней памяти и ее приложениях, разработанная Паоло Феррагиной и Роберто Гросси, представляет собой хорошо изученную структуру данных, сочетающую в себе преимущества попыток и B-деревьев.

К уже сделанным превосходным заметкам я добавлю молнии .

Хуэт, Джерард. «Функциональная жемчужина: молния» Журнал функционального программирования 7 (5): 549-554, сентябрь 1997 г.

Википедия: Молния (структура данных)

Кончон, Филлиатр, Постоянная структура данных UNION-FIND и Полупостоянные структуры данных .

Я бы добавил версию застежек-молний McBride в качестве производных типов данных.

Rangemaps

Это специализированная структура данных, но она может использоваться в качестве замены DIET Мартина Эрвига с немного отличающимися свойствами, поэтому, по крайней мере, существует одна существующая структура данных, с которой можно сравнивать. Сам DIET был описан в статье в JFP в 1998 году, поэтому, возможно, он не включен в чисто функциональные структуры данных.

Вслед за документом 2012 года, связанным выше, работа над векторами RRB была расширена и опубликована в ICFP'15.

Вектор RRB: практическая неизменяемая последовательность общего назначения http://dl.acm.org/citation.cfm?id=2784739