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

Чтобы представить «хлебные крошки», мы также будем использовать список со значениями направлений (значения >L и >R), называя их, однако, не >Directions, а >Breadcrumbs, потому что наши направления теперь будут переворачиваться по мере того, как мы оставляем их, проходя вниз по нашему дереву.

>type Breadcrumbs = [Direction]

Вот функция, которая принимает дерево и какие-то «хлебные крошки» и перемещается в левое поддерево, добавляя код >L в «голову» списка, который представляет наши хлебные крошки:

>goLeft :: (Tree a, Breadcrumbs) –> (Tree a, Breadcrumbs)

>goLeft (Node _ l _, bs) = (l, L:bs)

Мы игнорируем элемент в корне и правое поддерево и просто возвращаем левое поддерево вместе с прежними «хлебными крошками», где код >L присутствует в качестве «головы».

Вот функция для перемещения вправо:

>goRight :: (Tree a, Breadcrumbs) –> (Tree a, Breadcrumbs)

>goRight (Node _ _ r, bs) = (r, R:bs)

Она работает так же, как и функция для перемещения влево.

Давайте используем эти функции, чтобы взять наше дерево >freeTree и переместиться вправо, а затем влево.

>ghci> goLeft (goRight (freeTree, []))

>(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])

Теперь у нас есть дерево с символом >'W', находящимся в его корне, символом >'C' – в корне его левого поддерева и символом >'R' – в корне правого поддерева. «Хлебными крошками» являются коды >[L,R], потому что сначала мы пошли вправо, а затем влево.

Чтобы сделать обход нашего дерева более ясным, мы можем использовать оператор >–: из главы 13, который мы определили следующим образом:

>x –: f = f x

Это позволяет нам применять функции к значениям, сначала записывая значение, потом >–:, а затем функцию. Поэтому вместо выражения >goRight (freeTree, []) мы можем написать >(freeTree, []) –: goRight. Используя эту форму, перепишем предыдущий пример так, чтобы было более очевидно, что мы идём вправо, а затем влево:

>ghci> (freeTree, []) -: goRight -: goLeft

>(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])

Что, если мы хотим пойти обратно вверх по нашему дереву? Благодаря «хлебным крошкам» нам известно, что текущее дерево является левым поддеревом своего родителя, а последнее является правым поддеревом своего родителя – собственно, это всё, что нам известно. «Хлебные крошки» не сообщают нам достаточно сведений о родителе текущего поддерева, чтобы была возможность пойти вверх по дереву. Похоже, что помимо направления, по которому мы пошли, отдельная «хлебная крошка» должна также содержать все остальные сведения, которые необходимы для обратного движения вверх. В таком случае необходимыми сведениями являются элемент в родительском дереве вместе с его правым поддеревом.