функциональное программирование: эффективность неизменной структуры данных

Question

Я не понимаю, как компиляторы FP делают код, работающий с неизменяемыми структурами данных, быстрым, не разрушенным стеком и т. Д.

Например, операция вставки в дерево, она должна скопировать все дерево перед добавлением нового узла и вернуть скопированное дерево, в отличие от императивного couterpart, которому нужно только добавить указатель на новый узел. Если операция вставки выполняется миллионы раз, это потребует загрузки памяти, и копирование будет выполняться медленнее и медленнее, когда дерево будет больше. Как компиляторы FP действительно оптимизируют это?

Answer 1

Вам не нужно копировать все дерево, чтобы внести изменения; Вы можете поделиться большей частью структуры. Смотрите, например диаграммы в этом блоге или в этой лекции Рича Хикки о Clojure (см. обсуждение попыток хеширования на полпути).

Answer 2

Компилятор на самом деле не оптимизирует это, это то, что вы должны программировать специально при кодировании. Методы для этого объясняются в превосходных чисто функциональных структурах данных ( книга , диссертация ).

Answer 3

Взгляните на структуру данных Zipper .

Answer 4

Если сборщик мусора выполняет свою работу, старые копии структуры данных будут возвращены, когда они больше не будут использоваться.