Учебник по Haskell

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

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

вернуться обратно, опять пойти в туже соседнюю вершину, и так до бесконечности. Для того, чтобы избежать

подобных ситуаций мы будем запоминать те вершины, в которых мы уже побывали и не рассматривать их,

если они встретятся нам ещё раз.

Сформулируем задачу поиска в типах. У нас есть дерево поиска, которое содержит все возможные раз-

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

вершина к цели. Также у нас есть специальный предикат, который определён на вершинах, по нему мы мо-

жем узнать является ли данная вершина целью. Нам нужно получить путь, или цепочку вершин, которая

будет начинаться в корне дерева поиска и заканчиваться в целевой вершине.

search :: Ord h => (a -> Bool) -> Tree (a, h) -> Maybe [a]

Здесь a – это значение вершины и h – значение эвристики. Обратите внимание на зависимость Ord h в

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

запоминать повторяющиеся вершины, для этого мы воспользуемся типом множество из стандартного мо-

дуля Data.Set. Внутри Set могут хранится только значения, для которых определены операции сравнения,

поэтому нам придётся добавить в контекст ещё одну зависимость:

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 будет применена не сразу, а