Миран Липовача: Изучай 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. Поскольку мы «переместились обратно» и подняли последнюю «хлебную крошку», а затем использовали её, чтобы воссоздать родительское дерево, в новом списке эта «хлебная крошка» не содержится.