Композиция монадических функций

Когда мы говорили о законах монад в главе 13, вы узнали, что функция <=< очень похожа на композицию, но вместо того чтобы

 

работать с обычными функциями типа a –> b, она работает с мона- дическими функциями типа a –> m b. Вот пример:

ghci> let f = (+1). (*100) ghci> f 4

ghci> let g = (\x –> return (x+1)) <=< (\x –> return (x*100)) ghci> Just 4 >>= g

Just 401

В данном примере мы сначала произвели композицию двух обычных функций, применили результирующую функцию к 4, а затем произвели композицию двух монадических функций и пе- редали результирующей функции Just 4 с использованием опера- ции >>=.

Если у вас есть набор функций в списке, вы можете скомпоно- вать их все в одну большую функцию, просто используя констант- ную функцию id в качестве исходного аккумулятора и функцию (.) в качестве бинарной. Вот пример:

ghci> letf = foldr (.) id [(+1),(*100),(+1)] ghci> f 1

201

Функция f принимает число, а затем прибавляет к нему 1, умно- жает результат на 100 и прибавляет к этому 1.

Мы можем компоновать монадические функции так же, но вместо обычной композиции используем операцию <=<, а вмес- то id – функцию return. Нам не требуется использовать функцию foldM вместо foldr или что-то вроде того, потому что функция <=< гарантирует, что композиция будет происходить монадически.

Когда вы знакомились со списковой монадой в главе 13, мы ис- пользовали её, чтобы выяснить, может ли конь пройти из одной позиции на шахматной доске на другую ровно в три хода. Мы со- здали функцию под названием moveKnight, которая берёт позицию коня на доске и возвращает все ходы, которые он может сделать в дальнейшем. Затем, чтобы произвести все возможные позиции, в которых он может оказаться после выполнения трёх ходов, мы создали следующую функцию:

in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

 

И чтобы проверить, может ли конь пройти от start до end в три хода, мы сделали следующее:

canReachIn3:: KnightPos –> KnightPos –> Bool canReachIn3 start end = end `elem` in3 start

Используя композицию монадических функций, можно создать функцию вроде in3, только вместо произведения всех позиций, которые может занимать конь после совершения трёх ходов, мы сможем сделать это для произвольного количества ходов. Если вы посмотрите на in3, то увидите, что мы использовали нашу функцию moveKnight трижды, причём каждый раз применяли операцию >>=, чтобы передать ей все возможные предшествующие позиции. А те- перь давайте сделаем её более общей. Вот так:

import Data.List

inMany:: Int –> KnightPos –> [KnightPos]

inMany x start = return start >>= foldr (<=<) return (replicate x moveKnight)

Во-первых, мы используем функцию replicate, чтобы создать список, который содержит x копий функции moveKnight. Затем мы монадически компонуем все эти функции в одну, что даёт нам функ- цию, которая берёт исходную позицию и недетерминированно перемещает коня x раз. Потом просто превращаем исходную пози- цию в одноэлементный список с помощью функции return и пере- даём его исходной функции.

Теперь нашу функцию canReachIn3 тоже можно сделать более общей:

canReachIn:: Int –> KnightPos –> KnightPos –> Bool canReachIn x start end = end `elem` inMany x start

 

Создание монад

В этом разделе мы рассмотрим пример, показывающий, как тип со- здаётся, опознаётся как монада, а затем для него создаётся подходя- щий экземпляр класса Monad. Обычно мы не намерены создавать мо- наду с единственной целью – создать монаду. Наоборот, мы создаём тип, цель которого – моделировать аспект некоторой проблемы, а затем, если впоследствии мы видим, что этот тип представляет

 

значение с контекстом и может действовать как монада, мы опреде- ляем для него экземпляр класса Monad.

Как вы видели, списки используются для представления неде- терминированных значений. Список вроде [3,5,9] можно рассмат- ривать как одно недетерминированное значение, которое просто не может решить, чем оно будет. Когда мы передаём список в фун- кцию с помощью операции >>=, это просто создаёт все возможные варианты получения элемента из списка и применения к нему фун- кции, а затем представляет эти результаты также в списке.

Если мы посмотрим на список [3,5,9] как на числа 3, 5, и 9, встречающиеся одновременно, то можем заметить, что нет ника- кой информации в отношении того, какова вероятность встретить каждое из этих чисел. Что если бы нам было нужно смоделировать недетерминированное значение вроде [3,5,9], но при этом мы бы хотели показать, что 3 имеет 50-процентный шанс появиться, а ве- роятность появления 5 и 9 равна 25%? Давайте попробуем провес- ти эту работу!

Скажем, что к каждому элементу списка прилагается ещё одно значение: вероятность того, что он появится. Имело бы смысл представить это значение вот так:

[(3,0.5),(5,0.25),(9,0.25)]

Вероятности в математике обычно выражают не в процентах, а в вещественных числах между 0 и 1. Значение 0 означает, что чему-то ну никак не суждено сбыться, а значение 1 – что это что-то непременно произойдёт. Числа с плавающей запятой могут быст- ро создать путаницу, потому что они стремятся к потере точности, но язык Haskell предлагает тип данных для вещественных чисел. Он называется Rational, и определён он в модуле Data.Ratio. Чтобы создать значение типа Rational, мы записываем его так, как будто

 

это дробь. Числитель и знаменатель разделяются символом. Вот несколько примеров:

 

ghci> 1
1 4
ghci> 1	2 + 1
1 1
ghci> 1	3 + 5
19 12

Первая строка – это просто одна четвёртая. Во второй строке мы складываем две половины, чтобы получить целое. В третьей строке складываем одну третью с пятью четвёртыми и получаем девять двенадцатых. Поэтому давайте выбросим эти плавающие за- пятые и используем для наших вероятностей тип Rational:

ghci> [(3,1 2),(5,1 4),(9,1 4)]

[(3,1 2),(5,1 4),(9,1 4)]

Итак, 3 имеет один из двух шансов появиться, тогда как 5 и 9

появляются один раз из четырёх. Просто великолепно!

Мы взяли списки и добавили к ним некоторый дополнительный контекст, так что это тоже представляет значения с контекстами. Прежде чем пойти дальше, давайте обернем это в newtype, ибо, как я подозреваю, мы будем создавать некоторые экземпляры.

import Data.Ratio

 

newtype Prob a = Prob { getProb:: [(a, Rational)] } deriving Show

Это функтор?.. Ну, раз список является функтором, это тоже должно быть функтором, поскольку мы только что добавили что- то в список. Когда мы отображаем список с помощью функции, то применяем её к каждому элементу. Тут мы тоже применим её к каж- дому элементу, но оставим вероятности как есть. Давайте создадим экземпляр:

instance Functor Prob where

fmap f (Prob xs) = Prob $ map (\(x, p) –> (f x, p)) xs

Мы разворачиваем его из newtype при помощи сопоставления с образцом, затем применяем к значениям функцию f, сохраняя

 

вероятности как есть, и оборачиваем его обратно. Давайте посмот- рим, работает ли это:

ghci> fmap negate (Prob [(3,1 2),(5,1 4),(9,1 4)])

Prob {getProb = [(-3,1 2),(-5,1 4),(-9,1 4)]}

Обратите внимание, что вероятности должны давать в сумме 1. Если все эти вещи могут случиться, не имеет смысла, чтобы сумма их вероятностей была чем-то отличным от 1. Думаю, выпадение мо- неты на решку 75% раз и на орла 50% раз могло бы происходить только в какой-то странной Вселенной.

А теперь главный вопрос: это монада? Учитывая, что список является монадой, похоже, и это должно быть монадой. Во-пер- вых, давайте подумаем о функции return. Как она работает со списками? Она берёт значение и помещает его в одноэлементный список. Что здесь происходит? Поскольку это должен быть ми- нимальный контекст по умолчанию, она тоже должна создавать одноэлементный список. Что же насчёт вероятности? Вызов вы- ражения return x должен создавать монадическое значение, кото- рое всегда представляет x как свой результат, поэтому не имеет смысла, чтобы вероятность была равна 0. Если оно всегда должно представлять это значение как свой результат, вероятность долж- на быть равна 1!

А что у нас с операцией >>=? Выглядит несколько мудрёно, по- этому давайте воспользуемся тем, что для монад выражение m >>= f всегда равно выражению join (fmap f m), и подумаем, как бы мы раз- гладили список вероятностей списков вероятностей. В качестве примера рассмотрим список, где существует 25-процентный шанс, что случится именно 'a' или 'b'. И 'a', и 'b' могут появиться с рав- ной вероятностью. Также есть шанс 75%, что случится именно 'c' или 'd'. То есть 'c' и 'd' также могут появиться с равной вероят- ностью. Вот рисунок списка вероятностей, который моделирует данный сценарий:

 

Каковы шансы появления каждой из этих букв? Если бы мы должны были изобразить просто четыре коробки, каждая из ко- торых содержит вероятность, какими были бы эти вероятности? Чтобы узнать это, достаточно умножить каждую вероятность на все вероятности, которые в ней содержатся. Значение 'a' появи- лось бы один раз из восьми, как и 'b', потому что если мы умножим одну четвёртую на одну четвёртую, то получим одну восьмую. Зна- чение 'c' появилось бы три раза из восьми, потому что три четвёр- тых, умноженные на одну вторую, – это три восьмых. Значение 'd' также появилось бы три раза из восьми. Если мы сложим все веро- ятности, они по-прежнему будут давать в сумме единицу.

Вот эта ситуация, выраженная в форме списка вероятностей:

thisSituation:: Prob (Prob Char) thisSituation = Prob

[(Prob [('a',1	2),('b',1	2)], 1	4)
,(Prob [('c',1	2),('d',1	2)], 3	4)
]

Обратите внимание, её тип – Prob (Prob Char). Поэтому теперь, когда мы поняли, как разгладить вложенный список вероятностей, всё, что нам нужно сделать, – написать для этого код. Затем мы мо- жем определить операцию >>= просто как join (fmap f m), и заполу- чим монаду! Итак, вот функция flatten, которую мы будем исполь- зовать, потому что имя join уже занято:

flatten:: Prob (Prob a) –> Prob a

flatten (Prob xs) = Prob $ concat $ map multAll xs

where multAll (Prob innerxs, p) = map (\(x, r) –> (x, p*r)) innerxs

Функция multAll принимает кортеж, состоящий из списка веро- ятностей и вероятности p, которая к нему приложена, а затем умно- жает каждую внутреннюю вероятность на p, возвращая список пар элементов и вероятностей. Мы отображаем каждую пару в нашем списке вероятностей с помощью функции multAll, а затем просто разглаживаем результирующий вложенный список.

Теперь у нас есть всё, что нам нужно. Мы можем написать экзем- пляр класса Monad!

instance Monad Prob where return x = Prob [(x,1 1)]

 

m >>= f = flatten (fmap f m) fail _ = Prob []

Поскольку мы уже сделали всю тяжелую работу, экземпляр очень прост. Мы опреде- лили функцию fail, которая такова же, как и для списков, поэтому если при сопоставле- нии с образцом в выражении do происходит неудача, неудача случается в контексте спис- ка вероятностей.

Важно также проверить, что для только что созданной нами монады выполняются законы монад:

1. Первое правило говорит, что выра- жение return x >>= f должно равнять- ся выражению f x. Точное доказатель- ство было бы довольно громоздким, но нам видно, что если мы поместим значение в контекст по умолчанию с помощью функции return, затем отобразим это с помощью функции, используя fmap, а потом отобразим

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

2. Второе правило утверждает, что выражение m >> return ни- чем не отличается от m. Для нашего примера доказательство того, что выражение m >> return равно просто m, аналогично доказательству первого закона.

3. Третий закон утверждает, что выражение f <=< (g <=< h) должно быть аналогично выражению (f <=< g) <=< h. Это тоже верно, потому что данное правило выполняется для списковой монады, которая составляет основу для мона- ды вероятностей, и потому что умножение ассоциативно. 1 2 * (1 3 * 1 5) равно (1 2 * 1 3) * 1 5.

Теперь, когда у нас есть монада, что мы можем с ней делать? Она может помочь нам выполнять вычисления с вероятностями.

 

Мы можем обрабатывать вероятностные события как значения с контекстами, а монада вероятностей обеспечит отражение этих вероятностей в вероятностях окончательного результата.

Скажем, у нас есть две обычные монеты и одна монета, с одной стороны налитая свинцом: она поразительным образом выпадает на решку девять раз из десяти и на орла – лишь один раз из десяти. Если мы подбросим все монеты одновременно, какова вероятность того, что все они выпадут на решку? Во-первых, давайте создадим значения вероятностей для подбрасывания обычной монеты и для монеты, налитой свинцом:

data Coin = Heads | Tails deriving (Show, Eq)

 

coin:: Prob Coin

coin = Prob [(Heads,1 2),(Tails,1 2)]

 

loadedCoin:: Prob Coin

loadedCoin = Prob [(Heads,1 10),(Tails,9 10)]

И наконец, действие по подбрасыванию монет:

import Data.List (all)

 

flipThree:: Prob Bool flipThree = do

a <– coin b <– coin

c <– loadedCoin

return (all (==Tails) [a,b,c])

При попытке запустить его видно, что вероятность выпадения решки у всех трёх монет не так высока, даже несмотря на жульни- чество с нашей налитой свинцом монетой:

ghci> getProb flipThree

[(False,1 40),(False,9 40),(False,1 40),(False,9 40),

(False,1 40),(False,9 40),(False,1 40),(True,9 40)]

Все три приземлятся решкой вверх 9 раз из 40, что составля- ет менее 25%!.. Видно, что наша монада не знает, как соединить все исходы False, где все монеты не приземляются решкой вверх,

 

в один исход. Впрочем, это не такая серьёзная проблема, поскольку написание функции для вставки всех одинаковых исходов в один исход довольно просто (это упражнение я оставляю вам в качест- ве домашнего задания).

В этом разделе мы перешли от вопроса («Что если бы списки также содержали информацию о вероятностях?») к созданию ти- па, распознанию монады и, наконец, созданию экземпляра и вы- полнению с ним некоторых действий. Думаю, это очаровательно! К этому времени у вас уже должно сложиться довольно неплохое понимание монад и их сути.

 

ЗАСТЁЖКИ

Хотя чистота языка Haskell даёт море преимуществ, вместе с тем он заставляет нас решать некоторые проблемы не так, как мы решали бы их в нечистых языках.

Из-за прозрачности ссылок одно значение в языке Haskell всё равно что другое, если оно представляет то же самое. Поэтому если у нас есть дерево, заполненное пятёрками (или, мо- жет, пятернями?), и мы хотим изменить одну из них на шестёрку, мы должны каким-то образом понимать, какую именно пятёрку в нашем де- реве мы хотим изменить. Нам нужно знать, где в нашем дереве она находится. В нечистых язы- ках можно было бы просто указать, где в памяти находится пятёрка, и изменить её. Но в языке 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] фо- кусируется на поддереве, находящемся справа от корня. Пустой список направлений фокусируется на самом главном дереве.

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

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

 

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

Чтобы фокусироваться на поддереве, нам нужно что-то лучшее, не- жели просто список направлений, по которому мы следуем из кор- ня нашего дерева. А могло бы помочь, если бы мы начали с корня дерева и двигались на один шаг

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

Чтобы представить «хлеб- ные крошки», мы также будем

 

использовать список со значениями направлений (значения 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, содержащее элемент узла, из которого мы переместились, и не по- сещённое нами левое поддерево.

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

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

Давайте также изменим наш синоним типа Breadcrumbs, чтобы отразить это:

type Breadcrumbs a = [Crumb a]

Затем нам нужно изменить функции goLeft и goRight, чтобы они сохраняли информацию о путях, по которым мы не пошли, в на- ших «хлебных крошках», а не игнорировали эту информацию, как они делали это раньше. Вот новое определение функции goLeft:

goLeft:: (Tree a, Breadcrumbs a) –> (Tree a, Breadcrumbs a) goLeft (Node x l r, bs) = (l, (LeftCrumb x r):bs)

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

 

чение LeftCrumb, чтобы показать, что мы пошли влево. Мы также снабжаем наше значение LeftCrumb элементом узла, из которого мы переместились (то есть значением x), и правым поддеревом, кото- рое мы решили не посещать.

Обратите внимание: эта функция предполагает, что текущее де- рево, находящееся в фокусе, – не Empty. Пустое дерево не содержит никаких поддеревьев, поэтому если мы попытаемся пойти влево из пустого дерева, возникнет ошибка. Причина в том, что сравнение значения типа Node с образцом будет неуспешным, и нет образца, который заботится о конструкторе Empty.

Функция goRight аналогична:

goRight:: (Tree a, Breadcrumbs a) –> (Tree a, Breadcrumbs a) goRight (Node x l r, bs) = (r, (RightCrumb x l):bs)

Ранее мы могли двигаться влево или вправо. То, чем мы распола- гаем сейчас, – это возможность действительно возвращаться вверх, запоминая информацию о родительских узлах и путях, которые мы не посетили. Вот определение функции goUp:

goUp:: (Tree a, Breadcrumbs a) –> (Tree a, Breadcrumbs a) goUp (t, LeftCrumbx r:bs) = (Node x t r, bs)

goUp (t, RightCrumb x l:bs) = (Node x l t, bs)

Мы фокусируемся на дере- ве t и проверяем последнее зна- чение типа Crumb. Если это значе- ние равно LeftCrumb, мы строим новое дерево, используя наше де- рево t в качестве левого поддере- ва и информацию о правом под- дереве и элементе, которые мы не посетили, чтобы заполнить остальные части Node. Посколь- ку мы «переместились обратно» и подняли последнюю «хлебную