>elemAt :: Directions –> Tree a –> a

>elemAt (L:ds) (Node _ l _) = elemAt ds l

>elemAt (R:ds) (Node _ _ r) = elemAt ds r

>elemAt [] (Node x _ _) = x

Эта функция на самом деле очень похожа на функцию >changeToP. С одной только разницей: вместо запоминания того, что встречается на пути, и воссоздания дерева она игнорирует всё, кроме своего места назначения. Здесь мы заменяем символ >'W' символом >'P' и проверяем, сохраняется ли изменение в нашем новом дереве:

>ghci> let newTree = changeToP [R,L] freeTree

>ghci> elemAt [R,L] newTree

>'P'

Кажется, работает! В этих функциях список направлений служит чем-то вроде фокуса, потому как в точности указывает на одно поддерево нашего дерева. Например, список направлений >[R] фокусируется на поддереве, находящемся справа от корня. Пустой список направлений фокусируется на самом главном дереве.

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

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

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

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