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

Question

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

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

Спасибо.

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

Answer 1

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

• вам никогда не придется блокировать их, что чрезвычайно улучшает параллелизм .
• они могут иметь общую структуру, которая уменьшает использование памяти . Например, рассмотрим list [1, 2, 3, 4] на Haskell и некоторые императивные языки, такие как Java. Чтобы создать новый список в Haskell, вам нужно только создать новый cons (пара значений и ссылка на следующий элемент) и подключить его к предыдущему списку. В Java вы должны создать совершенно новый список, чтобы не повредить предыдущий.
• Вы можете создавать постоянные структуры данных Ленивый .
• также, если вы используете функциональный стиль, вы можете избежать мысли о времени и последовательности операций , и, таким образом, сделать ваши программы более декларативными .
• Тот факт, что структура данных является неизменной, позволяет сделать еще несколько предположений и, таким образом, расширяет возможности языка . Например, Clojure использует факт неизменности, чтобы правильно предоставлять реализации метода 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 содержит ах, и они совместно используют часть одной и той же памяти (с set довольно сложно сказать, какой объем памяти используется совместно, так как это дерево AVL иформа дерева меняется).Я могу продолжать делать это, отслеживая все изменения, которые я сделал в дереве, позволяя мне вернуться в предыдущее состояние.

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

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

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

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

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

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

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

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

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