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

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

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

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

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, чтобы сфокусироваться на вершине дерева и увидеть произведённые нами изменения в правильной перспективе.

Застёжки могут использоваться почти с любой структурой данных, поэтому неудивительно, что они работают с подсписками списков. В конце концов, списки очень похожи на деревья, только узел дерева содержит (или не содержит) элемент и несколько поддеревьев, а узел списка – элемент и лишь один подсписок. Когда мы реализовывали свои собственные списки в главе 7, то определили наш тип данных вот так:

data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)

Сравните это с определением нашего бинарного дерева – и легко увидите, что списки можно воспринимать в качестве деревьев, где каждый узел содержит лишь одно поддерево.

Список вроде [1,2,3]может быть записан как 1:2:3:[]. Он состоит из «головы» списка равной 1и «хвоста», который равен 2:3:[]. 2:3:[]также имеет «голову», которая равна 2, и «хвост», который равен 3:[]. Для 3:[]«голова» равна 3, а «хвост» является пустым списком [].

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

А из чего состояла бы отдельная «хлебная крошка» для списка? Когда мы имели дело с бинарными деревьями, нужно было, чтобы «хлебная крошка» хранила элемент, содержащийся в корне родительского узла, вместе со всеми поддеревьями, которые мы не выбрали. Она также должна была запоминать, куда мы пошли, – влево или вправо. Поэтому требовалось, чтобы в ней содержалась вся имеющаяся в узле информация, за исключением поддерева, на которое мы решили навести фокус.

Списки проще, чем деревья. Нам не нужно запоминать, по шли ли мы влево или вправо, потому что вглубь списка можно пойти лишь одним способом. Поскольку для каждого узла существует только одно поддерево, нам также не нужно запоминать пути, по которым мы не пошли. Кажется, всё, что мы должны запоминать, – это предыдущий элемент. Если у нас есть список вроде [3,4,5]и мы знаем, что предыдущим элементом было значение 2, мы можем пойти назад, просто поместив этот элемент в «голову» нашего списка, получая [2,3,4,5].