where f (s, h) = ((s, heur h s), next h alts s)
heur h s = h + distToGoal s
next h (a, d) = (a, d + h)
Поиск маршрутов в метро
Теперь давайте посмотрим как наша функция справится с задачей поиска маршрутов в метро:
metroTree :: Station -> Station -> Tree (Station, Double)
metroTree init goal = astarTree distMetroMap (stationDist goal) init
connect :: Station -> Station -> Maybe [Station]
connect a b = search (== b) $ metroTree a b
main = print $ connect (St Red Sirius) (St Green Prizrak)
К примеру найдём маршрут от станции “Дно Болота” до станции “Призрак”:
*Metro> connect (St Orange DnoBolota) (St Green Prizrak)
Just [St Orange DnoBolota, St Orange PlBakha,
St Red PlBakha, St Red Sirius, St Green Sirius,
St Green Zvezda, St Green Til,
St Green TrollevMost, St Green Prizrak]
*Metro> connect (St Red PlShekspira) (St Blue De)
Just [St Red PlShekspira, St Red Rodnik, St Blue Rodnik,
St Blue Krest, St Blue De]
*Metro> connect (St Red PlShekspira) (St Orange De)
Nothing
В третьем случае маршрут не был найден, поскольку у нас нет станции De на оранжевой ветке.
19.2 Тестирование с помощью QuickCheck
Мы проверили три случая, ещё три случая, ещё три случая, ожидаемый результат сходится с тем, что
возвращает нам интерпретатор, но можем ли мы быть уверены в том, что алгоритм действительно работает?
280 | Глава 19: Ориентируемся по карте
Для Haskell была разработана специальная библиотека тестирования QuickCheck, которая упрощает про-
цесс проверки программ. Мы можем сформулировать свойства, которые обязательно должны выполняться,
а QuickCheck сгенерирует случайный набор данных и проверит наши свойства на них.
Например в нашей задаче путь из A в B должен совпадать с перевёрнутым путём из B в A. Также все станции
в маршруте должны быть соседними. Давайте проверим эти свойства. Для этого нам нужно сформулировать
их в виде предикатов:
module Test where
import Control.Applicative
import Metro
prop1 :: Station -> Station -> Bool
prop1 a b = connect a b == (fmap reverse $ connect b a)
prop2 :: Station -> Station -> Bool
prop2 a b = maybe True (all (uncurry near) . pairs) $ connect a b
pairs :: [a] -> [(a, a)]
pairs xs = zip xs (drop 1 xs)
near :: Station -> Station -> Bool
near a b = a ‘elem‘ (fst distMetroMap b)
Установим QuickCheck:
cabal install QuickCheck
Теперь нам нужно подсказать QuickCheck как генерировать случайные значения типа Station. QuickCheck
тестирует функции, которые принимают значения из класса Arbitrary и возвращают Bool. Класс Arbitrary
отвечает за генерацию случайных значений.
Основной метод arbitrary возвращает генератор случайных значений:
class Arbitrary a where
arbitrary :: Gen a
Мы воспользуемся тем, что этот класс уже определён для многих стандартных типов. Кроме того класс
Gen явялется монадой. Мы сгенерируем случайное целое число и отобразим его в одну из станций. Сделать
это можно разными способами, мы начнём из одной станции и будем случайно блуждать по карте:
import Test.QuickCheck
…
instance Arbitrary Station where
arbitrary = ($ s0) . foldr (. ) id . fmap select ints
where ints = vector =<< choose (0, 100)
s0 = St Blue De
select :: Int -> Station -> Station
select i s = as !! mod i (length as)
where as = fst distMetroMap s
Мы воспользовались двумя функциями из бибилотеки QuickCheck. Это vector и choose. Первая строит
список случайных чисел заданной длины, а вторая выбирает случайное число из заданного диапазона. Теперь
мы можем протетстировать наши предикаты с помощью функции quickCheck:
*Test Prelude> quickCheck prop1
+++ OK, passed 100 tests.
*Test Prelude> quickCheck prop2
+++ OK, passed 100 tests.
*Test Prelude>
Свойства прошли тестирование на выборке из 100 комбинаций аргументов. Если нам интересно, мы
можем с помощью функции verboseCheck посмотреть на каких именно значениях проводилось тестирование:
Тестирование с помощью QuickCheck | 281
*Test Prelude> verboseCheck prop2
Passed:
St Black Kosmodrom
St Red UlBylichova
Passed:
St Black UlBylichova
St Orange Sever
Passed:
St Red Sirius
St Blue Krest
…
Если бы свойство не выполнилось, QuickCheck сообщил бы нам об этом и показал бы те элементы, для
которых свойство не выполнилось. Давайте составим такое свойство искусственно. Например, проверим,
находятся ли все станции на одной линии:
fakeProp :: Station -> Station -> Bool
fakeProp (St a _) (St b _) = a == b
Посмотрим, что на это скажет QuickCheck:
*Test Prelude> quickCheck fakeProp
*** Failed! Falsifiable (after 1 test):
St Green Sirius
St Blue Rodnik
По умолчанию QuickCheck проверит свойство сто раз. Для изменения этих настроек, мы можем восполь-
зоваться функцией quickCheckWith, дополнительным параметром она принимает значение типа Arg, которое
содержит параметры тестирования. Например протестируем первое свойство 500 раз:
*Test> quickCheckWith (stdArgs{ maxSuccess = 500 }) prop1
+++ OK, passed 500 tests.
Мы воспользовались стандартными настройками (stdArgs) и изменили один параметр.
Формирование тестовой выборки
Предположим, что мы уверены в правильной работе алгоритма для голубой и чёрной ветки метро, но
сомневаемся в остальных. Как раз для этого случая в QuickCheck предусмотрена функция a==> b. Это функ-
ция обозначает условную проверку, свойство b будет протестировано только в том случае, если свойство a
окажется верным. Иначе тестовые данные будут отброшены.
notBlueAndBlack a b = cond a && cond b ==> prop1 a b
where cond (St a _) = a /= Blue && a /= Black
Далее тестируем как обычно:
*Test> quickCheck notBlueAndBlack
+++ OK, passed 100 tests.
Также с помощью функции forAll мы можем подсказать QuickCheck на каких данных тестировать свой-
ство.
forAll :: (Show a, Testable prop) => Gen a -> (a -> prop) -> Property
Эта функция принимает генератор случайных значений и свойство, которое зависит от тех значений,
которые создаются этим генератором. К примеру, пусть нас интересуют только все возможные пути между
четырьмя станциями: (St Blue De), (St Red Lao), (St Green Til) и (St Orange Sever). Воспользуемся
функцией elements :: [a] -> Gen a, она как раз принимает список значений, и возвращает генератор,
который случайным образом выбирает любое значение из этого списка.
testFor = forAll (liftA2 (,) gen gen) $ uncurry prop1
where gen = elements [St Blue De, St Red Lao,
St Green Til, St Orange Sever]
Проверим, те ли значения попали в выборку:
282 | Глава 19: Ориентируемся по карте
*Test> verboseCheckWith (stdArgs{ maxSuccess = 3 }) testFor
Passed:
(St Blue De, St Orange Sever)
Passed:
(St Orange Sever, St Red Lao)
Passed:
(St Red Lao, St Red Lao)
+++ OK, passed 3 tests.
Мы можем настроить формирование выборки ещё одним способом. Для этого мы сделаем специальный
тип обёртку над Station и определим для ненго свой экземпляр класса Arbitrary:
newtype OnlyOrange = OnlyOrange Station
newtype Only4
= Only4
Station
instance Arbitrary OnlyOrange where
arbitrary = OnlyOrange . St Orange
elements [DnoBolota, PlBakha, Krest, Lao, Sever]
instance Arbitrary Only4 where
arbitrary = Only4 elements [St Blue De, St Red Lao,
St Green Til, St Orange Sever]
После этого мы можем очень легко комбинировать различные выборки при тестировании.
