интервала (ci, confidence interval). Среднее значение показывает оценку величины, мы говорим, что алго-
ритм работает примерно 100 миллисекунд. Дисперсия – это разброс результатов вокруг среднего значения.
С правой стороны мы видим графики с точками. Каждая точка обозначает отдельный запуск алгоритма.
Количество запусков соответствует флагу -s. В последнеё строке под графиком criterion сообщает степень
недоверия к результатам. В последнем опыте этот показатель достаточно высок. Возможно это связано с тем,
что наш алгоритм выбора случайных станций имеет сильный разброс по времени. Ведь сначала мы генери-
руем слуайное число n от 0 до 100, и затем начинаем блуждать по карте от начальной точке n раз. Также
может влиять то, что время работы алгоритма зависит от положения станций.
19.4 Краткое содержание
В этой главе мы реализовали алгоритм эвристического поиска А*. Также мы узнали несколько стандарт-
ных структур данных. Это множества и очереди с приоритетом и освежили в памяти ленивые вычисления.
Мы научились проверять свойства программ (QuickCheck), а также оценивать быстродействие программ
(criterion).
19.5 Упражнения
• Я говорил о том, что два варианта алгоритмов дают одинаковые результаты, но так ли это на самом
деле? Проверьте это в QuickCheck.
• Алгоритм эвристического поиска может применятся не только для поиска маршрутов на карте. Часто
алгоритм А* применяется в играх. Встройте этот алгоритм в игру пятнашки (глава 13). Если игрок за-
путался и не знает как ходить, он может попросить у компьютера совет. В этой задаче альтернативы~–
это вершины графа, соседние вершины~– это те вершины, в которые мы можем попасть за один ход.
Подсказка: воспользуйтесь манхэттенским расстоянием.
• Оцените эффективность двух алгоритмов поиска в игре пятнашки. Рассмотрите зависимость быстро-
действия от степени сложности игры.
Краткое содержание | 287
Глава 20
Императивное программирование
В этой главе мы потренируемся в укрощении императивного кода. В Haskell все побочные эффекты огоро-
жены от чистых функций бетонной стеной IO. Однажды оступившись, мы не можем свернуть с пути побочных
эффектов, мы вынуждены тащить на себе груз IO до самого конца программы. Тип IO, хоть и обволакивает
программу, всё же позволяет пользоваться благами чистых вычислений. От программиста зависит насколь-
ко сильна будет хватка IO. Необходимо уметь выделять точки, в которых применение побочных вычислений
действительно необходимо, подключая в них чистые функции через методы классов Functor, Applicative
и Monad. Тип IO похож на дорогу с контрольными пунктами, в которых необходимо отчитаться перед ком-
пилятором за “грязный код”. При неумелом проектировании написание программ, насыщенных побочными
эффектами, может превратится в пытку. Контрольные пункты будут встречаться в каждой функции.
Естественный источник побочных эффектов – это пользователь программы. Но, к сожалению, это не един-
ственный источник. Haskell – открытый язык программирования. В нём можно пользоваться программами
из низкоуровневого языка C. Основное преимущество С заключается в непревзойдённой скорости программ.
Этот язык позволяет программисту работать с памятью компьютера напрямую. Но за эту силу приходится
платить. Возможны очень неприятные и трудноуловимые ошибки. Утечки памяти, обращение по неверному
адресу в памяти, неожиданное обновление переменных. Ещё один плюс С в том, что это язык с историей,
на нём написано много хороших библиотек. Некоторые из них встроены в Haskell с помощью специального
механизма FFI (foreign function interface). Обсуждение того, как устроен FFI выходит за рамки этой книги. Ин-
тересующийся читатель может обратиться к книге Real World Haskell. Мы же потренируемся в использовании
таких библиотек. Язык C является императивным, поэтому, применяя его функций в Haskell, мы неизбежно
сталкиваемся с типом IO, поскольку большинство интересных функций в С изменяют состояние своих аргу-
ментов. В С пишут и чистые функции, такие функции переносятся в Haskell без потери чистоты, но это не
всегда возможно.
В этой главе мы напишем небольшую 2D-игру, подключив две FFI-библиотеки, это графическая библио-