Изучай Haskell во имя добра! - Миран Липовача

Заметили символ W в дереве? Предположим, мы хотим заменить его символом P. Как нам это сделать? Ну, один из подходящих способов – сопоставление нашего дерева с образцом до тех пор, пока мы не найдём элемент, сначала двигаясь вправо, а затем влево. Вот соответствующий код:

changeToP :: Tree Char –> Tree Char

changeToP (Node x l (Node y (Node _ m n) r)) = Node x l (Node y (Node 'P' m n) r)

Тьфу, какая гадость! Это не только некрасиво, но к тому же несколько сбивает с толку. Что здесь на самом деле происходит? Мы сопоставляем наше дерево с образцом и даём его корневому элементу идентификатор x (который превращается в символ 'P' из корня), а левому поддереву – идентификатор l. Вместо того чтобы дать имя правому поддереву, мы опять же сопоставляем его с образцом. Мы продолжаем это сопоставление с образцом до тех пор, пока не достигнем поддерева, корнем которого является наш искомый символ 'W'. Как только мы произвели сопоставление, мы перестраиваем дерево; только поддерево, которое содержало символ 'W', теперь содержит символ 'P'.

Есть ли лучший способ? Как насчёт того, чтобы наша функция принимала дерево вместе со списком направлений? Направления будут кодироваться символами L или R, представляя левую и правую стороны соответственно, и мы изменим элемент, которого достигнем, следуя переданным направлениям. Посмотрите:

data Direction = L | R deriving (Show)

type Directions = [Direction]

changeToP :: Directions –> Tree Char –> Tree Char

changeToP (L:ds) (Node x l r) = Node x (changeToP ds l) r

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] фокусируется на поддереве, находящемся справа от корня. Пустой список направлений фокусируется на самом главном дереве.

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

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

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

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

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

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

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

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

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

Давайте изменим наши «хлебные крошки», чтобы они содержали информацию обо всём, что мы проигнорировали ранее, когда двигались влево и вправо. Вместо типа Direction создадим новый тип данных:

data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a) deriving (Show)

Теперь вместо кода L у нас есть значение LeftCrumb, содержащее также элемент узла, из которого мы переместились, и не посещённое нами правое поддерево. Вместо кода R есть значение RightCrumb, содержащее элемент узла, из которого мы переместились, и не посещённое нами левое поддерево.