Сложные структуры данных в Haskell - как они работают?

Question

Как я выяснил, переменные в Haskell неизменны (таким образом, они на самом деле не являются "переменными").

В этом случае, если у нас сложная и большая структура данных, такая как красно-черное дерево, как мы должны реализовывать операции, которые фактически изменяют структуру данных?

Создать копию дерева каждый раз, когда элемент вставляется или удаляется?

Answer 1

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

Крис Окасаки Чисто функциональные структуры данных содержит ряд реализаций неизменяемых структур данных - эта книга является модифицированной версией его кандидатской диссертации, которую вы можете найти здесь

Answer 2

Ваша интуиция о копировании - это именно то направление, о котором вы должны думать. Тем не менее, «копирование» интеллектуально реализовано в среде выполнения Haskell. Например, учитывая

data Tree = Empty | Branch Tree Integer Tree

Вы можете реализовать функцию для замены левой ветви:

replaceLeft :: Tree -> Tree -> Tree
replaceLeft (Branch _ i r) newLeft = Branch newLeft i r

В результате вы не создаете полную копию нового дерева, так как в этом нет необходимости. Значение i и деревья r и newLeft не изменены, поэтому нам не нужно копировать их содержимое в новую память.

Новый Branch, который создается (это единственное реальное распределение в этом примере: создание структуры для хранения левого / правого дерева на Integer) все еще ссылается на те же самые значения из старой ветви Копирование не требуется!

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