Изучай Haskell во имя добра! (Липовача) - страница 280

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

Прогулка

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

>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)