Как чисто функциональные языки программирования справляются с быстро меняющимися данными?

22

Какие структуры данных вы можете использовать для удаления и замены O (1)? Или как избежать ситуаций, когда вам нужны упомянутые конструкции?

mrpyo
источник
2
Для тех из нас, кто менее знаком с чисто функциональными языками программирования, не могли бы вы рассказать немного больше, чтобы мы поняли, в чем ваша проблема?
FrustratedWithFormsDesigner
4
@FrustratedWithFormsDesigner Чисто функциональные языки программирования требуют, чтобы все переменные были неизменяемыми, что, в свою очередь, требует структур данных, которые создают новые версии самих себя при «изменении».
Доваль
5
Вам знакома работа Окасаки над чисто функциональными структурами данных?
2
Одной из возможностей является определение монады для изменяемых данных (см., Например, haskell.org/ghc/docs/4.08/set/sec-marray.html ). Таким образом, изменяемые данные обрабатываются аналогично IO.
Джорджио
1
@CodesInChaos: однако такие неизменяемые структуры обычно имеют гораздо больше накладных расходов, чем простые массивы. В результате, это очень практичная разница. Вот почему любой чисто функциональный язык, нацеленный на программирование общего назначения, должен иметь способ использовать изменяемые структуры, каким-то безопасным способом, совместимым с чистой семантикой. STМонады в Haskell делает это превосходно.
оставил около

Ответы:

32

Существует огромное количество структур данных, использующих лень и другие приемы для достижения амортизированного постоянного времени или даже (в некоторых ограниченных случаях, таких как очереди ) обновлений постоянного времени для многих видов проблем. Кандидатская диссертация Криса Окасаки «Чисто функциональные структуры данных» и одноименная книга являются ярким примером (возможно, первым основным), но с тех пор эта область продвинулась вперед . Эти структуры данных, как правило, не только чисто функциональны в интерфейсе, но также могут быть реализованы на чистом языке Haskell и аналогичных языках и являются полностью постоянными.

Даже без какого-либо из этих расширенных инструментов простые сбалансированные бинарные деревья поиска обеспечивают обновления в логарифмическом времени, поэтому изменяемая память может быть смоделирована с наихудшим логарифмическим замедлением.

Существуют и другие варианты, которые можно считать мошенничеством, но они очень эффективны в отношении усилий по внедрению и реальной производительности. Например, линейные типы или типы уникальности позволяют обновлять на месте в качестве стратегии реализации концептуально чистого языка, предотвращая сохранение программой предыдущего значения (памяти, которая будет видоизменяться). Это менее общее, чем постоянные структуры данных: например, вы не можете легко создать журнал отмены, сохранив все предыдущие версии состояния. Это все еще мощный инструмент, хотя AFAIK еще не доступен на основных функциональных языках.

Другой вариант безопасного введения изменяемого состояния в функциональную настройку - это STмонада в Haskell. Он может быть реализован без мутаций и, кроме unsafe*функций запрета , ведет себя так, как если бы он был просто модной оболочкой для неявной передачи постоянной структуры данных (ср. State). Но из-за некоторой хитрости системы типов, которая обеспечивает порядок оценки и предотвращает экранирование, ее можно безопасно реализовать с помощью мутации на месте со всеми преимуществами производительности.

Сообщество
источник
Также стоит упомянуть Zippers, дающую вам возможность делать быстрые изменения в фокусе в списке или дереве
jk.
1
@jk. Они упоминаются в посте « Теоретическая информатика», на который я ссылаюсь. Более того, они являются лишь одним (ну, классом) из многих соответствующих структур данных, и обсуждение их всех выходит за рамки и малопригодно.
достаточно справедливо, не следовал по ссылкам
JK.
9

Одна дешевая изменяемая структура - стек аргументов.

Взгляните на типичный факторный расчет в стиле SICP:

(defn fac (n accum) 
    (if (= n 1) 
        accum 
        (fac (- n 1) (* accum n)))

(defn factorial (n) (fac n 1))

Как видите, второй аргумент to facиспользуется как изменяемый аккумулятор для хранения быстро меняющегося продукта n * (n-1) * (n-2) * .... Однако в поле зрения нет изменяемой переменной, и нет способа непреднамеренно изменить аккумулятор, например, из другого потока.

Это, конечно, ограниченный пример.

Вы можете получить неизменяемые связанные списки с дешевой заменой головного узла (и, соответственно, любой части, начинающейся с головки): вы просто указываете новую головку на тот же следующий узел, что и старая головка. Это хорошо работает со многими алгоритмами обработки списков (на foldоснове чего угодно ).

Вы можете получить довольно хорошую производительность от ассоциативных массивов, основанных, например, на HAMT . Логически вы получаете новый ассоциативный массив с измененными парами ключ-значение. Реализация может делиться большей частью общих данных между старыми и вновь созданными объектами. Это не O (1), хотя; обычно вы получаете что-то логарифмическое, по крайней мере, в худшем случае. С другой стороны, неизменяемые деревья обычно не страдают от снижения производительности по сравнению с изменчивыми деревьями. Конечно, это требует некоторых накладных расходов памяти, обычно далеко не запретительных.

Другой подход основан на идее, что если дерево падает в лес и никто его не слышит, ему не нужно издавать звук. То есть, если вы можете доказать, что немного видоизмененного состояния никогда не покидает какую-то локальную область, вы можете безопасно изменять данные в нем.

Clojure имеет переходные процессы, которые являются изменчивыми «тенями» неизменяемых структур данных, которые не просачиваются за пределы локальной области видимости. Clean использует Unique для достижения чего-то похожего (если я правильно помню). Rust помогает делать подобные вещи со статически проверенными уникальными указателями.

9000
источник
1
+1, также за упоминание уникальных типов в Clean.
Джорджио
@ 9000 Мне кажется, я слышал, что в Haskell есть что-то похожее на переходные процессы Clojure - кто-то поправит меня, если я ошибаюсь.
Павел
@paul: Я очень бегло знаю Haskell, поэтому, если бы вы могли предоставить мою информацию (по крайней мере, ключевое слово для Google), я бы с радостью включил ссылку на ответ.
9000
1
@ Пол, я не уверен. Но у Haskell есть метод создания чего-то похожего на ML refи связывания их в определенной области. Смотрите IORefили STRef. И затем, конечно, есть TVars и MVars, которые похожи, но со здравой параллельной семантикой (stm для TVars и мьютекс, основанный для MVars)
Даниэль Гратцер
2

То, что вы спрашиваете, слишком широкое. O (1) удаление и замена из какой позиции? Глава последовательности? Хвост? Произвольная позиция? Используемая структура данных зависит от этих деталей. Тем не менее, 2-3 Finger Trees кажутся одной из самых универсальных постоянных структур данных:

Мы представляем 2-3 пальца, функциональное представление постоянных последовательностей, поддерживающих доступ к концам в амортизированном постоянном времени, и конкатенацию и расщепление во времени, логарифмическое по размеру меньшего куска.

(...)

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

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

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

Doval
источник