В чем преимущество чисто функциональной структуры данных? - PullRequest
55 голосов
/ 09 декабря 2010

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

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

Спасибо.

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

Ответы [ 5 ]

71 голосов
/ 09 декабря 2010

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

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

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

24 голосов
/ 09 декабря 2010

В дополнение к безопасности совместно используемой памяти большинство чисто функциональных структур данных также дают вам постоянство и практически бесплатно.Например, скажем, у меня есть 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:

alt text

14 голосов
/ 09 декабря 2010

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

9 голосов
/ 09 декабря 2010

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

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

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

8 голосов
/ 26 декабря 2010

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

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

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

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

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

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

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

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

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

...