Изучай Haskell во имя добра!

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

Давайте изменим наши «хлебные крошки», чтобы они содержали информацию обо всём, что мы проигнорировали ранее, когда двигались влево и вправо. Вместо типа 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, у нас есть вся необходимая информация для восстановления дерева; кроме того, у нас есть фокус на поддереве. Эта схема позволяет нам легко двигаться вверх, влево и вправо.