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

Question

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

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

Спасибо.

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

Answer 1

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

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

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

Answer 2

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

Answer 3

Возьмите этот маленький фрагмент F #:

let numbers = [1; 2; 3; 4; 5] 

с 100% уверенностью можно сказать, что это неизменяемый список целых чисел 1 до 5. Вы можете обойти ссылку на этот список и не должны что список может быть изменен. Этого достаточно для того, чтобы я использовал его.

Answer 4

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

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 остается неизмененной после добавления новых символов (он содержит только объявления) , в то время как b содержит ah, и они делят часть одной и той же памяти (с set, это довольно сложно определить, сколько памяти разделено, поскольку это дерево AVL и форма изменения дерева). Я могу продолжать делать это, отслеживая все изменения, внесенные мной в дерево, позволяя мне вернуться к предыдущему состоянию.

Вот большая диаграмма из Wikipedia article on Purely Functional, который показывает результаты вставить символ «е» в бинарном дереве xs:

Answer 5

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

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

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

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

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

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

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

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

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