Миран Липовача: Изучай Haskell во имя добра!

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

С парой, состоящей из значений типов Treeaи Breadcrumbsa, у нас есть вся необходимая информация для восстановления дерева; кроме того, у нас есть фокус на поддереве. Эта схема позволяет нам легко двигаться вверх, влево и вправо.

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

type Zipper a = (Tree a, Breadcrumbs a)

Я бы предпочёл назвать этот синоним типа Focus, поскольку это наглядно показывает, что мы фокусируемся на части структуры данных. Но так как для описания такой структуры чаще всего используется имя Zipper, будем придерживаться его.

Теперь, когда мы можем перемещаться вверх и вниз, давайте создадим функцию, изменяющую элемент в корне поддерева, на котором фокусируется застёжка.

modify :: (a –> a) –> Zipper a –> Zipper a

modify f (Node x l r, bs) = (Node (f x) l r, bs)

modify f (Empty, bs) = (Empty, bs)

Если мы фокусируемся на узле, мы изменяем его корневой элемент с помощью функции f. Фокусируясь на пустом дереве, мы оставляем его как есть. Теперь мы можем начать с дерева, перейти куда захотим и изменить элемент, одновременно сохраняя фокус на этом элементе, чтобы можно было легко переместиться далее вверх или вниз. Вот пример:

ghci> let newFocus = modify (\_ –> 'P') (goRight (goLeft (freeTree, [])))

Мы идём влево, затем вправо, а потом изменяем корневой элемент, заменяя его на 'P'. Если мы используем оператор –:, это будет читаться ещё лучше:

ghci> let newFocus = (freeTree, []) –: goLeft –: goRight –: modify (\_ –> 'P')

Затем мы можем перейти вверх, если захотим, и заменить имеющийся там элемент таинственным символом 'X':

ghci> let newFocus2 = modify (\_ –> 'X') (goUp newFocus)

Либо можем записать это, используя оператор –:следующим образом:

ghci> let newFocus2 = newFocus –: goUp –: modify (\_ –> 'X')

Перемещаться вверх просто, потому что «хлебные крошки», которые мы оставляем, формируют часть структуры данных, на которой мы не фокусируемся, но она вывернута наизнанку подобно носку. Вот почему когда мы хотим переместиться вверх, нам не нужно начинать с корня и пробираться вниз. Мы просто берём верхушку нашего вывернутого наизнанку дерева, при этом выворачивая обратно его часть и добавляя её в наш фокус.

Каждый узел имеет два поддерева, даже если эти поддеревья пусты. Поэтому, фокусируясь на пустом поддереве, мы по крайней мере можем сделать одну вещь: заменить его непустым поддеревом, таким образом прикрепляя дерево к листу. Код весьма прост:

attach :: Tree a –> Zipper a –> Zipper a

attach t (_, bs) = (t, bs)

Мы берём дерево и застёжку и возвращаем новую застёжку, фокус которой заменён переданным деревом. Можно не только расширять деревья, заменяя пустые поддеревья новыми, но и заменять существующие поддеревья. Давайте прикрепим дерево к дальнему левому краю нашего дерева freeTree:

ghci> let farLeft = (freeTree, []) –: goLeft –: goLeft –: goLeft –: goLeft

ghci> let newFocus = farLeft –: attach (Node 'Z' Empty Empty)

Значение newFocusтеперь сфокусировано на дереве, которое мы только что прикрепили, а остальная часть дерева находится в «хлебных крошках» в вывернутом наизнанку виде. Если бы мы использовали функцию goUpдля прохода всего пути к вершине дерева, оно было бы таким же деревом, как и freeTree, но с дополнительным символом 'Z'на дальнем левом краю.

Создать функцию, которая проходит весь путь к вершине дерева, независимо от того, на чём мы фокусируемся, очень просто. Вот она:

topMost :: Zipper a –> Zipper a

topMost (t, []) = (t, [])

topMost z = topMost (goUp z)

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

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