Тропинка из хлебных крошек

Чтобы фокусироваться на поддереве, нам нужно что-то лучшее, нежели просто список направлений, по которому мы следуем из корня нашего дерева. А могло бы помочь, если бы мы начали с корня дерева и двигались на один шаг влево или вправо за раз, оставляя по пути «хлебные крошки»? Используя этот подход, когда мы идём влево, мы запоминаем, что пошли влево; а когда идём вправо, мы запоминаем, что пошли вправо. Давайте попробуем.

Чтобы представить «хлебные крошки», мы также будем использовать список со значениями направлений (значения 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])