Чисто функциональная структура данных

В информатике чисто функциональная структура данных — это структура данных , которая может быть непосредственно реализована на чисто функциональном языке . Основное отличие произвольной структуры данных от чисто функциональной состоит в том, что последняя (строго) неизменяема . Это ограничение гарантирует, что структура данных обладает преимуществами неизменяемых объектов: (полная) постоянство , быстрое копирование объектов и потокобезопасность . Эффективные чисто функциональные структуры данных могут потребовать использования ленивых вычислений и мемоизации .

Определение

Постоянные структуры данных обладают свойством сохранять предыдущие версии самих себя неизмененными. С другой стороны, непостоянные структуры, такие как массивы, допускают деструктивное обновление . ^[1] то есть обновление, которое невозможно отменить. Как только программа записывает значение в какой-либо индекс массива, его предыдущее значение больше невозможно получить. ^{[ нужна ссылка ]}

Формально чисто функциональная структура данных — это структура данных, которая может быть реализована на чисто функциональном языке , таком как Haskell . На практике это означает, что структуры данных должны быть построены с использованием только постоянных структур данных, таких как кортежи, типы сумм , типы продуктов и базовые типы, такие как целые числа, символы и строки. Такая структура данных обязательно является постоянной. Однако не все постоянные структуры данных являются чисто функциональными. ^[1]^: 16 Например, постоянный массив — это постоянная структура данных, которая реализована с использованием массива и, следовательно, не является чисто функциональной. ^{[ нужна ссылка ]}

В книге «Чисто функциональные структуры данных » Окасаки сравнивает разрушительные обновления с ножами шеф-повара. ^[1]^: 2 Деструктивные обновления невозможно отменить, и поэтому их не следует использовать, если нет уверенности, что предыдущее значение больше не требуется. Однако деструктивные обновления также могут обеспечить эффективность, которую невозможно получить с помощью других методов. Например, структура данных, использующая массив и деструктивные обновления, может быть заменена аналогичной структурой данных, где массив заменяется картой , списком произвольного доступа или сбалансированным деревом , что допускает чисто функциональную реализацию. Но стоимость доступа может увеличиться с постоянного времени до логарифмического . ^{[ нужна ссылка ]}

Обеспечение чисто функциональной структуры данных.

Структура данных никогда не является функциональной по своей сути. Например, стек можно реализовать как односвязный список . Эта реализация является чисто функциональной, пока единственные операции в стеке возвращают новый стек, не изменяя старый стек. Однако, если язык не является чисто функциональным, система времени выполнения может быть не в состоянии гарантировать неизменность. Это иллюстрирует Окасаки. ^[1]^: 9–11 где он показывает, что объединение двух односвязных списков все еще может быть выполнено с использованием императивной настройки. ^{[ нужна ссылка ]}

Чтобы гарантировать, что структура данных используется чисто функциональным образом на нечистом функциональном языке, можно использовать модули или классы , обеспечивающие манипулирование только с помощью авторизованных функций. ^{[ нужна ссылка ]}

Использование чисто функциональных структур данных

Одна из центральных проблем адаптации существующего кода для использования чисто функциональных структур данных заключается в том, что изменяемые данныеструктуры предоставляют «скрытые выходные данные» для функций, которые их используют. Переписывание этих функций для использования чисто функциональных структур данных.требует добавления этих структур данных в качестве явных выходных данных.

Например, рассмотрим функцию, которая принимает изменяемый список, удаляет из списка первый элемент и возвращает этот элемент. В чисто функциональном случае удаление элемента из списка создает новый, более короткий список, но не обновляет исходный. Поэтому, чтобы быть полезной, чисто функциональная версия этой функции, вероятно, должна будет возвращать новый список вместе с удаленным элементом. В самом общем случае преобразованная таким образом программа должна возвращать «состояние» или «хранилище» программы как дополнительный результат каждого вызова функции. Говорят, что такая программа написана в стиле передачи данных .

Примеры

Вот список абстрактных структур данных с чисто функциональной реализацией:

Стек (первый вошел, последний вышел) реализован в виде односвязного списка ,
Очередь, реализованная как очередь реального времени ,
Двусторонняя очередь, реализованная как двусторонняя очередь в реальном времени ,
(Мульти)множество упорядоченных элементов и карта , индексированная упорядоченными ключами, реализованная в виде красно-черного дерева или, в более общем смысле, дерева поиска ,
Приоритетная очередь , реализованная как очередь Бродала
Список произвольного доступа, реализованный как косо-двоичный список произвольного доступа.
Хеширование
Молния (структура данных)

Проектирование и реализация

В своей книге «Чисто функциональные структуры данных » учёный-компьютерщик Крис Окасаки описывает методы, используемые для проектирования и реализации чисто функциональных структур данных, небольшая часть которых кратко изложена ниже.

Лень и мемоизация

Ленивые вычисления особенно интересны на чисто функциональном языке. ^[1]^: 31 потому что порядок вычисления никогда не меняет результат функции. Поэтому ленивые вычисления естественным образом становятся важной частью построения чисто функциональных структур данных. Это позволяет выполнять вычисления только тогда, когда их результат действительно необходим. Следовательно, код чисто функциональной структуры данных может без потери эффективности рассматривать одинаково данные, которые будут эффективно использоваться, и данные, которые будут игнорироваться. Единственные необходимые вычисления предназначены для первого типа данных; это то, что на самом деле будет выполнено. ^{[ нужна ссылка ]}

Одним из ключевых инструментов построения эффективных, чисто функциональных структур данных является мемоизация. ^[1]^: 31 Когда вычисление выполнено, оно сохраняется и не требует повторного выполнения. Это особенно важно в ленивых реализациях; дополнительные оценки могут потребовать того же результата, но невозможно узнать, какая оценка потребует его в первую очередь. ^{[ нужна ссылка ]}

Амортизированный анализ и планирование

Некоторые структуры данных, даже те, которые не являются чисто функциональными, например динамические массивы , допускают операции, которые эффективны большую часть времени (например, постоянное время для динамических массивов) и редко неэффективны (например, линейное время для динамических массивов). Затем амортизацию можно использовать для доказательства эффективности среднего времени выполнения операций. ^[1]^: 39 Другими словами, несколько неэффективных операций достаточно редки и не меняют асимптотическую эволюцию временной сложности при рассмотрении последовательности операций. ^{[ нужна ссылка ]}

В общем, для персистентных структур данных недопустимо наличие неэффективных операций, поскольку эту самую операцию можно вызывать много раз. Это неприемлемо ни для систем реального времени, ни для императивных систем, где пользователю может потребоваться предсказуемость времени, затрачиваемого на операцию. Более того, эта непредсказуемость усложняет использование параллелизма . ^[1]^: 83^{[ нужна ссылка ]}

Чтобы избежать этих проблем, некоторые структуры данных позволяют отложить неэффективную операцию — это называется планированием . ^[1]^: 84 Единственное требование состоит в том, что вычисление неэффективной операции должно завершиться до того, как ее результат действительно понадобится. Постоянная часть неэффективной операции выполняется одновременно с последующим вызовом эффективной операции, так что неэффективная операция уже полностью выполнена, когда она необходима, и каждая отдельная операция остается эффективной. ^{[ нужны разъяснения ]}

Пример: очередь

Амортизированные очереди ^[1]^: 65^[1]^: 73 состоят из двух односвязных списков: переднего и перевернутого заднего. Элементы добавляются в задний список и удаляются из переднего списка. Более того, всякий раз, когда передняя очередь пуста, задняя очередь меняется на противоположную и становится передней, а задняя очередь становится пустой. Амортизированная временная сложность каждой операции постоянна. Каждая ячейка списка добавляется, переворачивается и удаляется не более одного раза. Чтобы избежать неэффективной работы, при которой задний список переворачивается, очереди реального времени добавляют ограничение, согласно которому длина заднего списка равна длине переднего списка. Чтобы гарантировать, что передний список остается длиннее заднего, задний список переворачивается и добавляется к переднему списку. Поскольку эта операция неэффективна, она не выполняется сразу. Вместо этого он распределяется по последующим операциям. Таким образом, каждая ячейка вычисляется до того, как она понадобится, а новый передний список полностью вычисляется до того, как потребуется вызвать новую неэффективную операцию. ^{[ нужна ссылка ]}

См. также

Постоянная структура данных

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Чисто функциональные структуры данных Криса Окасаки , Cambridge University Press , 1998, ISBN 0-521-66350-4

Внешние ссылки

Чисто функциональные структуры данных» (формат PDF) Диссертация Криса Окасаки «
Обеспечение устойчивости структур данных Джеймс Р. Дрисколл, Нил Сарнак, Дэниел Д. Слитор, Роберт Э. Тарджан (PDF)
Полностью постоянные списки с катенацией Джеймса Р. Дрисколла, Дэниела Д. Слиатора, Роберта Э. Тарджана (PDF)
Постоянные структуры данных из MIT OpenCourseWare курса «Продвинутые алгоритмы»
Что нового в чисто функциональных структурах данных со времен Окасаки? по теоретической информатики обмену стеками

[Okasaki-book-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Чисто функциональные структуры данных Криса Окасаки , Cambridge University Press , 1998, ISBN 0-521-66350-4

[1]