Изучай Haskell во имя добра!

Хотя эта техника с виду весьма хороша, она может быть довольно неэффективной, особенно если мы хотим часто изменять элементы. Скажем, у нас есть огромное дерево и длинный список направлений, который указывает весь путь до некоего элемента в самом низу дерева. Мы используем список направлений, чтобы пройтись по дереву и изменить элемент внизу. Если мы хотим изменить другой элемент, который близок к только что изменённому нами элементу, нужно начать с корня дерева и снова пройти весь путь вниз. Какая тоска!..

В следующем разделе мы найдём более удачный способ фокусироваться на поддереве – способ, который позволяет нам эффективно переводить фокус на близлежащие поддеревья.

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

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

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

Движемся обратно вверх

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

Вообще у отдельной «хлебной крошки» должны быть все сведения, необходимые для восстановления родительского узла. Так что она должна иметь информацию из всех путей, которыми мы не пошли, а также знать направление, по которому мы пошли. Однако она не должна содержать поддерево, на котором мы фокусируемся в текущий момент, – потому что у нас уже есть это поддерево в первом компоненте кортежа. Если бы оно присутствовало у нас и в «хлебной крошке», мы бы имели копию уже имеющейся информации.