В информатике чисто функциональная структура данных — это структура данных , которая может быть непосредственно реализована на чисто функциональном языке . Основное отличие произвольной структуры данных от чисто функциональной состоит в том, что последняя (строго) неизменяема . Это ограничение гарантирует, что структура данных обладает преимуществами неизменяемых объектов: (полная) постоянство , быстрое копирование объектов и потокобезопасность . Эффективные чисто функциональные структуры данных могут потребовать использования ленивых вычислений и мемоизации .
Постоянные структуры данных обладают свойством сохранять предыдущие версии самих себя неизмененными. С другой стороны, непостоянные структуры, такие как массивы, допускают деструктивное обновление [1] , то есть обновление, которое невозможно отменить. Как только программа записывает значение в какой-либо индекс массива, его предыдущее значение больше невозможно получить. [ нужна цитата ]
Формально чисто функциональная структура данных — это структура данных, которая может быть реализована на чисто функциональном языке , таком как Haskell . На практике это означает, что структуры данных должны быть построены с использованием только постоянных структур данных, таких как кортежи, типы сумм , типы продуктов и базовые типы, такие как целые числа, символы и строки. Такая структура данных обязательно является постоянной. Однако не все постоянные структуры данных являются чисто функциональными. [1] : 16 Например, постоянный массив — это постоянная структура данных, которая реализована с использованием массива и, следовательно, не является чисто функциональной. [ нужна цитата ]
В книге « Чисто функциональные структуры данных» Окасаки сравнивает разрушительные обновления с ножами шеф-повара. [1] : 2 Деструктивные обновления невозможно отменить, поэтому их не следует использовать, пока не будет уверенности, что предыдущее значение больше не требуется. Однако деструктивные обновления также могут обеспечить эффективность, которую невозможно получить с помощью других методов. Например, структура данных, использующая массив и деструктивные обновления, может быть заменена аналогичной структурой данных, где массив заменяется картой , списком произвольного доступа или сбалансированным деревом , что допускает чисто функциональную реализацию. Но стоимость доступа может увеличиться с постоянного времени до логарифмического . [ нужна цитата ]
Структура данных никогда не является функциональной по своей сути. Например, стек можно реализовать как односвязный список . Эта реализация является чисто функциональной, пока единственные операции в стеке возвращают новый стек, не изменяя старый стек. Однако, если язык не является чисто функциональным, система времени выполнения может быть не в состоянии гарантировать неизменность. Это иллюстрирует Окасаки, [1] : 9–11 , где он показывает, что объединение двух односвязных списков все еще может быть выполнено с использованием императивной настройки. [ нужна цитата ]
Чтобы гарантировать, что структура данных используется чисто функциональным образом на нечистом функциональном языке, можно использовать модули или классы , обеспечивающие манипулирование только с помощью авторизованных функций. [ нужна цитата ]
Одна из центральных проблем адаптации существующего кода для использования чисто функциональных структур данных заключается в том, что изменяемые структуры данных предоставляют «скрытые выходные данные» для функций, которые их используют. Переписывание этих функций для использования чисто функциональных структур данных требует добавления этих структур данных в качестве явных выходных данных.
Например, рассмотрим функцию, которая принимает изменяемый список, удаляет из списка первый элемент и возвращает этот элемент. В чисто функциональном случае удаление элемента из списка создает новый, более короткий список, но не обновляет исходный. Поэтому, чтобы быть полезной, чисто функциональная версия этой функции, вероятно, должна будет возвращать новый список вместе с удаленным элементом. В самом общем случае преобразованная таким образом программа должна возвращать «состояние» или «хранилище» программы как дополнительный результат каждого вызова функции. Говорят, что такая программа написана в стиле передачи данных .
Вот список абстрактных структур данных с чисто функциональными реализациями:
В своей книге «Чисто функциональные структуры данных» учёный-компьютерщик Крис Окасаки описывает методы, используемые для проектирования и реализации чисто функциональных структур данных, небольшая часть которых кратко изложена ниже.
Ленивое вычисление особенно интересно в чисто функциональном языке [1] : 31, поскольку порядок вычисления никогда не меняет результат функции. Поэтому ленивые вычисления естественным образом становятся важной частью построения чисто функциональных структур данных. Это позволяет выполнять вычисления только тогда, когда их результат действительно необходим. Следовательно, код чисто функциональной структуры данных может без потери эффективности рассматривать одинаково данные, которые будут эффективно использоваться, и данные, которые будут игнорироваться. Единственные необходимые вычисления предназначены для первого типа данных; это то, что на самом деле будет выполнено. [ нужна цитата ]
Одним из ключевых инструментов построения эффективных, чисто функциональных структур данных является мемоизация. [1] : 31 Когда вычисление завершено, оно сохраняется и не требует повторного выполнения. Это особенно важно в ленивых реализациях; дополнительные оценки могут потребовать того же результата, но невозможно знать, какая оценка потребует его в первую очередь. [ нужна цитата ]
Некоторые структуры данных, даже те, которые не являются чисто функциональными, например динамические массивы , допускают операции, которые эффективны большую часть времени (например, постоянное время для динамических массивов) и редко неэффективны (например, линейное время для динамических массивов). Затем амортизацию можно использовать для доказательства эффективности среднего времени выполнения операций. [1] : 39 То есть несколько неэффективных операций достаточно редки и не меняют асимптотическую эволюцию временной сложности при рассмотрении последовательности операций. [ нужна цитата ]
В общем, для персистентных структур данных недопустимо наличие неэффективных операций, поскольку эту самую операцию можно вызывать много раз. Это неприемлемо ни для систем реального времени, ни для императивных систем, где пользователю может потребоваться предсказуемость времени, затрачиваемого на операцию. Более того, эта непредсказуемость усложняет использование параллелизма . [1] : 83 [ нужна ссылка ]
Чтобы избежать этих проблем, некоторые структуры данных позволяют отложить неэффективную операцию — это называется планированием . [1] : 84 Единственное требование состоит в том, чтобы вычисление неэффективной операции закончилось до того, как ее результат действительно понадобится. Постоянная часть неэффективной операции выполняется одновременно с последующим вызовом эффективной операции, так что неэффективная операция уже полностью выполнена, когда она необходима, и каждая отдельная операция остается эффективной. [ нужны разъяснения ]
Амортизированные очереди [1] : 65 [1] : 73 состоят из двух односвязных списков: переднего и перевернутого заднего. Элементы добавляются в задний список и удаляются из переднего списка. Более того, всякий раз, когда передняя очередь пуста, задняя очередь меняется на противоположную и становится передней, а задняя очередь становится пустой. Амортизированная временная сложность каждой операции постоянна. Каждая ячейка списка добавляется, переворачивается и удаляется не более одного раза. Чтобы избежать неэффективной работы, при которой задний список переворачивается, в очереди реального времени добавляется ограничение, заключающееся в том, что длина заднего списка равна длине переднего списка. Чтобы гарантировать, что передний список остается длиннее заднего, задний список переворачивается и добавляется к переднему списку. Поскольку эта операция неэффективна, она не выполняется сразу. Вместо этого оно распределяется по последующим операциям. Таким образом, каждая ячейка вычисляется до того, как она понадобится, а новый передний список полностью вычисляется до того, как потребуется вызвать новую неэффективную операцию. [ нужна цитата ]