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