В чем преимущество чисто функциональной структуры данных?

Question

В чем преимущество чисто функциональной структуры данных?

существует большое количество текстов о структурах данных и библиотеках кода структур данных. Я понимаю, что чисто функциональная структура данных легче рассуждать. Однако мне трудно понять реальное преимущество использования чисто функциональной структуры данных в прагматическом коде (используя функциональный язык программирования или нет) над императивным аналогом. Кто-нибудь может предоставить некоторые реальные случаи, когда чисто функциональная структура данных имеет преимущество и зачем?

примеры вдоль линии, как я использую data_structure_name на programming_language сделать приложение потому что он может сделать certain_thing.

спасибо.

PS: то, что я подразумеваю под чисто функциональной структурой данных, не совпадает с постоянной структурой данных. Постоянная структура данных-это структура данных, которая не меняется?? С другой стороны, чисто функциональная структура данных-это структура данных, работает чисто.

737 5

haskell functional-programming data-structures ocaml purely-functional

5 ответов:

Comments

Ничего не найдено.

ffriend · Accepted Answer · 2010-12-09 18:11:39

чисто функциональные (ака постоянные или неизменяемые) структуры данных дают вам несколько преимуществ:

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

они могут поделиться структурой, которая уменьшает использование памяти. Например, рассмотрим list [1, 2, 3, 4] в Haskell и некоторых императивных языках, таких как Java. Чтобы создать новый список в Haskell вам нужно только создать новый cons (пара значений и ссылка на следующий элемент) и подключить его к предыдущему списку. В Java вы должны создать совершенно новый список, чтобы не повредить предыдущий.

вы можете сделать постоянные структуры данных лень.

кроме того, если вы используете функциональный стиль, вы можете не думать о времени и последовательности операций и так, сделать ваши программы более декларативный.

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

с неизменяемыми данными и функциональным стилем вы также можете свободно использовать memoization.

там гораздо больше преимуществ, в общем, это другой способ моделирование реального мира. этой и некоторые другие главы из SICP дадут вам более точное представление о программировании с неизменяемыми структурами, его преимуществах и недостатках.

Niki Yoshiuchi · Accepted Answer · 2010-12-09 18:18:23

в дополнение к общей памяти безопасности наиболее чисто функции структуры данных также дают вам настойчивость, и практически бесплатно. Например, допустим, у меня есть set в OCaml, и я хочу добавить некоторые новые значения к нему я могу сделать это:
module CharSet = Set.Make(Char)
let a = List.fold_right CharSet.add ['a';'b';'c';'d'] CharSet.empty in
let b = List.fold_right CharSet.add ['e';'f';'g';'h'] a in
...
a остается без изменений после добавления новых символов (он содержит только a-d), в то время как b содержит a-h, и они разделяют некоторые из той же памяти (с set Это довольно сложно скажите, сколько памяти разделяется, так как это дерево AVL и форма дерева изменяется). Я могу продолжать делать это, отслеживая все изменения, которые я внес в дерево, позволяя мне вернуться в предыдущее состояние.

вот отличная диаграмма из статья в Википедии о чисто функциональной это показывает результаты вставки символа ' e ' в двоичное дерево xs:

Marcelo Cantos · Accepted Answer · 2010-12-09 17:30:17

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

ChaosPandion · Accepted Answer · 2010-12-09 17:37:29

возьмите этот маленький фрагмент F#:
let numbers = [1; 2; 3; 4; 5]
вы можете сказать со 100% уверенностью, что это неизменяемый список чисел от 1 до 5. Вы можете передать ссылку на этот список и никогда не беспокоиться о том, что список может быть изменен. Это достаточная причина для меня, чтобы использовать его.

Jon Harrop · Accepted Answer · 2010-12-26 00:45:33

чисто функциональные структуры данных имеют следующие преимущества:

сохраняемость: старые версии могут быть повторно использованы безопасно, зная, что они не могут быть изменены.

совместное использование: многие версии структуры данных могут храниться одновременно с только скромными требованиями к памяти.

потокобезопасность: любая мутация скрыта внутри ленивых Громов (если таковые имеются) и, следовательно, обрабатывается языком реализация.

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

Инкрементальность: чисто функциональные структуры данных состоят из множества крошечных частей, что делает их идеальными для инкрементной сборки мусора, что приводит к снижению задержек.

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

то, что я подразумеваю под чисто функциональной структурой данных, не совпадает с постоянной структурой данных.

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