Как вы узнали на уроках биологии, есть множество различных деревьев, поэтому давайте выберем зёрнышко, которое мы используем, чтобы посадить наше. Вот оно:
>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)