 | Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) ( Узнайте, как и когда удалить этот шаблон сообщения )
|
В информатике , чисто функциональная структура данных является структурой данных , которые могут быть реализованы в чисто функциональном языке . Основное отличие произвольной структуры данных от чисто функциональной состоит в том, что последняя (строго) неизменяема . Это ограничение гарантирует, что структура данных обладает преимуществами неизменяемых объектов: (полная) постоянство , быстрое копирование объектов и безопасность потоков . Для эффективных чисто функциональных структур данных может потребоваться ленивая оценка и запоминание .
Определение [ править ]
Постоянные структуры данных обладают свойством сохранять неизменными предыдущие версии самих себя. С другой стороны, такие структуры, как массивы допускают разрушительное обновление , [1] , то есть обновление , которое не может быть отменено. Как только программа записывает значение в некоторый индекс массива, его предыдущее значение больше не может быть получено. [ необходима цитата ]
Формально чисто функциональная структура данных - это структура данных, которая может быть реализована на чисто функциональном языке , таком как Haskell . На практике это означает , что структуры данных должны быть построены с использованием только постоянные структуры данных , такие как кортежи, типы сумм , видов продукции , а также базовые типы , такие как целые числа, символы, строки. Такая структура данных обязательно постоянна. Однако все постоянные структуры данных не являются чисто функциональными. [1] : 16 Например, постоянный массив - это постоянная структура данных, которая реализуется с использованием массива, поэтому не является чисто функциональной. [цитата необходима ]
В книге « Чисто функциональные структуры данных» Окасаки сравнивает разрушительные обновления с ножами шеф-повара. [1] : 2 Деструктивные обновления нельзя отменить, поэтому их нельзя использовать, если нет уверенности в том, что предыдущее значение больше не требуется. Однако деструктивные обновления также могут обеспечить эффективность, которую нельзя получить с помощью других методов. Например, структура данных, использующая массив и деструктивные обновления, может быть заменена аналогичной структурой данных, в которой массив заменяется картой , списком произвольного доступа или сбалансированным деревом , допускающим чисто функциональную реализацию. Но стоимость доступа может увеличиваться с постоянного до логарифмического времени . [цитата необходима ]
Обеспечение чисто функциональной структуры данных [ править ]
Структура данных никогда не бывает функциональной по своей сути. Например, стек может быть реализован как односвязный список . Эта реализация является чисто функциональной, пока единственные операции в стеке возвращают новый стек без изменения старого стека. Однако, если язык не является чисто функциональным, система времени выполнения может быть не в состоянии гарантировать неизменность. Это проиллюстрировано Окасаки [1] : 9-11, где он показывает, что объединение двух односвязных списков все еще может быть выполнено с использованием императивного параметра. [ необходима цитата ]
Чтобы гарантировать, что структура данных используется чисто функциональным образом на нечистом функциональном языке, модули или классы могут использоваться для обеспечения манипуляции только через авторизованные функции. [ необходима цитата ]
Использование чисто функциональных структур данных [ править ]
Одна из основных проблем адаптации существующего кода для использования чисто функциональных структур данных заключается в том, что изменяемые структуры данных обеспечивают «скрытые выходы» для функций, которые их используют. Переписывание этих функций для использования чисто функциональных структур данных требует добавления этих структур данных в качестве явных выходных данных.
Например, рассмотрим функцию, которая принимает изменяемый список, вставляет элемент в список и возвращает длину нового списка. В чисто функциональных условиях вставка нового элемента в список создает новый список, но не обновляет исходный. Следовательно, чтобы быть полезной, чисто функциональная версия этой функции, вероятно, должна будет возвращать как длину списка, так и сам новый список. В наиболее общем случае преобразованная таким образом программа должна возвращать «состояние» или «хранилище» программы в качестве дополнительного результата при каждом вызове функции. Говорят, что такая программа написана в стиле передачи магазина .
Примеры [ править ]
Вот список абстрактных структур данных с чисто функциональными реализациями:
- Стек (первый пришел, последний ушел) реализован как односвязный список ,
- Очередь, реализованная как очередь в реальном времени ,
- Двусторонняя очередь, реализованная как двусторонняя очередь в реальном времени ,
- (Множественный) набор упорядоченных элементов и карт, проиндексированных упорядоченными ключами, реализованный в виде красно-черного дерева или, в более общем смысле, дерева поиска ,
- Приоритетная очередь , реализованная как очередь Brodal
- Список произвольного доступа, реализованный как асимметричный список произвольного доступа
- Хеширование
- Застежка-молния (структура данных)
Дизайн и реализация [ править ]
В своей книге « Чисто функциональные структуры данных» ученый-компьютерщик Крис Окасаки описывает методы, используемые для разработки и реализации чисто функциональных структур данных, небольшое подмножество которых кратко излагается ниже.
Лень и запоминание [ править ]
Ленивое вычисление особенно интересно в чисто функциональном языке [1] : 31, потому что порядок вычисления никогда не изменяет результат функции. Следовательно, ленивое вычисление, естественно, становится важной частью построения чисто функциональных структур данных. Это позволяет производить вычисления только тогда, когда их результат действительно требуется. Следовательно, код чисто функциональной структуры данных может без потери эффективности рассматривать данные, которые будут эффективно использоваться, и данные, которые будут игнорироваться. Единственное необходимое вычисление - это первый вид данных; это то, что на самом деле будет выполнено. [ необходима цитата ]
Мемоизация - один из ключевых инструментов построения эффективных чисто функциональных структур данных. [1] : 31 Когда вычисление выполнено, оно сохраняется, и его не нужно выполнять второй раз. Это особенно важно в ленивых реализациях; дополнительные оценки могут потребовать того же результата, но невозможно знать, какая оценка потребует этого в первую очередь. [ необходима цитата ]
Амортизированный анализ и планирование [ править ]
Некоторые структуры данных, даже те, которые не являются чисто функциональными, такие как динамические массивы , допускают операции, которые эффективны большую часть времени (например, постоянное время для динамических массивов) и редко неэффективны (например, линейное время для динамических массивов). Затем можно использовать амортизацию, чтобы доказать, что среднее время выполнения операций является эффективным. [1] : 39 То есть несколько неэффективных операций достаточно редки и не меняют асимптотическую эволюцию временной сложности, когда рассматривается последовательность операций. [ необходима цитата ]
В общем, наличие неэффективных операций неприемлемо для постоянных структур данных, потому что сама эта операция может вызываться много раз. Это неприемлемо ни для систем реального времени, ни для обязательных систем, где пользователю может потребоваться, чтобы время, затрачиваемое на выполнение операции, было предсказуемым. Кроме того, эта непредсказуемость усложняет использование параллелизма . [1] : 83 [ необходима ссылка ]
Чтобы избежать этих проблем, некоторые структуры данных позволяют отложить неэффективную операцию - это называется планированием . [1] : 84 Единственное требование - вычисление неэффективной операции должно завершаться до того, как ее результат действительно понадобится. Постоянная часть неэффективной операции выполняется одновременно со следующим вызовом эффективной операции, так что неэффективная операция уже полностью выполнена, когда она необходима, и каждая отдельная операция остается эффективной. [ требуется разъяснение ]
Пример: очередь [ править ]
Амортизированные очереди [1] : 65 [1] : 73 состоят из двух односвязных списков: переднего и обратного заднего. Элементы добавляются в задний список и удаляются из переднего списка. Кроме того, когда передняя очередь пуста, задняя очередь переворачивается и становится передней, а задняя очередь становится пустой. Амортизированная временная сложность каждой операции постоянна. Каждая ячейка списка добавляется, переворачивается и удаляется не более одного раза. Чтобы избежать неэффективной операции, когда задний список перевернут, очереди в реальном временидобавить ограничение, что длина заднего списка равна длине переднего списка. Чтобы задний список стал длиннее, чем передний, передний список добавляется к заднему списку и переворачивается. Поскольку эта операция неэффективна, она не выполняется сразу. Вместо этого он распределяется по последующим операциям. Таким образом, каждая ячейка вычисляется до того, как она понадобится, и новый передний список полностью вычисляется до того, как потребуется вызвать новую неэффективную операцию. [ необходима цитата ]
См. Также [ править ]
- Постоянная структура данных
Ссылки [ править ]
- ^ Б с д е е г ч я J K чисто функциональные структуры данных по Крис Окасаки , Cambridge University Press , 1998, ISBN 0-521-66350-4
Внешние ссылки [ править ]
- Тезис Криса Окасаки о чисто функциональных структурах данных (формат PDF)
- Создание устойчивых структур данных Джеймс Р. Дрисколл, Нил Сарнак, Дэниел Д. Слейтор, Роберт Э. Тарджан (PDF)
- Полностью постоянные списки с цепочкой от Джеймса Р. Дрисколла, Дэниела Д. Слейтора, Роберта Э. Тарджана (PDF)
- Постоянные структуры данных из курса MIT OpenCourseWare Advanced Algorithms
- Что нового после Окасаки в чисто функциональных структурах данных? об обмене стеком по теоретической информатике
