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

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

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

Спасибо.

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

Ответы

Ответ 1

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

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

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

Ответ 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 it kind сложно определить, сколько памяти разделено, поскольку дерево AVL и форма дерева изменяются). Я могу продолжать это делать, отслеживая все изменения, внесенные мной в дерево, позволяя мне вернуться в предыдущее состояние.

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

alt text

Ответ 3

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

Ответ 4

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

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

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

Ответ 5

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

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

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

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

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

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

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

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

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