поэтому нам придётся добавить в контекст ещё одну зависимость:
import Data.Tree
import qualified Data.Set as S
search :: (Ord h, Ord a) => (a -> Bool) -> Tree (a, h) -> Maybe [a]
Поиск будет заключаться в том, что мы будем обходить дерево от корня к узлам. При этом среди всех
узлов-альтернатив мы будем просматривать узлы с наименьшим значением эвристики. В этом нам помо-
жет специальная структура данных, которая называется очередью с приоритетом (priority queue). Эта очередь
хранит элементы с учётом их старшинства (приоритета). Мы можем добавлять в неё элементы и извлекать
элементы. При этом мы всегда будем извлекать элемент с наименьшим приоритетом. Мы воспользуемся
очередями из библиотеки fingertree. Для начала установим библиотеку:
cabal install fingertree
Теперь посмотрим в документацию и узнаем какие функции нам доступны. Документацию к пакету мож-
но найти на сайте http://hackage.haskell.org/package/fingertree. Пока отложим детальное изучение ин-
терфейса, отметим лишь то, что мы можем добавлять элементы к очереди и извлекать элементы с учётом
приоритета:
Алгоритм эвристического поиска А* | 277
insert
:: Ord k => k -> v -> PQueue k v -> PQueue k v
minView :: Ord k => PQueue k v -> Maybe (v, PQueue k v)
Вернёмся к функции search. Я бы хотел обратить ваше внимание на то, как мы будем разрабатывать эту
функцию. Вспомним, что Haskell – ленивый язык. Это означает, что при обработке рекурсивных типов данных,
функция “углубляется” в значение лишь тогда, когда функция, которая вызвала эту функцию попросит её об
этом. Это даёт нам возможность работать с потенциально бесконечными структурами данных и, что более
важно, разделять сложный алгоритм на независимые составляющие.
В функции search нам необходимо обойти все элементы в порядке значения эвристики и остановиться
в вершине, на которой целевой предикат вернёт True. Но для начала мы добавим к вершинам их пути из
корня, для того чтобы в конце мы смогли узнать как мы попали в текущую вершину. Итак наша функция
разбивается на три составляющие:
search :: (Ord h, Ord a) => (a -> Bool) -> Tree (a, h) -> Maybe [a]
search isGoal =
findPath isGoal . flattenTree . addPath
выпишем типы составляющих функций и проверим код в интерпретаторе.
un = undefined
findPath :: (a -> Bool) -> [Path a] -> Maybe [a]
findPath = un
flattenTree :: (Ord h, Ord a) => Tree (Path a, h) -> [Path a]
flattenTree = un
addPath :: Tree (a, h) -> Tree (Path a, h)
addPath = un
data Path a = Path
{ pathEnd
:: a
, path
:: [a]
}
Обратите внимание на то как поступающие на вход данные разделились между функциями. Информа-
ция о приоритете вершин не идёт дальше функции flattenTree, а предикат isGoal используется только в
функции findPath. Модуль прошёл проверку типов и мы можем детализировать функции дальше:
addPath :: Tree (a, h) -> Tree (Path a, h)
addPath = iter []
where iter ps t = Node (Path val (reverse ps’), h) $
iter ps’ subForest t
where (val, h)
= rootLabel t
ps’
= val : ps
В этой функции мы просто присоединяем к данной вершине все родительские вершины, так мы составля-
ем маршрут от данной вершины до начальной, поскольку мы всё время добавляем новые вершины в начало
списка, в итоге у нас получаются перевёрнутые маршруты, поэтому перед тем как обернуть значение в кон-
структор Path мы переворачиваем список. На самом деле нам нужно перевернуть только один путь. Путь,
который ведёт к цели, но за счёт того, что язык у нас ленивый, функция reverse будет применена не сразу, а
лишь тогда, когда нам действительно понадобится значение пути. Это как раз и произойдёт лишь один раз,
в самом конце программы, лишь для одного значения!
Давайте пока пропустим функцию flattenTree и сначала определим функцию findPath. Эта функция
принимает все вершины, которые мы обошли если бы шли без цели (функции isGoal) и ищет среди них
первую, которая удовлетворяет предикату. Для этого мы воспользуемся стандартной функцией find из мо-
дуля Data.List:
findPath :: (a -> Bool) -> [Path a] -> Maybe [a]
findPath isGoal =
fmap path . find (isGoal . pathEnd)
Напомню тип функции find, она принимает предикат и список, а возвращает первое значение списка, на
котором предикат вернёт True:
find :: (a -> Bool) -> [a] -> Maybe a
278 | Глава 19: Ориентируемся по карте
Функция fmap применяется из-за того, что результат функции find завёрнут в Maybe, это частично опре-
делённая функция. В самом деле ведь в списке может и не оказаться подходящего значения.
Осталось определить функцию flattenTree. Было бы хорошо определить её так, чтобы она была развёрт-
кой для списка. Поскольку функция find является свёрткой (может быть определена через fold), вместе эти
функции работали бы очень эффективно. Мы определим функцию flattenTree через взаимную рекурсию.
Две функции будут по очереди вызывать друг друга. Одна из них будет извлекать следующее значение из
очереди, а другая – проверять не встречалось ли нам уже такое значение, и добавлять новые элементы в
очередь.
flattenTree :: (Ord h, Ord a) => Tree (Path a, h) -> [Path a]
flattenTree a = ping none (singleton a)