Движемся обратно вверх

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

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

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

Давайте изменим наши «хлебные крошки», чтобы они содержали информацию обо всём, что мы проигнорировали ранее, когда двигались влево и вправо. Вместо типа Direction создадим новый тип данных:

data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a) deriving (Show)

Теперь вместо кода L у нас есть значение LeftCrumb, содержащее также элемент узла, из которого мы переместились, и не посещённое нами правое поддерево. Вместо кода R есть значение RightCrumb, содержащее элемент узла, из которого мы переместились, и не посещённое нами левое поддерево.

Эти «хлебные крошки» уже содержат все сведения, необходимые для воссоздания дерева, по которому мы прошли. Теперь это не обычные «хлебные крошки» – они больше похожи на дискеты, которые мы оставляем при перемещении, потому что они содержат гораздо больше информации, чем просто направление, по которому мы шли!

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

Давайте также изменим наш синоним типа Breadcrumbs, чтобы отразить это:

type Breadcrumbs a = [Crumb a]

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

goLeft :: (Tree a, Breadcrumbs a) –> (Tree a, Breadcrumbs a)

goLeft (Node x l r, bs) = (l, (LeftCrumb x r):bs)

Как вы можете видеть, она очень похожа на нашу предыдущую функцию goLeft, но вместо того чтобы просто добавлять код L в «голову» нашего списка «хлебных крошек», мы добавляем туда значение LeftCrumb, чтобы показать, что мы пошли влево. Мы также снабжаем наше значение LeftCrumb элементом узла, из которого мы переместились (то есть значением x), и правым поддеревом, которое мы решили не посещать.

Обратите внимание: эта функция предполагает, что текущее дерево, находящееся в фокусе, – не Empty. Пустое дерево не содержит никаких поддеревьев, поэтому если мы попытаемся пойти влево из пустого дерева, возникнет ошибка. Причина в том, что сравнение значения типа Node с образцом будет неуспешным, и нет образца, который заботится о конструкторе Empty.

Функция goRight аналогична:

goRight :: (Tree a, Breadcrumbs a) –> (Tree a, Breadcrumbs a)

goRight (Node x l r, bs) = (r, (RightCrumb x l):bs)

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

goUp :: (Tree a, Breadcrumbs a) –> (Tree a, Breadcrumbs a)

goUp (t, LeftCrumbx r:bs) = (Node x t r, bs)

goUp (t, RightCrumb x l:bs) = (Node x l t, bs)

Мы фокусируемся на дереве t и проверяем последнее значение типа Crumb. Если это значение равно LeftCrumb, мы строим новое дерево, используя наше дерево t в качестве левого поддерева и информацию о правом поддереве и элементе, которые мы не посетили, чтобы заполнить остальные части Node. Поскольку мы «переместились обратно» и подняли последнюю «хлебную крошку», а затем использовали её, чтобы воссоздать родительское дерево, в новом списке эта «хлебная крошка» не содержится.

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

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

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

type Zipper a = (Tree a, Breadcrumbs a)

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