Сложные структуры данных в Haskell - как они работают?
Как я понял, переменные в Haskell неизменяемы (таким образом, они не являются "переменными" ).
В этом случае, если у нас есть сложная и большая структура данных, например красно-черное дерево, как мы должны реализовывать операции, которые фактически изменяют структуру данных?
Создайте копию дерева каждый раз, когда элемент вставлен или удален?
Ответы
Ответ 1
Да, решение заключается в возврате новой структуры данных, которая представляет измененное значение, однако нет необходимости копировать всю структуру для вашего примера (красно-черные деревья), поскольку вы можете просто скопировать узлы по пути из корень к вставленному node. Это позволяет операции вставки быть такой же сложной, как и императивная версия.
Chris Okasaki Чисто функциональные структуры данных содержит ряд реализаций неизменных структур данных - эта книга является модифицированной версией его докторской диссертации, которую вы можно найти здесь
Ответ 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
) все еще ссылается на те же самые значения из старой ветки, не требуется копирование!
Поскольку структуры данных неизменны, нет никакого вреда в этом.