Изучай Haskell во имя добра! (Липовача) - страница 284

>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)