Вопрос прост: я не могу понять структуру данных Zipper.
Мой вопрос связан с его использованием с деревом.
Я хочу понять, как изменить дерево node с помощью zipper. И как не копировать все дерево (или большую часть его).
Пожалуйста, уточните, не ошибаюсь ли я на молнии. Может быть, это не поможет с обновлением дерева?
Или, может быть, можно обновить дерево, и я просто не вижу пути?
Начнем с Zipper-analog для списков. Если вы хотите изменить n-й элемент списка, он принимает O (n), потому что вам нужно скопировать первые элементы n-1. Вместо этого вы можете сохранить список в виде структуры ((первые n-1 элементы перевернуты) n-ый элемент (остальные элементы)). Например, список (1 2 3 4 5 6), изменяемый в 3, будет представлен как ((2 1) 3 (4 5 6)). Теперь вы можете легко изменить 3 на что-то еще. Вы также можете легко перемещать фокус влево ((1) 2 (3 4 5 6)) и вправо ((3 2 1) 4 (5 6)).
Застежка-молния - та же самая идея, примененная к деревьям. Вы представляете определенный фокус в дереве плюс контекст (вплоть до родителей, вплоть до детей), который дает вам все дерево в форме, где он легко модифицируется в фокусе, и легко перемещать фокус вверх и вниз.
Вот очень хорошая статья, объясняющая использование застежки-молнии для менеджера оконной панели в Haskell. Статья в Википедии не является хорошей ссылкой.
Короче говоря, молния представляет собой указатель или дескриптор определенного node в структуре дерева или списка. Застежка-молния дает естественный способ взять древовидную структуру и рассматривать ее так, как будто дерево было "подобрано" сфокусированным node - по сути, вы получаете второе дерево, не требуя дополнительных копий, сделанных из исходного дерева или затрагивающих другие пользователей дерева.
В приведенном примере показан порядок сортировки окон по местоположению на экране, а затем для моделирования фокуса используется молния, направленная в окно фокусировки. Вы получаете хороший набор операций O (1), таких как вставка и удаление без специального окна с фокусом или записи дополнительного кода.
Узнайте, что у Haskell также есть отличная глава о молниях.
Эта статья связана с Haskell, но также объясняет, что молнии довольно хорошо, и ее легко абстрагироваться от особенностей Haskell.