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