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

Как вы узнали на уроках биологии, есть множество различных деревьев, поэтому давайте выберем зёрнышко, которое мы используем, чтобы посадить наше. Вот оно:

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

Наше дерево или пусто, или является узлом, содержащим элемент и два поддерева. Вот хороший пример такого дерева, которое я отдаю вам, читатель, просто задаром!

freeTree :: Tree Char

freeTree =

  Node 'P'

    (Node 'O'

      (Node 'L'

        (Node 'N' Empty Empty)

        (Node 'T' Empty Empty)

      )

      (Node 'Y'

        (Node 'S' Empty Empty)

        (Node 'A' Empty Empty)

      )

    )

    (Node 'L'

      (Node 'W'

        (Node 'C' Empty Empty)

        (Node 'R' Empty Empty)

      )

      (Node 'A'

        (Node 'A' Empty Empty)

        (Node 'C' Empty Empty)

      )

    )

А вот это дерево, представленное графически:

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