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

563

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

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

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

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

jkff
источник
20
Хороший вопрос У меня только что был студент, спрашивающий меня об этом, и я не знал ответа.
Суреш Венкат
Это нормально, но вы можете получить лучшие ответы по переполнению стека. Если вы спросите там, обязательно и ссылку на обсуждение здесь.
Чарльз Стюарт
3
Что ж, Haskell Reddit видел это, так что оттуда тоже будет несколько хороших ответов, но отличный вопрос. Просто находясь на полпути через книгу Окасаки, я сам думал о том же. +1
Роберт Массайоли

Ответы:

553

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

Известный в 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(n)Θ(nlgn)Θ(nlgn)Θ(lg2n)

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

  • O(m)mO(lglgn)

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

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

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

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

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

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

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

jbapple
источник
5
Я не помню, чтобы флажок "сообщества вики" в этом ответе. Есть ли способ отменить это?
jbapple
7
@jbapple: после определенного количества правок все сообщения становятся вики сообщества. Это впечатляюще тщательный обзор. Спасибо.
Фил Миллер
29
Отличный список! Это заставляет меня желать, чтобы Окасаки опубликовал второе издание.
Раду GRIGore
4
Обратите внимание, что Isabelle / HOL может генерировать код для SML, OCaml, Haskell, Scala. Инструмент Haskabelle также может импортировать Haskell в Isabelle / HOL.
Макарий
2
Термин «извлечение программы» является одним из Coq: вы берете конструктивное доказательство и делаете из него исполняемую программу, отбрасывая некоторые вещи. В Изабель это называется «генерацией кода» и работает по-другому, используя спецификации HOL в качестве псевдокода, а не доказательства. Извлечение доказательств в Изабель / HOL, согласно Berghofer, работает как Coq, но редко используется в наши дни.
Макарий
63

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

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

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

Мэтт Мэйт
источник
4
Молнии УДИВИТЕЛЬНЫЕ. Для многих случаев использования они позволяют представлениям на основе дерева стать «правильным» выбором для многих типов данных, в противном случае это было бы немного сложнее
Картер Тацио Шонвальд
1
Пример их использования для манипулирования XML: anti-xml.org/zippers.html
Механическая улитка
40

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

Раду ГРИГОРЕ
источник
Вау, настойчивый СОЮЗ-НАЙТИ! Спасибо!
JKFF
3
Ну, вроде ... Смотрите статью.
Раду GRIGore
1
... или, если хотите, посмотрите код (Мэтт Паркинсон) github.com/septract/jstar/blob/master/src/utils/…
Раду ГРИГОР
5
Теперь я понимаю, почему у комментария "вроде .." было повышение. Они имеют хорошую производительность только тогда, когда один почти исключительно либо не использует постоянство, либо постоянно возвращается назад: если вы часто используете как «новую», так и «старую» версии, вы облажались. Крутая идея перекорения хотя.
jkff
Ссылку Раду теперь можно найти по адресу github.com/septract/jstar-old/blob/…
jbapple
20

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

никто
источник
Я люблю это. Это так здорово, что у производного есть приложение, которое так сильно отличается от определения скорости изменения!
SamB
3
SamB, вам также могут быть интересны производные регулярных выражений (если вы еще не знали о них).
jbapple
14

Rangemaps

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

Сложно увидеть био
источник
7

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

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

Майк Рейни
источник