>changeToP (R:ds) (Node x l r) = Node x l (changeToP ds r)
>changeToP [] (Node _ l r) = Node 'P' l r
Если первый элемент в списке направлений – >L, мы строим новое дерево, похожее на прежнее, только элемент в его левом под дереве заменён символом >'P'. Когда мы рекурсивно вызываем функцию >changeToP, то передаём ей только «хвост» списка направлений, потому что мы уже переместились влево. То же самое происходит в случае с направлением >R. Если список направлений пуст, это значит, что мы дошли до нашего места назначения, так что мы возвращаем дерево, аналогичное переданному, за исключением того, что в качестве корневого элемента оно содержит символ >'P'.
Чтобы не распечатывать дерево целиком, давайте создадим функцию, которая принимает список направлений и сообщает нам об элементе в месте назначения:
>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] фокусируется на поддереве, находящемся справа от корня. Пустой список направлений фокусируется на самом главном дереве.
Хотя эта техника с виду весьма хороша, она может быть довольно неэффективной, особенно если мы хотим часто изменять элементы. Скажем, у нас есть огромное дерево и длинный список направлений, который указывает весь путь до некоего элемента в самом низу дерева. Мы используем список направлений, чтобы пройтись по дереву и изменить элемент внизу. Если мы хотим изменить другой элемент, который близок к только что изменённому нами элементу, нужно начать с корня дерева и снова пройти весь путь вниз. Какая тоска!..
В следующем разделе мы найдём более удачный способ фокусироваться на поддереве – способ, который позволяет нам эффективно переводить фокус на близлежащие поддеревья.
Тропинка из хлебных крошек
Чтобы фокусироваться на поддереве, нам нужно что-то лучшее, нежели просто список направлений, по которому мы следуем из корня нашего дерева. А могло бы помочь, если бы мы начали с корня дерева и двигались на один шаг влево или вправо за раз, оставляя по пути «хлебные крошки»? Используя этот подход, когда мы идём влево, мы запоминаем, что пошли влево; а когда идём вправо, мы запоминаем, что пошли вправо. Давайте попробуем.