Какова польза от чисто функциональной структуры данных?

Question

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

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

Спасибо.

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

Answer 1

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

• Вам никогда не придется их блокировать, что чрезвычайно улучшается параллелизм.
• Они могут делиться структурой, которая уменьшает использование памяти. Анкет Например, рассмотрим список [1, 2, 3, 4] в Хаскелле и на некотором императивном языке, таком как Java. Чтобы создать новый список в Хаскелле, вам нужно только создать новый cons (Пара значения и ссылки на связь) и подключите его к предыдущему списку. В Java вы должны создать совершенно новый список, чтобы не повредить предыдущий.
• Вы можете сделать постоянные структуры данных ленивый.
• Кроме того, если вы используете функциональный стиль, вы можете Избегайте думать о времени и последовательности операций, и так, сделай свои программы больше декларативный.
• факт, что структура данных неизменна, позволяет сделать еще несколько предположений и поэтому расширить возможности языка. Анкет Например, Клоджюр Использует тот факт об неизменности, чтобы правильно предоставить реализации метода HashCode () на каждом объекте, поэтому любой объект может использоваться в качестве ключа на карте.
• С неизменными данными и функциональным стилем вы также можете свободно использовать записка.

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

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

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

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

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

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

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

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

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