4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, …
И так далее, на каждом шаге мы будем получать одно простое число. Зачёркивание мы будем имитиро-
вать с помощью типа Maybe. Всё начинается с потока целых чисел, в котором не зачёркнуто ни одно число:
nums :: Stream (Maybe Int)
nums = mapS Just $ iterateS (+1) 2
mapS :: (a -> b) -> Stream a -> Stream b
mapS f = ana $ \xs -> (f $ headS xs) :& tailS xs
iterateS :: (a -> a) -> a -> Stream a
iterateS f = ana $ \x -> x :& f x
В силу ограничений системы типов Haskell мы не можем определить экземпляр Functor для типа Stream,
поскольку Stream является не самостоятельным типом а типом-синонимом. Поэтому нам приходится опре-
делить функцию mapS. Определим шаг рекурсии:
primes :: Stream Int
primes = ana erato nums
erato xs = n :& erase n ys
where n
= fromJust $ headS xs
ys = dropWhileS isNothing xs
Переменная n содержит первое не зачёркнутое число на данном шаге. Переменная ys указывает на спи-
сок чисел, из начала которого удалены все зачёркнутые числа. Функции isNothing и fromJust взяты из стан-
дартного модуля Data.Maybe. Нам осталось определить лишь две функции. Это аналог функции dropWhile
на списках. Эта функция удаляет из начала списка все элементы, которые удовлетворяют некоторому пре-
дикату. Вторая функция erase вычёркивает все числа в потоке кратные данному.
dropWhileS :: (a -> Bool) -> Stream a -> Stream a
dropWhileS p = psi >> phi
where phi ((b, xs) :& next) = if b then next else xs
psi xs = (p $ headS xs, xs) :& tailS xs
В этой функции мы сначала генерируем список пар, который содержит значения предиката и остатки
списка, а затем находим в этом списке первый такой элемент, значение которого равно False.
erase :: Int -> Stream (Maybe a) -> Stream (Maybe a)
erase n xs = ana phi (0, xs)
where phi (a, xs)
| a == 0
= Nothing
:& (a’, tailS xs)
| otherwise = headS xs :& (a’, tailS xs)
where a’ = if a == n-1 then 0 else (a+1)
Гиломорфизм | 249
В функции erase мы заменяем на Nothing каждый элемент, порядок следования которого кратен аргу-
менту n. Проверим, что у нас получилось:
*Fix> primes
(2 :& (3 :& (5 :& (7 :& (11 :& (13 :& (17 :& (19 :& (23 :& (29 :& (31 :& (37 :& (41 :& (43 :& (47 :& (53 :& (59 :&
(61 :& (67 :& (71 :& (73 :& (79 :& (83 :& (89 :& (97 :&
(101 :& (103 :& (107 :& (109 :& (113 :& (127 :& (131 :&
...
16.4 Краткое содержание
В этой главе мы узнали, что любая рекурсивная функция может быть выражена через структурную ре-
курсию. Мы узнали как в теории категорий определяются типы. Типы являются начальными и конечными
объектами в специальных категориях, которые называются алгебрами функторов. Слоган теории категорий
гласит:
Управляющие структуры определяются структурой типов.
Определив тип, мы получаем вместе с ним две функции структурной рекурсии, это катаморфизм (для
начальных объектов) и анаморфизм (для конечных объектов). С помощью катаморфизма мы можем свора-
чивать значение данного типа в значения любого другого типа, а с помощью анаморфизма мы можем раз-
ворачивать значения данного типа из значений любого другого типа. Также мы узнали, что категория Hask
является категорией CPO, категорией полных частично упорядоченных множеств.
16.5 Упражнения
• Потренируйтесь в определении рекурсивных функций через гиломорфизм. Попробуйте переписать как
можно больше определений из главы о структурной рекурсии в терминах типа Fix и функций cata, ana
и hylo. Также потренируйтесь на стандартных функциях из модуля Prelude. Определите новые типы
через Fix например деревья из модуля Data.Tree. Попробуйте свои силы на функциях по-сложнее
например алгоритме эвристического поиска.
• Определите монадные версии рекурсивных функций:
cataM :: (Monad m, Traversable t) => (t a -> m a) -> Fix t -> m a
anaM
:: (Monad m, Traversable t) => (a -> m (t a)) -> (a -> m (Fix t))
hyloM :: (Monad m, Traversable t) => (t b -> m b) -> (a -> m (t a)) -> (a -> m b) С помощью этих функций мы, например, можем преобразовывать дерево выражения и при этом обнов-
лять какое-нибудь состояние или читать из общего окружения.
В этом определении стоит новый класс Traversable. Разберитесь с ним самостоятельно. Немного под-
скажу. Этот класс появился вместе с классом Applicative. Когда разработчики поняли о существова-
нии полезной абстракции, которая ослабляет класс Monad, они также обратили внимание на функцию
sequence:
sequence :: Monad m => [m a] -> m [a]
sequence = foldr (liftM2 (:)) (return [])
Эту функцию можно записать с помощью одних лишь методов класса Applicative. Поэтому ограниче-
ние в контексте функции избыточно. Класс Traversable предназначени для устранения этой неточно-
сти. Посмотрим на основной метод класса:
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
Тип очень похож на тип функции mapM. И не случайно, ведь mapM определяется через sequence. Только
теперь вместо списка стоит более общий тип. Это тип Foldable, который определяет список как нечто,
на чём можно проводить операции свёртки.
250 | Глава 16: Категориальные типы
Глава 17
Дополнительные возможности
В этой главе мы рассмотрим некоторые дополнительные возможности языка и расширения, они часто
используются в серьёзных программах. Можно писать программы и без них, но с ними гораздо легче и увле-
кательней.
17.1 Пуд сахара
В этом разделе мы рассмотрим специальный синтаксический сахар, который позволяет более кратко
записывать операции для некоторых структур.
Сахар для списков
Перечисления
Для класса Enum определён специальный синтаксис составления последовательностей перечисляемых
значений. Так например мы можем составить список целых чисел от нуля до десяти:
Prelude> [0 .. 10]
[0,1,2,3,4,5,6,7,8,9,10]
А так мы можем составить бесконечную последовательность положительных чисел:
Prelude> take 20 $ [0 .. ]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]
Мы можем составлять последовательности с определённым шагом. Так можно выделить все чётные по-
ложительные числа:
Prelude> take 20 $ [0, 2 .. ]
[0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38]
А так мы можем составить убывающую последовательность чисел:
Prelude> [10, 9 .. 0]
[10,9,8,7,6,5,4,3,2,1,0]
Что интересно в списке могут находиться не только числа, а любые значения из класса Enum. Например
определим тип:
data Day
= Monday | Tuesday | Wednesday | Thursday
| Friday | Saturday | Sunday
deriving (Show, Enum)
Теперь мы можем написать:
*Week> [Friday .. Sunday]
[Friday, Saturday, Sunday]
*Week> [ Monday .. ]
[Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday]
Также шаг последовательности может быть и дробным:
*Week> [0, 0.5 .. 4]
[0.0,0.5,1.0,1.5,2.0,2.5,3.0,3.5,4.0]
| 251
Генераторы списков
Генераторы списков (list comprehensions) объединяют в себе функции преобразования и фильтрации спис-
ков. Они записываются так:
[ f x | x <- list, p x]
В этой записи мы фильтруем список list предикатом p и преобразуем результат функцией f. Например
возведём в квадрат все чётные элементы списка:
Prelude> [x*x | x <- [1 .. 10], even x]
[4,16,36,64,100]
Предикатов может быть несколько, так например мы можем оставить лишь положительные чётные числа:
Prelude> [x | x <- [-10 .. 10], even x, x >= 0]
[0,2,4,6,8,10]
Также элементы могут браться из нескольких списков, посмотрим на все возможные комбинации букв из
пары слов:
Prelude> [ [x,y] | x <- ”Hello”, y <- ”World”]
[”HW”,”Ho”,”Hr”,”Hl”,”Hd”,”eW”,”eo”,”er”,”el”,
”ed”,”lW”,”lo”,”lr”,”ll”,”ld”,”lW”,”lo”,”lr”,
”ll”,”ld”,”oW”,”oo”,”or”,”ol”,”od”]
Сахар для монад, do-нотация
Монады используются столь часто, что для них придумали специальный синтаксис, который облегчает
подстановку специальных значений в функции нескольких переменных. Монады позволяют комбинировать
специальные функции вида
a -> m b
Если бы эти функции выглядели как обычные функции:
a -> b
их можно было свободно комбинировать с другими функциями. А так нам постоянно приходится поль-
зоваться методами класса Monad. Очень часто функции с побочными эффектами имеют вид:
a1 -> a2 -> a3 -> ... -> an -> m b
А теперь представьте, что вам нужно подставить специальное значение третьим аргументом такой функ-
ции и затем передать ещё в одну такую же функцию. Для облегчения участи программистов было придумано
специальное окружение do, в котором специальные функции комбинируются так словно они являются обыч-
ными. Для этого используется обратная стрелка. Посмотрим как определяется функция sequence в окруже-
нии do:
sequence :: [m a] -> m [a]
sequence []
= return []
sequence (mx:mxs)
= do
x
<- mx
xs <- sequence mxs
return (x:xs)
Во втором уравнении сначала мы говорим вычислителю словом do о том, что выражения записаны в мире
монады m. Запись с перевёрнутой стрелкой x <- mx означает, что мы далее в do-блоке можем пользоваться
значением x так словно оно имеет тип просто a, но не m a. Смотрите в этом определении мы сначала извле-
каем первый элемент списка, затем извлекаем хвост списка, приведённый к типу m [a], и в самом конце мы
соединяем голову и хвост и в самом конце оборачиваем результат в специальное значение.
Например мы можем построить функцию, которая дважды читает строку со стандартного ввода и затем
возвращает объединение двух строк:
252 | Глава 17: Дополнительные возможности
getLine2 :: IO String
getLine2 = do
a <- getLine
b <- getLine
return (a ++ b)
В do-нотации можно вводить локальные переменные с помощью слова let:
t = do
b <- f a
c <- g b
let x = c + b
y = x + c
return y
Посмотрим как do-нотация переводится в выражение, составленное с помощью методов класса Monad:
do
a <- ma
=>
ma >>= (\a -> exp)
exp
do
exp1
=>
exp1 >> exp2
exp2
do
let x = fx
=>
let x = fx
y = fy
y = fy
exp
in
exp
Переведём с помощью этих правил определение для второго уравнения из функции sequence
sequence (mx:mxs) = do
x
<- mx
mx >>= (\x -> do
xs
<- sequence mxs
=>
xs <- sequence mxs
=>
return (x:xs)
return (x:xs))
=>
mx >>= (\x -> sequence mxs >>= (\xs -> return (x:xs)))
do или Applicative?
С появлением класса Applicative во многих случаях do-нотация теряет свою ценность. Так например
любой do-блок вида:
f mx my = do
x <- mx
y <- my
return (op x y)
Можно записать гораздо короче:
f = liftA2 op
Например напишем функцию, которая объединяет два файла в один:
appendFiles :: FilePath -> FilePath -> FilePath -> IO ()
С помощью do-нотации:
appendFiles file1 file2 resFile = do
a <- readFile file1
b <- readFile file2
writeFile resFile (a ++ b)
А теперь с помощью класса Applicative:
appendFiles file1 file2 resFile = writeFile resFile =<<
liftA2 (++) (readFile file1) (readFile file2)
Пуд сахара | 253
17.2 Расширения
Расширение появляется в ответ на проблему, с которой трудно или невозможно справится в рамках стан-
дарта Haskell. Мы рассмотрим несколько наиболее часто используемых расширений. Расширения подключа-
ются с помощью специального комментария. Он помещается в начале модуля. Расширение действует только
в текущем модуле.
{-# LANGUAGE
ExtentionName1, ExtentionName2, ExtentionName3 #-}
Обратите внимание на символ решётка, обрамляющие комментарии. Слово LANGUAGE говорит компи-
лятору о том, что мы хотим воспользоваться расширениями с именами ExtentionName1, ExtentionName2,
ExtentionName3. Такой комментарий называется прагмой (pragma). Часто компилятор ghc в случае ошибки
предлагает нам подключить расширение, в котором ошибка уже не будет ошибкой, а возможностью языка.
Он говорит возможно вы имели в виду расширение XXX. Например попробуйте загрузить в интерпретатор
модуль:
module Test where
class Multi a b where
В этом случае мы увидим ошибку:
Prelude> :l Test
[1 of 1] Compiling Test
( Test. hs, interpreted )
Test. hs:3:0:
Too many parameters for class ‘Multi’
(Use -XMultiParamTypeClasses to allow multi-parameter classes)
In the class declaration for ‘Multi’
Failed, modules loaded: none.
Компилятор сообщает нам о том, что у нас слишком много параметров в классе Multi. В рамках стандар-
та Haskell можно создавать лишь классы с одним параметром. Но за сообщением мы видим подсказку, если
мы воспользуемся расширением -XMultiParamTypeClasses, то всё будет хорошо. В этом сообщении имя рас-
ширения закодировано в виде флага. Мы можем запустить ghc или ghci с этим флагом и тогда расширение
будет активировано, и модуль загрузится. Попробуем:
Prelude> :q
Leaving GHCi.
$ ghci -XMultiParamTypeClasses
Prelude> :l Test
[1 of 1] Compiling Test
( Test. hs, interpreted )
Ok, modules loaded: Test.
*Test>
Модуль загрузился! У нас есть и другая возможность подключить модуль с помощью прагмы LANGUAGE.
Имя расширения записано во флаге после символов -X. Добавим в модуль Test расширение с именем
MultiParamTypeClasses:
{-# LANGUAGE MultiParamTypeClasses #-}
module Test where
class Multi a b where
Теперь загрузим ghci в обычном режиме:
*Test> :q
Leaving GHCi.
$ ghci
Prelude> :l Test
[1 of 1] Compiling Test
( Test. hs, interpreted )
Ok, modules loaded: Test.
254 | Глава 17: Дополнительные возможности
Обобщённые алгебраические типы данных
Предположим, что мы хотим написать компилятор небольшого языка. Наш язык содержит числа и логиче-
ские значения. Мы можем складывать числа и умножать. Для логических значений определена конструкция
if-then-else. Определим тип синтаксического дерева для этого языка:
data Exp = ValTrue
| ValFalse
| If Exp Exp Exp
| Val Int
| Add Exp Exp
| Mul Exp Exp
deriving (Show)
В этом определении кроется одна проблема. Наш тип позволяет нам строить бессмысленные выражения
вроде Add ValTrue (Val 2) или If (Val 1) ValTrue (Val 22). Наш тип Val включает в себя все хорошие вы-
ражения и много плохих. Эта проблема проявится особенно ярко, если мы попытаемся определить функцию
eval, которая вычисляет значение для нашего языка. Получается, что тип этой функции:
eval :: Exp -> Either Int Bool
Для решения этой проблемы были придуманы обобщённые алгебраические типы данных (generalised
algebraic data types, GADTs). Они подключаются расширением GADTs. Помните когда-то мы говорили, что
типы можно представить в виде классов. Например определение для списка
data List a = Nil | Cons a (List a)
можно мысленно переписать так:
data List a where
Nil
:: List a
Cons :: a -> List a -> List a
Так вот в GADT определения записываются именно в таком виде. Обобщение заключается в том, что
теперь на месте произвольного параметра a мы можем писать конкретные типы. Определим тип GExp
{-# LANGUAGE GADTs #-}
data Exp a where
ValTrue
:: Exp Bool
ValFalse
:: Exp Bool
If
:: Exp Bool -> Exp a -> Exp a -> Exp a
Val
:: Int -> Exp Int
Add
:: Exp Int -> Exp Int -> Exp Int
Mul
:: Exp Int -> Exp Int -> Exp Int
Теперь у нашего типа Exp появился параметр, через который мы кодируем дополнительные ограничения
на типы операций. Теперь мы не сможем составить выражение Add ValTrue ValFalse, потому что оно не
пройдёт проверку типов.
Определим функцию eval:
eval :: Exp a -> a
eval x = case x of
ValTrue
-> True
ValFalse
-> False
If p t e
-> if eval p then eval t else eval e
Val n
-> n
Add a b
-> eval a + eval b
Mul a b
-> eval a * eval b
Если eval получит логическое значение, то будет возвращено значение типа Bool, а на значение типа Exp
Int будет возвращено целое число. Давайте убедимся в этом:
Расширения | 255
*Prelude> :l Exp
[1 of 1] Compiling Exp
( Exp. hs, interpreted )
Ok, modules loaded: Exp.
*Exp> let notE x = If x ValFalse ValTrue
*Exp> let squareE x = Mul x x
*Exp>
*Exp> eval $ squareE $ If (notE ValTrue) (Val 1) (Val 2)
4
*Exp> eval $ notE ValTrue
False
*Exp> eval $ notE $ Add (Val 1) (Val 2)
< interactive>:1:14:
Couldn’t match expected type ‘Bool’ against inferred type ‘Int’
Expected type: Exp Bool
Actual type: Exp Int
In the return type of a call of ‘Add’
In the second argument of ‘($)’, namely ‘Add (Val 1) (Val 2)’
Сначала мы определили две вспомогательные функции. Затем вычислили несколько значений. Haskell
очень часто применяется для построения компиляторов. Мы рассмотрели очень простой язык, но в более
сложном случае суть останется прежней. Дополнительный параметр позволяет нам закодировать в парамет-
ре тип функций нашего языка. Спрашивается: зачем нам дублировать вычисления в функции eval? Зачем нам
сначала кодировать выражение конструкторами, чтобы только потом получить то, что мы могли вычислить
и напрямую.
При таком подходе у нас есть полный контроль за деревом выражения, мы можем проводить дополни-
тельную оптимизацию выражений, если нам известны некоторые закономерности. Ещё функция eval может
вычислять совсем другие значения. Например она может по виду выражения составлять код на другом языке.
Возможно этот язык гораздо мощнее Haskell по вычислительным способностям, но беднее в плане вырази-
тельности, гибкости синтаксиса. Тогда мы будем в функции eval проецировать разные конструкции Haskell
в конструкции другого языка. Такие программы называются предметно-ориентированными языками програм-
мирования (domain specific languages). Мы кодируем в типе Exp некоторую область и затем надстраиваем
над типом Exp разные полезные функции. На самом последнем этапе функция eval переводит всё дерево
выражения в значение или код другого языка.
Отметим, что не так давно было предложено другое решение этой задачи. Мы можем закодировать типы
функций в классе:
class E exp where
true
:: exp Bool
false
:: exp Bool
iff
:: exp Bool -> exp a -> exp a -> exp a
val
:: Int -> exp Int
add
:: exp Int -> exp Int -> exp Int
mul
:: exp Int -> exp Int -> exp Int
Преимуществом такого подхода является модульность. Мы можем спокойно разделить выражение на две
составляющие части:
class (Log exp, Arith exp) => E exp
class Log exp where
true
:: exp Bool
false
:: exp Bool
iff
:: exp Bool -> exp a -> exp a -> exp a
class Arith exp where
val
:: Int -> exp Int
add
:: exp Int -> exp Int -> exp Int
mul
:: exp Int -> exp Int -> exp Int
Интерпретация дерева выражения в этом подходе заключается в создании экземпляра класса. Например
создадим класс-вычислитель Eval:
newtype Eval a = Eval { runEval :: a }
instance Log Eval where
256 | Глава 17: Дополнительные возможности
true
= Eval True
false
= Eval False
iff p t e = if runEval p then t else e
instance Arith Eval where
val
= Eval
add a b = Eval $ runEval a + runEval b
mul a b = Eval $ runEval a * runEval b
instance E Eval
Теперь проведём такую же сессию вычисления значений, но давайте теперь сначала определим их в тексте
программы:
notE :: Log exp => exp Bool -> exp Bool
notE x = iff x true false
squareE :: Arith exp => exp Int -> exp Int
squareE x = mul x x
e1 :: E exp => exp Int
e1 = squareE $ iff (notE true) (val 1) (val 2)
e2 :: E exp => exp Bool
e2 = notE true
Загрузим в интерпретатор:
*Exp> :r
[1 of 1] Compiling Exp
( Exp. hs, interpreted )
Ok, modules loaded: Exp.
*Exp> runEval e1
4
*Exp> runEval e2
False
Получились такие же результаты и в этом случае нам не нужно подключать никаких расширений. Теперь
создадим тип-принтер, он будет распечатывать выражение:
newtype Print a = Print { runPrint :: String }
instance Log Print where
true
= Print ”True”
false
= Print ”False”
iff p t e = Print $ ”if (” ++ runPrint p ++ ”) {”
++ runPrint t ++ ”}”
++ ”{” ++ runPrint e ++ ”}”
instance Arith Print where
val n
= Print $ show n
add a b = Print $ ”(” ++ runPrint a ++ ”)+(” ++ runPrint b ++ ”)”
mul a b = Print $ ”(” ++ runPrint a ++ ”)*(” ++ runPrint b ++ ”)”
Теперь распечатаем предыдущие выражения:
*Exp> :r
[1 of 1] Compiling Exp
( Exp. hs, interpreted )
Ok, modules loaded: Exp.
*Exp> runPrint e1
”(if (if (True) {False}{True}) {1}{2})*(if (if (True) {False}{True}) {1}{2})”
*Exp> runPrint e2
”if (True) {False}{True}”
При таком подходе нам не пришлось ничего менять в выражениях, мы просто заменили тип выражения
и оно автоматически подстроилось под нужный результат. Подробнее об этом подходе можно почитать на
сайте http://okmij.org/ftp/tagless-final/course/course.html или в статье Жака Каре (Jacques Carette), Олега Киселёва (Oleg Kiselyov) и Чунг-Че Шена (Chung-chieh Shan) Finally Tagless, Partially Evaluated.
Расширения | 257
Семейства типов
Семейства типов позволяют выражать зависимости типов. Например представим, что класс определяет
не только методы, но и типы. Причём новые типы зависят от конкретного экземпляра класса. Посмотрим,
например, на определение линейного пространства из библиотеки vector-space:
class AdditiveGroup v where
zeroV
:: v
(^+^)
:: v -> v -> v
negateV :: v -> v
class AdditiveGroup v => VectorSpace v where
type Scalar v
:: *
(*^)
:: Scalar v -> v -> v
Линейное пространство это математическая структура, объектами которой являются вектора и скаля-
ры. Для векторов определена операция сложения, а для скаляров операции сложения и умножения. Кроме
того определена операция умножения вектора на скаляр. При этом должны выполнятся определённые свой-
ства. Мы не будем подробно на них останавливаться, вкратце заметим, что эти свойства говорят о том, что
мы действительно пользуемся операциями сложения и умножения. В классе VectorSpace мы видим новую
конструкцию, объявление типа. Мы говорим, что есть производный тип, который следует из v. Далее через
двойное двоеточие мы указываем его вид. В данном случае это простой тип без параметров.
Вид (kind) это тип типа. Простой тип без параметра обозначается звёздочкой. Тип с параметром обозна-
чается как функция * -> *. Если бы тип принимал два параметра, то он обозначался бы * -> * -> *. Также
параметры могут быть не простыми типами а типами с параметрами, например тип, который обозначает
композицию типов:
newtype O f g a = O { unO :: f (g a) }
имеет вид (* -> *) -> (* -> *) -> * -> *.
Определим класс векторов на двумерной сетке и сделаем его экземпляром класса VectorSpace. Для нача-
ла создадим новый модуль с активным расширением TypeFamilies и запишем в него классы для линейного
пространства
{-# Language TypeFamilies #-}
module Point2D where
class AdditiveGroup v where
...
Теперь определим новый тип:
data V2 = V2 Int Int
deriving (Show, Eq)
Сделаем его экземпляром класса AdditiveGroup:
instance AdditiveGroup V2 where
zeroV
= V2 0 0
(V2 x y)
^+^ (V2 x’ y’)
= V2 (x+x’) (y+y’)
negateV (V2 x y)
= V2 (-x) (-y)
Мы складываем и вычитаем значения в каждом из элементов кортежа. Нейтральным элементом от-
носительно сложения будет кортеж, состоящий из двух нулей. Теперь определим экземпляр для класса
VectorSpace. Поскольку кортеж состоит из двух целых чисел, скаляр также будет целым числом:
instance VectorSpace V2 where
type Scalar V2 = Int
s *^ (V2 x y) = V2 (s*x) (s*y)
Попробуем вычислить что-нибудь в интерпретаторе:
258 | Глава 17: Дополнительные возможности
*Prelude> :l Point2D
[1 of 1] Compiling Point2D
( Point2D. hs, interpreted )
Ok, modules loaded: Point2D.
*Point2D> let v =
V2 1 2
*Point2D> v ^+^ v
V2 2 4
*Point2D> 3 *^ v ^+^ v
V2 4 8
*Point2D> negateV $ 3 *^ v ^+^ v
V2 (-4) (-8)
Семейства функций дают возможность организовывать вычисления на типах. Посмотрим на такой клас-
сический пример. Реализуем в типах числа Пеано. Нам понадобятся два типа. Один для обозначения нуля,
а другой для обозначения следующего элемента:
{-# Language TypeFamilies, EmptyDataDecls #-}
module Nat where
data Zero
data Succ a
Значения этих типов нам не понадобятся, поэтому мы воспользуемся расширением EmptyDataDecls, ко-
торое позволяет определять типы без значенеий. Значениями будут комбинации типов. Мы определим опе-
рации сложения и умножения для чисел. Для начала определим сложение:
type family Add a b :: *
type instance Add a Zero
= a
type instance Add a (Succ b)
= Succ (Add a b)
Первой строчкой мы определили семейство функций Add, у которого два параметра. Определение семей-
ства типов начинается с ключевой фразы type family. За двоеточием мы указали тип семейства. В данном
случае это простой тип без параметра. Далее следуют зависимости типов для семейства Add. Зависимости
типов начинаются с ключевой фразы type instance. В аргументах мы словно пользуемся сопоставлением с
образцом, но на этот раз на типах. Первое уравнение:
type instance Add a Zero
= a
Говорит о том, что если второй аргумент имеет тип ноль, то мы вернём первый аргумент. Совсем как в
обычном функциональном определении сложения для натуральных чисел Пеано. а во втором уравнении мы
составляем рекурсивное уравнение:
type instance Add a (Succ b)
= Succ (Add a b)
Точно также мы можем определить и умножение:
type family Mul a b :: *
type instance Mul a Zero
= Zero
type instance Mul a (Succ b)
= Add a (Mul a b)
При этом нам придётся подключить ещё одно расширение UndecidableInstances, поскольку во втором
уравнении мы подставили одно семейство типов в другое. Этот флаг часто используется в сочетании с рас-
ширением TypeFamilies. Семейства типов фактически позволяют нам определять функции на типах. Это
ведёт к тому, что алгоритм вывода типов становится неопределённым. Если типы правильные, то компиля-
тор сможет это установить, но если они окажутся неправильными, может возникнуть такая ситуация, что
компилятор зациклится и будет бесконечно долго искать соответствие одного типа другому. Теперь про-
верим результаты. Для этого мы создадим специальный класс, который будет переводить значения-типы в
обычные целочисленные значения:
class Nat a where
toInt :: a -> Int
instance Nat Zero where
toInt = const 0
instance Nat a => Nat (Succ a) where
toInt x = 1 + toInt (proxy x)
proxy :: f a -> a
proxy = undefined
Расширения | 259
Мы определили для каждого значения-типа экземпляр класса Nat, в котором мы можем переводить типы
в числа. Функция proxy позволяет нам извлечь значение из типа-конструктора Succ, так мы поясняем ком-
пилятору тип значения. При этом мы нигде не пользуемся значениями типов Zero и Succ, ведь у этих типов
нет значений. Поэтому в экземпляре для Zero мы пользуемся постоянной функцией const.
Теперь посмотрим, что у нас получилось:
Prelude> :l Nat
*Nat> let x = undefined :: (Mul (Succ (Succ (Succ Zero))) (Succ (Succ Zero)))
*Nat> toInt x
6
Видно, что с помощью класса Nat мы можем извлечь значение, закодированное в типе. Зачем нам эти
странные типы-значения? Мы можем использовать их в двух случаях. Мы можем кодировать значения в типе
или проводить более тонкую проверку типов.
Помните когда-то мы определяли функции для численного интегрирования. Там точность метода была
жёстко задана в тексте программы:
dt :: Fractional a => a
dt = 1e-3
-- метод Эйлера
int :: Fractional a => a -> [a] -> [a]
int x0 ~(f:fs) = x0 : int (x0 + dt * f) fs
В этом примере мы можем создать специальный тип потоков, у которых шаг дискретизации будет зако-
дирован в типе.
data Stream n a = a :& Stream n a
Параметр n кодирует точность. Теперь мы можем извлекать точность из типа:
dt :: (Nat n, Fractional a) => Stream n a -> a
dt xs = 1 / (fromIntegral $ toInt $ proxy xs)
where proxy :: Stream n a -> n
proxy = undefined
int :: (Nat n, Fractional a) => a -> Stream n a -> Stream n a
int x0 ~(f:& fs) = x0 :& int (x0 + dt fs * f) fs
Теперь посмотрим как мы можем сделать проверку типов более тщательной. Представим, что у нас есть
тип матриц. Известно, что сложение определено только для матриц одинаковой длины, а для умножения
матриц число столбцов одной матрицы должно совпадать с числом колонок другой матрицы. Мы можем
отразить все эти зависимости в целочисленных типах:
data Mat n m a = ...
instance Num a => AdditiveGroup (Mat n m a) where
a ^+^ b
= ...
zeroV
= ...
negateV a
= ...
mul :: Num a => Mat n m a -> Mat m k a -> Mat n k a
При таких определениях мы не сможем сложить матрицы разных размеров. Причём ошибка будет вычис-
лена до выполнения программы. Это освобождает от проверки границ внутри алгоритма умножения матриц.
Если алгоритм запустился, то мы знаем, что размеры аргументов соответствуют.
Скоро в ghc появится поддержка чисел на уровне типов. Это будет специальное расширение
TypeLevelNats, при включении которого можно будет пользоваться численными литералами в типах,
также будут определены операции-семейства типов на численных типах с привычными именами +, *.
Классы с несколькими типами
Рассмотрим несколько полезных расширений, относящихся к определению классов и экземпляров клас-
сов. Расширение MultiParamTypeClasses позволяет объявлять классы с несколькими аргументами. Например
взгляните на такой класс:
class Iso a b where
to
:: a -> b
from
:: b -> a
Так мы можем определить изоморфизм между типами a и b
260 | Глава 17: Дополнительные возможности
Экземпляры классов для синонимов
Расширение TypeSynonymInstances позволяет определять экземпляры для синонимов типов. Мы уже
пользовались этим расширением, когда определяли рекурсивные типы через тип Fix, там нам нужно бы-
ло определить экземпляр Num для синонима Nat:
type Nat = Fix N
instance Num Nat where
В рамках стандарта все суперклассы должны быть простыми. Все они имеют вид T a. Если мы хотим хотим
использовать суперклассы с составными типами, нам придётся подключить расширение FlexibleContexts.
Этим расширением мы пользовались, когда определяли экземпляр Show для Fix:
instance Show (f (Fix f)) => Show (Fix f) where
show x = ”(” ++ show (unFix x) ++ ”)”
Функциональные зависимости
Класс можно представить как множество типов, для которых определены данные операции. С появлением
расширения MultiParamTypeClasses мы можем определять операции класса для нескольких типов. Так наше
множество классов превращается в отношение. Наш класс связывает несколько типов между собой. Если из
одной компоненты отношения однозначно следует другая, такое отношение принято называть функцией.
Например обычную функцию одного аргумента можно представить как множество пар (x, f x). Для того
чтобы множество таких пар было функцией необходимо, чтобы выполнялось свойство:
forall x, y.
x == y => f x == f y
Для одинаковых входов мы получаем одинаковые выходы. С функциональными зависимостями мы мо-
жем ввести такое ограничение на классы с несколькими аргументами. Рассмотрим практический пример.
Библиотека Boolean определяет обобщённые логические значения,
class Boolean b where
true, false :: b
notB
:: b -> b
(&&*), (||*) :: b -> b -> b
Логические значения определены в терминах простейших операций, теперь мы можем обобщить связку
if-then-else и классы Eq и Ord:
class Boolean bool => IfB bool a | a -> bool where
ifB :: bool -> a -> a -> a
class Boolean bool => EqB bool a | a -> bool where
(==*), (/=*) :: a -> a -> bool
class Boolean bool => OrdB bool a | a -> bool where
(<*), (>=*), (>*), (<=*) :: a -> a -> bool
Каждый из классов определён на двух типах. Один из них играет роль обычных логических значений, а
второй тип~– это такой же параметр как и в обычных классах из модуля Prelude. В этих определениях нам
встретилась новая конструкция: за переменными класса через разделитель “или” следует что-то похожее на
тип функции. В этом типе мы говорим, что из типа a следует тип bool, или тип a однозначно определяет тип
bool. Эта информация помогает компилятору выводить типы. Если он встретит в тексте выражение v = a <*
b и тип одного из аргументов a или b известен, то тип v будет определён по зависимости.
Зачем нам может понадобиться такая система классов? Например, с ней мы можем определить экземпляр
Boolean для предикатов или функций вида a -> Bool и затем определить три остальных класса для функций
вида a -> b. Мы сравниваем не отдельные логические значения, а функции которые возвращают логические
значения. Так в выражении ifB c t e функция c играет роль “маски”, если на данном значении функция c
вернт истину, то мы воспользуемся значением функции t, иначе возьмём результат из функции e. Например
так мы можем определить функцию модуля:
*Boolean> let absolute = ifB (> 0) id negate
*Boolean> map absolute [-10 .. 10]
[10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10]
Расширения | 261
Мы можем указать несколько зависимостей (через запятую) или зависимость от нескольких типов (через
пробел, слева от стрелки):
class C a b c | a -> b, b c -> a where
...
Отметим, что многие функциональные зависимости можно выразить через семейства типов. Пример из
библиотеки Boolean можно было бы записать так:
class Boolean a where
true, false
:: a
(&&*), (||*)
:: a -> a -> a
class Boolean (B a) => IfB a where
type B a :: *
ifB :: (B a) -> a -> a -> a
class IfB a => EqB a where
(==*), (/=*) :: a -> a -> B a
class IfB a => OrdB a where
(<*), (>*), (>=*), (<=*) :: a -> a -> B a
Исторически первыми в Haskell появились функциональные зависимости. Поэтому некоторые пакеты на
Hackage определены в разных вариантах. Семейства типов используются более охотно.
Ограничение мономорфизма
В Haskell мы можем не писать типы функций. Они будут выведены компилятором автоматически. Но
написание типов функций считается признаком хорошего стиля. Поскольку по типам можно догадаться чем
функция занимается. Но есть в правиле вывода типов одно исключение. Если мы напишем:
f = show
То компилятор сообщит нам об ошибке. Это выражение приводит к ошибке, которая вызвана ограничени-
ем мономорфизма. Мы говорили о нём в главе о типах. Часто в сильно обобщённых библиотеках, с больши-
ми зависимостями в типах выписывать типы крайне неудобно. Например в библиотеке создания парсеров
Parsec. С этим ограничением приходится писать огромные объявления типов для крохотных выражений.
Что-то вроде:
fun :: (Stream s m t, Show t) => ParsecT s u m a -> ParsecT s u m [a]
fun = g . h (q x) y
И так для любого выражения. В этом случае лучше просто выключить ограничение, добавив в начало
файла:
{-# Language NoMonomorphismRestriction #-}
Полиморфизм высших порядков
Когда мы говорили об ST нам встретилась функция с необычным типом:
runST :: (forall s. ST s a) -> a
Слово forall обозначает для любых. Любой полиморфный тип в Haskell подразумевает, что он определён
для любых типов. Например, когда мы пишем:
reverse :: [a] -> [a]
map
:: (a -> b) -> [a] -> [b]
На самом деле мы пишем:
reverse :: forall a. [a] -> [a]
map
:: forall a b. (a -> b) -> [a] -> [b]
262 | Глава 17: Дополнительные возможности
По названию слова forall может показаться, что оно несёт в себе много свободы. Оно говорит о том, что
функция определена для любых типов. Но если присмотреться, то эта свобода оказывается жёстким огра-
ничением. “Для любых” означает, что мы не можем делать никаких предположений о внутренней природе
значения. Мы не можем разбирать такие значения на составляющие части. Мы можем только подставлять
их в новые полиморфные функции (как в map), отбрасывать (как const) или перекладывать из одного ме-
ста в другое (как в swap или reverse). Мы можем немного смягчить ограничение, если укажем в контексте
функции какие классы определены для значений данного типа.
Все стандартные полиморфные типы имеют вид:
fun :: forall a b .. z. Expr(a, b, ... , z)
Причём Expr не содержит forall, а только стрелки и применение новых типов к параметрам. Такой тип
называют полиморфным типом первого порядка (rank). Если forall стоит справа от стрелки, то его можно
вынести из выражения, например, следующие выражения эквивалентны:
fun :: forall a.
a -> (forall b. b -> b)
fun :: forall a b. a -> (b -> b)
Так мы можем привести не стандартный тип к стандартному. Если же forall встречается слева от стрел-
ки, как в функции runST, то его уже нельзя вынести. Это приводит к повышению порядка полиморфизма.
Порядок полиморфизма определяется как самый максимум среди всех подвыражений, что стоят слева от
стрелки плюс один. Так в типе
runST :: (forall s. ST s a) -> a
Слева от стрелки стоит тип первого порядка, прибавив единицу, получим порядок для всего выражения.
Если вдруг нам захочется воспользоваться такими типами, мы можем включить одно из расширений:
{-# Language Rank2Types #-}
{-# Language RankNTypes #-}
В случае рангов произвольного порядка алгоритм вывода типов может не завершиться. В этом случае нам
придётся помогать компилятору расставляя типы сложных функций вручную.
Лексически связанные типы
Мы уже привыкли к тому, что когда мы пишем
swap :: (a, b) -> (b, a)
компилятор понимает, что a и b указывают на один и тот же тип слева и справа от стрелки. При этом типы
a и b не обязательно разные. Иногда нам хочется расширить действие контекста функции и распространить
его на всё тело функции. Например ранее в этой главе, когда мы имитировали числа через типы, для того
чтобы извлечь число из типа, мы пользовались трюком с функцией proxy:
instance Nat a => Nat (Succ a) where
toInt x = 1 + toInt (proxy x)
proxy :: f a -> a
proxy = undefined
Единственное назначение функции proxy~– это передача информации о типе. Было бы гораздо удобнее
написать:
instance Nat a => Nat (Succ a) where
toInt x = 1 + toInt (undefined :: a)
Проблема в том, что по умолчанию любой полиморфный тип в Haskell имеет первый ранг, компилятор
читает нашу запись как (x :: forall a. a), и получается, что мы говорим: x имеет любой тип, какой
захочешь! Не очень полезная информация. Компилятор заблудился и спрашивает у нас: “куда пойти?” А
мы ему: “да куда захочешь”. Как раз для таких случаев существует расширение ScopedTypeVariables. Оно
связывает тип, объявленный в заголовке класса/функции с типами, которые встречаются в теле функции.
В случае функций есть одно отличие от случая с классами. Если мы хотим расширить действие переменной
из объявления типа функции, необходимо упомянуть её в слове forall в стандартном положении (как для
типа первого порядка). У нас был ещё один пример с proxy:
Расширения | 263
dt :: (Nat n, Fractional a) => Stream n a -> a
dt xs = 1 / (fromIntegral $ toInt $ proxy xs)
where proxy :: Stream n a -> n
proxy = undefined
В этом случае мы пишем:
{-# Language ScopedTypeVariables #-}
...
dt :: forall n. (Nat n, Fractional a) => Stream n a -> a
dt xs = 1 / (fromIntegral $ toInt (undefined :: n))
Обратите внимение на появление forall в определении типа. Попробуйте скомпилировать пример без
него или переместите его в другое место. Во многих случаях применения этого рсширения можно избежать
с помощью стандартной функции asTypeOf, посмотрим на определение из Prelude:
asTypeOf :: a -> a -> a
asTypeOf x y = x
Фактически это функция const, оба типа которой одинаковы. Она часто используется в инфиксной форме
для фиксации типа первого аргумента:
q = f $ x ‘asTypeOf‘ var
Получается очень наглядно, словно это предложение обычного языка.
И другие удобства и украшения
Стоит упомянуть несколько расширений. Они лёгкие для понимания, в основном служат украшению
записи или для сокращения рутинного кода.
Директива deriving может использоваться только с несколькими стандартными классами, но если мы
определили тип-обёртку через newtype или просто синоним, то мы можем очень просто определить новый
тип экземпляром любого класса, который доступен завёрнутому типу. Как раз для этого существует расши-
рение GeneralizedNewtypeDeriving:
newtype MyDouble = MyDouble Double
deriving (Show, Eq, Enum, Ord, Num, Fractional, Floating)
Мы говорили о том, что обычные числа в Haskell перегружены, иногда возникает необходимость в пе-
регруженных строках, как раз для этого существует расширение OverloadedStrings. При этом за обычной
записью строк может скрываться любой тип из класса:
class IsString a where
fromString :: String -> a
Расширение TypeOperators позволяет определять инфиксные имена не только для конструкторов типов,
но и для самих типов, синонимов типов и даже классов:
data a :+: b = Left a | Right b
17.3 Краткое содержание
В этой главе мы затронули малую часть возможностей, которые предоставляются системой ghc. Haskell
является полигоном для испытания самых разнообразных идей. Это экспериментальный язык. Но в практиче-
ских целях в 1998 году был зафиксирован стандарт языка, его обычно называют Haskell98. Любое расшире-
ние подключается с помощью специальной прагмы Language. Новый стандарт Haskell Prime включит в себя
наиболее устоявшиеся расширения. Также мы рассмотрели несколько полезных классов и синтаксических
конструкций, которые, возможно, облегчают написание программ.
17.4 Упражнения
Это была справочная глава, присмотритесь к рассмотренным возможностям и подумайте какие нужны
вам, а какие нет. Возможно вы вовсе не будете ими пользоваться, но некоторые из них могут встретиться
вам в чужом коде или в библиотеках.
264 | Глава 17: Дополнительные возможности
Глава 18
Средства разработки
В этой главе мы познакомимся с основными средствами разработки больших программ. Мы научимся
устанавливать и создавать библиотеки, писать документацию.
18.1 Пакеты
В Haskell есть ещё один уровень организации данных, мы можем объединять модули в пакеты (package).
Также как и модули пакеты могут зависеть от других пакетов, если они пользуются модулями их этих па-
кетов. Одним пакетом мы уже пользовались и довольно часто, это пакет base, который содержит все стан-
дартные модули, например такие как Prelude, Control.Applicative или Data.Function. Для создания и
установки пакетов существует приложение cabal. Оно определяет протокол организации и распростране-
ния модулей Haskell.
Создание пакетов
Предположим, что мы написали программу, которая состоит из нескольких модулей. Пусть все модули
хранятся в директории с именем src. Для того чтобы превратить набор модулей в пакет, нам необходимо
поместить в одну директорию с src два файла:
• имяПакета. cabal – файл с описанием пакета.
• Setup. hs – файл с инструкциями по установке пакета
.cabal
Посмотрим на простейший файл с описанием библиотеки, этот файл находится в одной директории с
той директорией, в которой содержатся все модули приложения и имеет расширение . cabal:
Name
: Foo
Version
: 1.0
Library
build-depends
: base
exposed-modules
: Foo
Сначала идут свойства пакета. Общий формат определения свойства:
ИмяСвойства : Значение
В примере мы указали имя пакета Foo, и версию 1.0. После того, как мы указали все свойства, мы опре-
деляем будет наш пакет библиотекой или исполняемой программой или возможно он будет и тем и другим.
Если пакет будет библиотекой, то мы помещаем за набором атрибутов слово Library, а если это исполняе-
мая программа, то мы помещаем слово Executable, после мы пишем описание модулей пакета, зависимости
от других пакетов, какие модули будут видны пользователю. Формат составления описаний в этой части та-
кой же как и в самом начале файла. Сначала идёт зарезервированное слово-атрибут, затем через двоеточие
следует значение. Обратите внимание на отступы за словом Library, они обязательны и сделаны с помощью
пробелов, cabal не воспринимает табуляцию.
Файл . cabal может содержать комментарии, они делаются также как и в Haskell, закомментированная
строка начинается с двойного тире.
| 265
Setup.hs
Файл Setup. hs содержит информацию о том как устанавливается библиотека. При установке могут ис-
пользоваться другие программы и библиотеки. Пока мы будем пользоваться простейшим случаем:
import Distribution.Simple
main = defaultMain
Этот файл позволяет нам создавать библиотеки и приложения, которые созданы только с помощью
Haskell. Это не так уж и мало!
Создаём библиотеки
Типичный файл . cabal для библиотеки выглядит так:
Name:
pinocchio
Version:
1.1. 1
Cabal-Version:
>= 1.2
License:
BSD3
License-File:
LICENSE
Author:
Mister Geppetto
Homepage:
http://pinocchio. sourceforge. net/
Category:
AI
Synopsis:
Tools for creation of woodcrafted robots
Build-Type:
Simple
Library
Build-Depends: base
Hs-Source-Dirs: src/
Exposed-modules:
Wood.Robot.Act, Wood.Robot.Percept, Wood.Robot.Think
Other-Modules:
Wood.Robot.Internals
Этим файлом мы описали библиотеку с именем pinocchio, версия 1.1.1, она использует версию cabal
не ниже 1.2. Библиотека выпущена под лицензией BSD3. Файл с лицензией находится в текущей директо-
рии под именем LICENSE. Автор библиотеки Mister Geppetto. Подробнее узнать о библиотеке можно на её
домашней странице http://pinocchio. sourceforge. net/. Атрибут Category указывает на широкую отрасль
знаний, к которой принадлежит наша библиотека. В данном случае мы описываем библиотеку для построе-
ния роботов из дерева, об этом мы пишем в атрибуте Synopsis (краткое описание), поэтому наша библиоте-
ка принадлежит к категории искусственный интеллект или сокращённо AI. Последний атрибут Build-Type
указывает на тип сборки пакета. Мы будем пользоваться значением Simple, который соответствует сборке с
помощью простейшего файла Setup. hs, который мы рассмотрели в предыдущем разделе.
После описания пакета, идёт слово Library, ведь мы создаём библиотеку. Далее в атрибуте Build-
Depends
мы указываем зависимости для нашего пакета. Здесь мы перечисляем все пакеты, которые мы используем в
своей библиотеке. В данном случае мы пользовались лишь стандартной библиотекой base. В атрибуте hs-
source-dirs мы указываем, где искать директорию с исходным кодом библиотеки. Затем мы указываем три
внешних модуля, они будут доступны пользователю после установки библиотеки (атрибут Exposed-Modules),
и внутренние скрытые модули (атрибут Other-Modules).
Создаём исполняемые программы
Типичный файл . cabal для исполняемой программы:
Name:
micro
Version:
0.0
Cabal-Version:
>= 1.2
License:
BSD3
Author:
Tony Reeds
Synopsis:
Small programming language
Build-Type:
Simple
Executable micro
266 | Глава 18: Средства разработки
Build-Depends:
base, parsec
Main-Is:
Main. hs
Hs-Source-Dirs: micro
Executable micro-repl
Main-Is:
Main. hs
Build-Depends:
base, parsec
Hs-Source-Dirs: repl
Other-Modules:
Utils
В этом файле мы описываем две программы. Компилятор языка и интерпретатор языка micro. Если срав-
нить этот файл с файлом для библиотеки, то мы заметим лишь один новый атрибут. Это Main-Is. Он указыва-
ет в каком модуле содержится функция main. После установки этого пакета будут созданы два исполняемых
файла. С именами micro и micro-repl.
Установка пакета
Пакеты устанавливаются с помощью команды install. Необходимо перейти в директорию пакета, ту,
в которой находятся два служебных файла (. cabal и Setup. hs) и директория с исходниками, и запустить
команду:
cabal install
Если мы нигде не ошиблись в описании пакета, не перепутали табуляцию с пробелами при отступах, или
указали без ошибок все зависимости, то пакет успешно установится. Если это библиотека, то мы сможем
подключать экспортируемые ей модули в любом другом модуле, просто указав их в директиве import. При
этом нам уже не важно, где находятся модули библиотеки. Мы имеем возможность импортировать их из
любого модуля. Если же пакет был исполняемой программой, будут созданы бинарные файлы программ. В
конце cabal сообщит нам куда он их положил.
Иногда возникают проблемы с пакетами, которые генерируют исполняемые файлы, а затем с их помощью
устанавливают другие пакеты. Проблема возникает из-за того, что cabal может положить бинарный файл в
директорию, которая не видна следующим программам, которые хотят продолжить установку. В этом слу-
чае необходимо либо переложить созданные бинарные файлы в директорию, которая будет им видна, или
добавить директорию с новыми бинарными файлами в PATH (под UNIX, Linux). Переменная операционной
системы PATH содержит список всех путей, в которых система ищет исполняемые программы, если путь не
указан явно. Посмотреть содержание PATH можно, вызвав:
$ echo $PATH
Появится строка директорий, которые записаны через двоеточие. Для того чтобы добавить директорию
/data/dir в PATH необходимо написать:
$ PATH=$PATH:/data/dir
Эта команда добавит директорию в PATH для текущей сессии в терминале, если мы хотим записать её
насовсем, мы добавим эту команду в специальный скрытый файл . bashrc, он находится в домашней дирек-
тории пользователя. Под Windows добавить директорию в PATH можно с помощью графического интерфейса.
Кликните правой кнопкой мыши на иконку My Computer (Мой Компьютер), в появившемся меню выбери-
те вкладку Properties (Свойства). Появится окно System Properties (Свойства системы), в нём выберите
вкладку Advanced и там нажмите на кнопку Environment variables (Переменные среды). И в этом окне будет
строка Path, её мы и хотим отредактировать, добавив необходимые нам пути.
Давайте потренируемся и создадим библиотеку и исполняемую программу. Создадим библиотеку, кото-
рая выводит на экран Hello World. Создадим директорию hello, и в ней создадим директорию src. Эта ди-
ректория будет содержать исходный код. Главный модуль библиотеки экспортирует функцию приветствия:
module Hello where
import Utility.Hello(hello)
import Utility.World(world)
helloWorld = hello ++ ”, ” ++ world ++ ”!”
Главный модуль программы Main. hs определяет функцию main, которая выводит текст приветствия на
экран:
Пакеты | 267
module Main where
import Hello
main = print helloWorld
У нас будет два внутренних модуля, каждый из которых определяет синоним для одного слова. Мы по-
местим их в папку Utility. Это модуль Utility.Hello
module Utility.Hello where
hello = ”Hello”
И модуль Utility.World:
module Utility.World where
world = ”World”
Исходники готовы, теперь приступим к описанию пакета. Создадим в корневой директории пакета файл
hello. cabal.
Name:
hello
Version:
1.0
Cabal-Version:
>= 1.2
License:
BSD3
Author:
Anton
Synopsis:
Little example of cabal usage
Category:
Example
Build-Type:
Simple
Library
Build-Depends: base == 4.*
Hs-Source-Dirs: src/
Exposed-modules:
Hello
Other-Modules:
Utility.Hello
Utility.World
Executable hello
Build-Depends: base == 4.*
Main-Is: Main. hs
Hs-Source-Dirs: src/
В этом файле мы описали библиотеку и программу. В строке base == 4.* мы указали версию пакета base.
Запись 4.* означает любая версия, которая начинается с четвёрки. Осталось только поместить в корневую
директорию пакета файл Setup. hs.
import Distribution.Simple
main = defaultMain
Теперь мы можем переключиться на корневую директорию пакета и установить пакет:
anton@anton-desktop:~/haskell-notes/code/ch-17/hello$ cabal install
Resolving dependencies...
Configuring hello-1.0...
Preprocessing library hello-1.0...
Preprocessing executables for hello-1.0...
Building hello-1.0...
[1 of 3] Compiling Utility.World
( src/Utility/World. hs, dist/build/Utility/World. o )
[2 of 3] Compiling Utility.Hello
( src/Utility/Hello. hs, dist/build/Utility/Hello. o )
[3 of 3] Compiling Hello
( src/Hello. hs, dist/build/Hello. o )
Registering hello-1.0...
[1 of 4] Compiling Utility.World
( src/Utility/World. hs, dist/build/hello/hello-tmp/Utility/World. o )
[2 of 4] Compiling Utility.Hello
( src/Utility/Hello. hs, dist/build/hello/hello-tmp/Utility/Hello. o )
[3 of 4] Compiling Hello
( src/Hello. hs, dist/build/hello/hello-tmp/Hello. o )
[4 of 4] Compiling Main
( src/Main. hs, dist/build/hello/hello-tmp/Main. o )
Linking dist/build/hello/hello ...
Installing library in /home/anton/. cabal/lib/hello-1.0/ghc-7.4. 1
Installing executable(s) in /home/anton/. cabal/bin
Registering hello-1.0...
268 | Глава 18: Средства разработки
Мы видим сообщения о процессе установки. После установки в текущей директории пакета появилась
директория dist, в которую были помещены скомпилированные файлы библиотеки. В последних строках
cabal сообщил нам о том, что он установил библиотеку в директорию:
Installing library in /home/anton/. cabal/lib/hello-1.0/ghc-7.4. 1
и исполняемый файл в директорию:
Installing executable(s) in /home/anton/. cabal/bin
С помощью различных флагов мы можем контролировать процесс установки пакета. Назначать дополни-
тельные директории, указывать куда поместить скомпилированные файлы. Подробно об этом можно почи-
тать в справке, выполнив в командной строке одну из команд:
cabal --help
cabal install --help
Если у вас не получилось сразу установить пакет не отчаивайтесь и почитайте сообщения об ошибках
из cabal, он информативно жалуется о забытых зависимостях и неспособности правильно прочитать файл с
описанием пакета.
Удаление библиотеки
Установленные с помощью cabal файлы видны из любого модуля. Имена модулей регистрируются гло-
бально. Если нам захочется установить библиотеку с уже зарегистрированным именем, произойдёт хаос.
Возможно прежняя библиотека нам уже не нужна. Как нам удалить её? Посмотрим на решение для компи-
лятора ghc. Мы можем посмотреть список всех зарегистрированных в ghc библиотек с помощью команды:
$ ghc-pkg list
Cabal-1.8.0.6
array-0.3.0.1
base-4.2.0.2
...
...
Появится длинный список с именами библиотек. Для удаления одной из них мы можем выполнить ко-
манду:
ghc-pkg unregister имя-библиотеки
Например так мы можем удалить только что установленную библиотеку hello:
$ ghc-pkg unregister hello
Репозиторий пакетов Hackage
Если у нас подключен интернет, то мы можем воспользоваться наследием сообщества Haskell и уста-
новить пакет с Hackage. Там расположено много-много-много пакетов. Любой разработчик Haskell может
добавить свой пакет на Hackage. Посмотреть на пакеты можно на сайте этого репозитория:
http://hackage.haskell.org
Если для вашей задачи необходимо выполнить какую-нибудь довольно общую задачу, например написать
тип красно-чёрных деревьев или построить парсер или возможно вам нужен веб-сервер, поищите этот пакет
на Hackage, он там наверняка окажется, ещё и в нескольких вариантах.
Для установки пакета с Hackage нужно просто написать
cabal install имя-пакета
Возможно нам нужен очень новый пакет, который был только что залит автором на Hackage. Тогда вы-
полняем:
cabal update
Происходит обновление данных о загруженных на Hackage. Что хорошо, вы можете загрузить исходники
из Hackage, например у вас никак не получается написать пакет, который устанавливался бы без ошибок.
Просто загрузим исходники какого-нибудь пакета из Hackage и посмотрим на пример рабочего пакета.
Пакеты | 269
Дополнительные атрибуты пакета
В файле . cabal также часто указывают такие атрибуты как:
Maintainer Поле содержит адрес электронной почты технической поддержки
Stability Статус версии библиотеки (стабильная, экспериментальная, нестабильная).
Description Подробное описание назначения пакета. Оно помещается на главную страницу пакета в доку-
ментации.
Extra-Source-Files В этом поле можно через пробел указать дополнительные файлы, включаемые в пакет.
Это могут быть примеры использования, описание в формате PDF или хроника изменений и другие
служебные файлы.
License-file Путь к файлу с лицензией.
ghc-options Флаги компиляции для GHC. Если в нашей библиотеке мы активно пользуемся продвинуты-
ми прагмами оптимизации, необходимо сообщить об этом компилятору пользователя. Например, мы
можем написать в этом атрибуте -O или -O2.
Установка библиотек для профилирования
Помните когда-то мы занимались профилированием? Это было в главе, посвящённой устройству GHC.
Мы включали флаг -prof и всё шло гладко. Там мы профилировали код, в котором участвовали лишь
стандартные библиотеки из пакета base, такие как Prelude. Но если мы попробуем профилировать код с
какими-нибудь другими библиотеками, установленными с помощью cabal, GHC возмутится и скажет, что
для профилирования не хватает специальной версии библиотеки имярек. Для того чтобы иметь возможность
профилировать код, в котором участвуют другие библиотеки необходимо установить их с возможностью
профилирования. Это делается при установке с помощью специального флага –“enable-library-profiling
или –“enable-executable-profiling (если мы устанавливаем исполняемое приложение):
$ cabal install имярек --reinstall --enable-library-profiling
Библиотека будет установлена в двух экземплярах: для исполнения и профилирования. Возможно биб-
лиотека имярек потребует переустановки некоторых библиотек, от которых она зависит. Повторяем эту про-
цедуру для этих библиотек и возвращаемся к исходной библиотеке. К сожалению, избежать переустановки
библиотек нельзя. Но мы можем сделать так, чтобы все будущие библиотеки устанавливались с возмож-
ностью профилирования. Для этого необходимо отредактировать файл настроек программы cabal. Ищем
директори, в которой cabal хранит свои служебные файлы. Если вы пользуетесь Linux, то скорее всего это
скрытая директория . cabal в вашей домашней директории. Если вы пользуетесь Windows, положение ди-
ректории зависит от версии системы. Но ничего, узнать её положение можно, выполнив в ghci
Prelude> :m System.Directory
Prelude System.Directory> getAppUserDataDirectory ”cabal”
Присмотритесь к этой директории в ней вы найдёте много полезных данных. В ней находятся испол-
няемые программы, скомпилированные библиотеки, а также исходный код библиотек. В этой директории
находится и файл config с настройками для cabal. Ищем строчку с полем library-profiling: False. Меня-
ем значение на True и раскомментируем эту строчку, если она закомментирована. После этого cabal install
будет устанавливать библиотеки для профилирования. На первых порах это вызовет массу неудобств из-за
необходимости переустановки многих библиотек.
18.2 Создание документации с помощью Haddock
Если мы зайдём на Hackage, то там мы увидим длинный список пакетов, отсортированных по категориям.
К какой категории какой пакет относится мы указываем в . cabal-файле в атрибуте Category. Далее рядом с
именем пакета мы видим краткое описание, оно берётся из атрибута Synopsis. Если мы зайдём на страницу
одного из пакетов, то там мы увидим страницу в таком же формате, что и документация к стандартным
библиотекам. Мы видим описание пакета и ниже иерархию модулей. Мы можем зайти в заинтересовавший
нас модуль и посмотреть на объявленные функции, типы и классы. В самом низу страницы находится ссылка
к исходникам пакета.
“Домашняя страница” пакета была создана с помощью приложения Haddock. Оно генерирует документа-
цию в формате html по специальным комментариям. Haddock встроен в cabal, например мы можем сделать
документацию к нашему пакету hello. Для этого нужно переключиться на корневую директорию пакета и
вызвать:
270 | Глава 18: Средства разработки
cabal haddock
После этого в директории dist появится директория doc, в которой внутри директории html находится
созданная документация. Мы можем открыть файл index. html и там мы увидим “иерархию нашего” модуля.
В модуле пока нет ни одной функции, так получилось потому, что Haddock помещает в документацию лишь
те функции, у которых есть объявление типа. Если мы добавим в модуле Hello. hs: к единственной функции
объявление типа:
helloWorld :: String
helloWorld = hello ++ ”, ” ++ world ++ ”!”
И теперь перезапустим haddock. То мы увидим, что в модуле Hello появилась одна запись.
Комментарии к определениям
Прокомментировать любое определение можно с помощью комментария следующего вида:
-- | Here is the comment
helloWorld :: String
helloWorld = hello ++ ”, ” ++ world ++ ”!”
Обратите внимание на значок “или”, сразу после комментариев. Этот комментарий будет включен в
документацию. Также можно писать комментарии после определения для этого к комментарию добавляется
значок степени:
helloWorld :: String
helloWorld = hello ++ ”, ” ++ world ++ ”!”
-- ^ Here is the comment
К сожалению на момент написания этих строк Haddock может включать в документацию лишь латинские
символы. Комментарии могут простираться несколько строк:
-- | Here is the type.
-- It contains three elements.
-- That’s it.
data T = A | B | C
Также они могут быть блочными:
{-|
Here is the type.
It contains three elements.
That’s it.
-}
data T = A | B | C
Мы можем комментировать не только определение целиком, но и отдельные части. Например так мы
можем пояснить отдельные аргументы у функции:
add :: Num a => a
-- ^ The first argument
-> a
-- ^ The second argument
-> a
-- ^ The return value
Методы класса и отдельные конструкторы типа можно комментировать как обычные функции:
data T
-- | constructor A
= A
-- | constructor B
| B
-- | constructor C
| C
Или так:
Создание документации с помощью Haddock | 271
data T = A
-- ^ constructor A
| B
-- ^ constructor B
| C
-- ^ and so on
Комментарии к классу:
-- | С-class
class С a where
-- | f-function
f :: a -> a
-- | g-function
g :: a -> a
Комментарии к модулю
Комментарии к модулю помещаются перед объявлением имени модуля. Эта информация попадёт в самое
начало страницы документации:
-- | Little example
module Hello where
Структура страницы документации
Если модуль большой, то его бывает удобно разделить на части, словно разделы в главе книги. Определе-
ния группируются по функциональности и помещаются в разные разделы или даже подразделы. Структура
документации определяется с помощью специальных комментариев в экспорте модуля. Посмотрим на при-
мер:
-- | Little example
module Hello(
-- * Introduction
-- | Here is the little example to show you
-- how to make docs with Haddock
-- * Types
-- | The types.
T(.. ),
-- * Classes
-- | The classes.
C(.. ),
-- * Functions
helloWorld
-- ** Subfunctions1
-- ** Subfunctions2
) where
...
Комментарии со звёздочкой создают раздел, а с двумя звёздочками – подраздел. Те определения, ко-
торые экспортируются за комментариями со звёздочкой попадут в один раздел или подраздел. Если сразу
за комментарием со звёздочкой идёт комментарий со знаком “или”, то он будет помещён в самое начало
раздела. В нём мы можем пояснить по какому принципу группируются определения в данном разделе.
Разметка
С помощью специальных символов можно выделять различные элементы текста, например, ссылки, куски
кода, названия определений или модулей. Haddock установит необходимые ссылки и выделит элемент в
документации.
При этом символы \, ’, ‘, ”, @, < являются специальными, если вы хотите воспользоваться одним из
специальных символов в тексте необходимо написать перед ним обратный слэш \. Также символы для обо-
значения комментариев *, |, ^ и > являются специальными, если они расположены в самом начале строки.
272 | Глава 18: Средства разработки
Параграфы
Параграфы определяются по пустой сроке в комментарии. Так например мы можем разбить текст на два
параграфа:
-- | The first paragraph goes here.
--
-- The second paragraph goes here.
fun :: a -> b
Блоки кода
Существует два способа обозначения блоков кода:
-- | This documentation includes two blocks of code:
--
-- @
--
f x = x + x
--
g x = x
-- @
--
-- >
g x = x * 42
В первом варианте мы заключаем блок кода в окружение ...@@. Так мы можем выделить целый кусок
кода. Для выделения одной строки мы можем воспользоваться знаком > .
Примеры вычисления в интерпретаторе
В Haddock мы можем привести пример вычисления выражения в интерпретаторе. Это делается с помощью
тройного символа > :
-- | Two examples are given bellow:
--
-- >>> 2+3
-- 5
--
-- >>> print 1 >> print 2
-- 1
-- 2
Строки, которые идут сразу за строкой с символом >>> помечаются как результат выполнения выражения
в интерпретаторе.
Имена определений
Для того чтобы выделить имя любого определения, будь то функция, тип или класс, необходимо заклю-
чить его в ординарные кавычки, как в ’T’. При этом Haddock установит ссылку к определению и подсветит
имя в тексте. Для того чтобы сослаться на определение из другого модуля необходимо написать его полное
имя, то есть с приставкой имени модуля, например функция fun, определённая в модуле M, имеет полное
имя M. fun, тогда в комментариях мы обозначаем её ’M.fun’.
Ординарные кавычки часто используются в английском языке как апострофы, в таких сочетаниях как
don’t, isn’t. Перед такими вхождениями ординарных кавычек можно не писать обратный слэш. Haddock сумеет
отличить их от идентификатора.
Курсив и моноширинный шрифт
Для выделения текста курсивом, он заключается в окружение ... . Для написания текста моноширинным
шрифтом, он заключается в окружение ...@@.
Модули
Для обозначения модулей используются двойные кавычки, как в
-- | This is a reference to the ”Foo” module.
Создание документации с помощью Haddock | 273
Списки
Список без нумерации обозначается с помощью звёздочек:
-- | This is a bulleted list:
--
--
* first item
--
--
* second item
Пронумерованный список, обозначается символами (n) или n. (n с точкой), где n – некоторое целое
число:
-- | This is an enumerated list:
--
--
(1) first item
--
--
2. second item
Список определений
Определения обозначаются квадратными скобками, например комментарий:
-- | This is a definition list:
--
--
[@foo@] The description of @foo@.
--
--
[@bar@] The description of @bar@.
в документации будет выглядеть так:
foo The description of foo.
bar The description of bar.
Для выделения текста моноширинным шрифтом мы воспользовались окружением ...@@.
URL
Ссылки на сайты включаются с помощью окружения <...> .
Ссылки внутри модуля
Для того чтобы сослаться на какой-нибудь текст внутри модуля, его необходимо отметить ссылкой. Для
этого мы помещаем в том месте, на которое мы хотим сослаться, запись #label#, где label – это идентифика-
тор ссылки. Теперь мы можем сослаться на это место из другого модуля с помощью записи ” module#label”,
где module – имя модуля, в котором находится ссылка label.
18.3 Краткое содержание
В этой главе мы познакомились с основными элементами арсенала разработчика программ. Мы научи-
лись создавать библиотеки и документировать их.
18.4 Упражнения
Вспомните один из примеров и превратите его в библиотеку. Например, напишите библиотеку для нату-
ральных чисел Пеано.
274 | Глава 18: Средства разработки
Глава 19
Ориентируемся по карте
Рассмотрим задачу поиска маршрута на карте. У нас есть карта метро и нам нужно проложить маршрут
от одной станции к другой. Карта метро~– это граф, узлы обозначают станции, а рёбра соединяют соседние
станции. Предположим, что мы знаем расстояния между всеми станциями и нам надо найти кратчайший
путь от станции площадь Баха до станции Таинственный лес (рис. 19.1).
Космодром
Запад
Таинственный
лес
Призрак
Инева
ул.Булычёва
Троллев мост
Тилль
Сириус
Звезда
Север
Лао
Юг
Де
пл.Баха
Крест
пл.Шекспира
Дно болота
Родник
Восток
Рис. 19.1: Схема метрополитена
Давайте переведём этот рисунок на Haskell. Сначала опишем имена линий и станций:
module Metro where
data Station = St Way Name
deriving (Show, Eq)
data Way = Blue | Black | Green | Red | Orange
deriving (Show, Eq)
data Name = Kosmodrom | UlBylichova | Zvezda
| Zapad | Ineva | De | Krest | Rodnik | Vostok
| Yug | Sirius | Til | TrollevMost | Prizrak | TainstvenniyLes
| DnoBolota | PlBakha | Lao | Sever
| PlShekspira
deriving (Show, Eq)
Предположим, что нам известны координаты каждой из станций. По ним мы можем вычислять расстояние
между станциями по прямой:
| 275
data Point = Point
{ px :: Double
, py :: Double
} deriving (Show, Eq)
place :: Name -> Point
place x = uncurry Point $ case x of
Kosmodrom
-> (-3,7)
UlBylichova
-> (-2,4)
Zvezda
-> (0,1)
Zapad
-> (1,7)
Ineva
-> (0.5, 4)
De
-> (0, -1)
Krest
-> (0, -3)
Rodnik
-> (0, -5)
Vostok
-> (-1, -7)
Yug
-> (-7, -1)
Sirius
-> (-3,0)
Til
-> (3,2)
TrollevMost
-> (5,4)
Prizrak
-> (8,6)
TainstvenniyLes
-> (11,7)
DnoBolota
-> (-7, -4)
PlBakha
-> (-3, -3)
Lao
-> (3.5,0)
Sever
-> (6,1)
PlShekspira
-> (3, -3)
dist :: Point -> Point -> Double
dist a b = sqrt $ (px a - px b)^2 + (py a - py b)^2
stationDist :: Station -> Station -> Double
stationDist (St n a) (St m b)
| n /= m && a == b
= penalty
| otherwise
= dist (place a) (place b)
where penalty = 1
Расстояние между точками вычисляется по формуле Евклида (dist). Если у станций одинаковые имена,
но они расположены на разных линиях мы будем считать, что расстояние между ними равно единице. Теперь
нам необходимо описать связность станций. Мы опишем связность в виде функции, которая для данной
станции возвращает список всех соседних с ней станций:
metroMap :: Station -> [Station]
metroMap x = case x of
St Black Kosmodrom
-> [St Black UlBylichova]
St Black UlBylichova
->
[St Black Kosmodrom, St Black Zvezda, St Red UlBylichova]
St Black
Zvezda
->
[St Black UlBylichova, St Blue
Zvezda, St Green Zvezda]
...
Приведён пример заполнения только для одной линии. Остальные линии заполняются аналогично. Об-
ратите внимание на то, что некоторые станции имеют одинаковые имена, но находятся на разных линиях.
Всё готово для того чтобы написать функцию поиска маршрута. Для этого мы воспользуемся алгоритмом
A*.
19.1 Алгоритм эвристического поиска А*
Наша задача относится к задачам поиска путей на графе. Путём на графе называют такую последователь-
ность узлов, в которой для любых двух соседних узлов существует ребро, которое их соединяет. В нашем
случае графом является карта метро, узлами~– станции, рёбрами~– линии между станциями, а путями~–
маршруты.
Представим, что мы находимся в узле A и нам необходимо попасть в узел B и единственное, что нам
известно~– это все соседние узлы с тем, в котором мы находимся. У нас есть возможность перейти в один
276 | Глава 19: Ориентируемся по карте
из соседних узлов и посмотреть нет ли среди их соседей узла B. В этом случае нам ничего не остаётся кроме
того как бродить по карте от станции к станции в случайном порядке, пока мы не натолкнёмся на узел B или
все узлы не кончатся. Такой поиск называют слепым.
Вот если бы у нас был компас, который в каждой точке указывал в сторону цели нам было бы гораздо
проще. Такой компас принято называть эвристикой. Это функция, которая принимает узел и возвращает
число. Чем меньше число, тем ближе узел к цели. Обычно эвристика указывает не точное расстояние до
цели, поскольку мы не знаем где цель, а приблизительную оценку. Мы не знаем расстояние до цели, но
догадываемся, нам кажется, что она где-то там, ещё чуть-чуть и мы найдём её. Примером эвристики для
поиска по карте может быть функция, которая вычисляет расстояние по прямой до цели. Предположим, что
мы не знаем где находится цель (какая дорога к ней ведёт), но мы знаем её координаты. Также мы знаем
координаты каждой вершины, в которой мы находимся. Тогда мы можем легко вычислить расстояние по
прямой до цели и наш поиск станет гораздо более осмысленным.
Так находясь в точке A мы можем сразу пойти в тот соседний узел, который ближе всех к цели. Такой
поиск называют поиском по первому лучшему приближению. В поиске A* учитывается не только расстояние
до цели, но и то расстояние, которое мы уже прошли. Мы выбираем не ту вершину, которая ближе к цели, а
ту для которой полный путь до цели будет минимальным. Ведь пока мы идём мы можем запоминать какое
расстояние мы уже прошли. Прибавив к этому значению, то которое мы получим с помощью эвристики мы
получим полный (предполагаемый) путь до цели.
Поиск А* гораздо лучше поиска по первому лучшему приближению. Его часто применяют в компьютерных
играх для поиска пути или принятия решений.
Принято разделять поиск на графе и поиск на дереве. Если мы идём по графу, то вершины могут по-
вторятся (они образуют циклы). В случае поиска на дереве мы считаем, что все вершины уникальны. При
поиске на графе очень важно запоминать те вершины, в которых мы уже побывали. Иначе мы будем очень
часто ходить кругами.
В 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 будет применена не сразу, а
лишь тогда, когда нам действительно понадобится значение пути. Это как раз и произойдёт лишь один раз,
в самом конце программы, лишь для одного значения!
Давайте пока пропустим функцию 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)
ping :: (Ord h, Ord a) => Visited a -> ToVisit a h -> [Path a]
ping visited toVisit
| isEmpty toVisit = []
| otherwise
= pong visited toVisit’ a
where (a, toVisit’) = next toVisit
pong :: (Ord h, Ord a)
=> Visited a -> ToVisit a h -> Tree (Path a, h) -> [Path a]
pong visited toVisit a
| inside a visited
= ping visited toVisit
| otherwise
= getPath a :
ping (insert a visited) (schedule (subForest a) toVisit)
Типы Visited и ToVisit обозначают наборы вершин, которые мы уже посетили и которые только собира-
емся посетить. Не вдаваясь в подробности интерфейса этих типов, давайте присмотримся к функциям ping и
pong с точки зрения функции, которая их будет вызывать, а именно функции findPath. Эта функция ожидает
на входе список. Внутри она обходит список в поисках нужного элемента, поэтому она будет применять со-
поставление с образцом, разбирая список на части. Сначала она запросит сопоставление с пустым списком,
запустится функция ping с пустым множеством посещённых вершин (none) и одним элементом в очереди
вершин (singleton a), которые предстоит посетить. Функция ping проверит не является ли очередь пустой,
очередь содержит один элемент, поэтому она перейдёт к следующему случаю и извлечёт из очереди один
элемент (next), который будет передан в функцию pong. Функция pong проверит нет ли в списке уже посе-
щённых элементов того, который был только что извлечён (inside a visited). Если это окажется так, то
она запросит следующий элемент у функции ping. Если же исходный элемент окажется новым, она добавит
его в список (getPath a : ... ) и запланирует обход всех дочерних деревьев данного элемента (schedule
(subForest a) toVisit). При первом заходе исходный элемент окажется новым и функция findPath поймёт,
что список не пустой и остановит вычисление. Она немного передохнёт и примется за следующий случай.
Там она будет извлекать первый элемент списка и сопоставлять его с предикатом. При этом первый элемент
уже вычислен. Мы воспользуемся этим, убедимся в том, что он не является целью и рекурсивно вызовем
функцию find на хвосте списка. Функция findPath запросит следующее значение и так далее.
Наша функция flattenPath не является развёрткой, но очень похожа на неё тем, что позволяет вычислять
результирующий список частично. Например функция length требует полного обхода списка. Мы не можем
использовать её с бесконечными списками. Теперь давайте разберёмся с подчинёнными функциями:
getPath :: Tree (Path a, h) -> Path a
getPath = fst . rootLabel
Функции для множества вершин, которые мы уже посетили:
import qualified Data.Set as S
...
type Visited a
= S.Set a
none :: Ord a => Visited a
none = S. empty
insert :: Ord a => Tree (Path a, h) -> Visited a -> Visited a
insert = S. insert . pathEnd . getPath
inside :: Ord a => Tree (Path a, h) -> Visited a -> Bool
inside = S. member . pathEnd . getPath
Алгоритм эвристического поиска А* | 279
Функции для очереди тех вершин, что мы только собираемся посетить:
import Data.Maybe
import qualified Data.PriorityQueue.FingerTree as Q
...
type ToVisit a h = Q.PQueue h (Tree (Path a, h))
priority t = (snd $ rootLabel t, t)
singleton :: Ord h => Tree (Path a, h) -> ToVisit a h
singleton = uncurry Q. singleton . priority
next :: Ord h => ToVisit a h -> (Tree (Path a, h), ToVisit a h)
next = fromJust . Q. minView
isEmpty :: Ord h => ToVisit a h -> Bool
isEmpty = Q. null
schedule :: Ord h => [Tree (Path a, h)] -> ToVisit a h -> ToVisit a h
schedule = Q. union . Q. fromList . fmap priority
Эти функции очень простые, они специализируют более общие функции для типов Set и
PQueue, вы наверняка легко разберётесь с ними, заглянув в документацию к модулям Data.Set и
Data.PriorityQueue.FingerTree.
Осталось только написать функцию, которая будет составлять дерево поиска для алгоритма A*. Она при-
нимает функцию ветвления, а также функцию расстояния до цели и строит по ним дерево поиска:
astarTree :: (Num h, Ord h)
=> (a -> [(a, h)]) -> (a -> h) -> a -> Tree (a, h)
astarTree alts distToGoal s0 = unfoldTree f (s0, 0)
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]
После этого мы можем очень легко комбинировать различные выборки при тестировании.
*Test> quickCheck $ \(Only4 a) (Only4 b) -> prop1 a b
+++ OK, passed 100 tests.
*Test> quickCheck $ \(Only4 a) (OnlyOrange b) -> prop1 a b
+++ OK, passed 100 tests.
*Test> quickCheck $ \a (OnlyOrange b) -> prop2 a b
+++ OK, passed 100 tests.
Классификация тестовых случаев
Мы можем попросить у QuickCheck, чтобы он разбил тестовую выборку на классы и в конце тестирования
сообщил бы нам сколько элементов в какой класс попали. Это делается с помощью функции classify:
classify :: Testable prop => Bool -> String -> prop -> Property
Она принимает условие классификации, метку класса и свойство. Например так мы можем разбить вы-
борку по типам линий:
prop3 :: Station -> Station -> Property
prop3 a@(St wa _) b@(St wb _) =
classify (wa == Orange || wb == Orange) ”Orange” $
classify (wa == Black
|| wb == Black)
”Black”
$
classify (wa == Red
|| wb == Red)
”Red”
$ prop1 a b
Протестируем:
*Test> quickCheck prop3
+++ OK, passed 100 tests:
34% Red
15% Orange
9% Black
8% Orange, Red
6% Black, Red
5% Orange, Black
19.3 Оценка быстродействия с помощью criterion
Недавно появилась библиотека unordered-containers. Она предлагает более эффективную реализацию
нескольких структур из стандартной библиотеки containers. Например там мы можем найти тип HashSet.
Почему бы нам не заменить на него стандартный тип Set?
Оценка быстродействия с помощью criterion | 283
cabal install unordered-containers
Изменения отразятся лишь на контекстах объявлений типов. Элементы принадлжежащие множеству
HashSet должны быть экземплярами классов Eq и Hashable. Новый класс Hashable нужен для ускорения
работы с данными. Давайте посмотрим на этот класс:
Prelude> :m Data.Hashable
Prelude Data.Hashable> :i Hashable
class Hashable a where
hash :: a -> Int
hashWithSalt :: Int -> a -> Int
-- Defined in ‘Data.Hashable’
...
... много экземпляров
Обязательный метод класса hash даёт нам возможность преобразовать элемент в целое число. Это число
называют хеш-ключом. Хеш-ключи используеются для хранения элементов в хеш-таблицах. Мы не будем
подробно на них останавливаться, отметим лишь то, что они позволяют очень быстро извлекать данные из
контейнеров и обновлять данные.
Теперь просто скопируйте модуль Astar. hs измените одну строчку, и добавьте ещё одну (в шапке моду-
ля):
import qualified Data.HashSet as S
import Data.Hashable
Попробуйте загрузить модуль в интерпретатор. ghci выдаст длинный список ошибок, это – хорошо. По
ним вы сможете легко догадать в каких местах необходимо заменить Ord a на (Hashable a, Eq a).
Теперь для поиска маршрутов нам необходимо определить экземпляр класса Hashable для типа Station.
В модуле Data.Hashable уже определены экземпляры для многих стандартных типов. Мы воспользуемся
экземпляром для целых чисел.
Добавим в driving подчинённых типов класс Enum и воспользуемся им в экземпляре для Hashable:
instance Hashable Station where
hash (St a b) = hash (fromEnum a, fromEnum b)
Теперь определим две функции определения маршрута:
import qualified AstarSet
as S
import qualified AstarHashSet
as H
...
connectSet :: Station -> Station -> Maybe [Station]
connectSet a b = S. search (== b) $ metroTree a b
connectHashSet :: Station -> Station -> Maybe [Station]
connectHashSet a b = H. search (== b) $ metroTree a b
Как нам сравнить быстродействие двух алгоримтов? Оценка быстродействия программ, написанных на
Haskell, может таить в себе подвохи. Например если мы запустим оба алгоритма в одной программе, возмож-
но случится такая ситуация, что часть данных, одинаковая для каждого из методов будет вычислена один
раз, а во втором алгоритме переиспользована, и нам может показаться, что второй алгоритм гораздо быстрее
первого. Также необходимо учитывать внешние факторы. Тестовая программа вычисляется на одном ком-
пьютере, и если алгоритмы тестируются в разное время, может статься так, что мы сидели-сидели и ждали
пока тест завершится, в это время работал первый алгоритм, потом нам надоело ждать, мы решили включить
музыку, проверить почту, и второму алгоритмку досталось меньше вычислительных ресурсов. Все эти фак-
торы необходимо учитывать при тестировании. Как раз для этого и существует замечательная бибилиотека
criterion.
Она проводит серию тестов и по ним оценивает показатели быстродействия. При этом учитывается до-
стоверность тестов. По результатам тестирования показатели сверяются между собой, и если разброс оказы-
вается слишком большим, программа сообщает нам: что-то тут не чисто, данным не стоит доверять. Более
того результаты оформляются в наглядные графики, мы можем на глаз оценить распределения и разброс
показателей.
284 | Глава 19: Ориентируемся по карте
Основные типы criterion
Центральным элементом бибилиотеки является класс Benchmarkable. Он объединяет данные, которые
можно тестировать. Среди них чистые функции (тип Pure) и значения с побочными эффектами (тип IO a).
Мы можем превращать данные в тесты (тип Benchmark) с помощью функции bench:
benchSource :: Benchmarkable b => String -> b -> Benchmark
Она добавляет к данным комментарий и превращает их в тесты. Как было отмечено, существует одна
тонкость при тестировании чистых функций: чистые функции в Haskell могут разделять данные между со-
бой, поэтому для независимого тестирования мы оборачиваем функции в специальный тип Pure. У нас есть
два варианта тестирования:
Мы можем протестировать приведение результата к заголовочной нормальной форме (вспомните главу
о ленивых вычислениях):
nf :: NFData b => (a -> b) -> a -> Pure
или к слабой заголовочной нормальной форме:
whnf :: (a -> b) -> a -> Pure
Аналогичные функции (nfIO, whnfIO) есть и для данных с побочными эффектами. Класс NFData обозна-
чает все значения, для которых заголовочная нормальная форма определена. Этот класс пришёл в бибилио-
теку criterion из библиотеки deepseq. Стоит отметить эту бибилотеку. В ней определён аналог функции
seq. Функция seq приводит значения к слабой заголовочной нормальной форме (мы заглядываем вглюбь
значения лишь на один конструктор), а функция deepseq проводит полное вычисление значения. Значение
приводится к заголовочной нормальной форме.
Также нам пригодится функция группировки тестов:
bgroup :: String -> [Benchmark] -> Benchmark
С её помощью мы объединяем список тестов в один, под некоторым именем. Тестирование проводится с
помощью функции defaultMain:
defaultMain :: [Benchmark] -> IO ()
Она принимает список тестов и выполняет их. Выполнение тестов заключается в компиляции програм-
мы. После компиляции мы получим исполняемый файл который проводит тестирование в зависимости от
параметров, указываемых фланами. До них мы ещё доберёмся, а пока опишем наши тесты:
-- | Module: Speed.hs
module Main where
import Criterion.Main
import Control.DeepSeq
import Metro
instance NFData Station where
rnf (St a b) = rnf (rnf a, rnf b)
instance NFData Way
where
instance NFData Name where
pair1 = (St Orange DnoBolota, St Green Prizrak)
pair2 = (St Red Lao, St Blue De)
test name search = bgroup name $ [
bench ”1” $ nf (uncurry search) pair1,
bench ”2” $ nf (uncurry search) pair2]
main = defaultMain [
test ”Set”
connectSet,
test ”Hash” connectHashSet]
Оценка быстродействия с помощью criterion | 285
Экземпляр для класса NFData похож на экземпляр для Hashable. Мы также определили метод значения
через методы для типов, из которых он состоит. Класс NFData устроен так, что для типов из класса Enum мы
можем воспользоваться определением по умолчанию (как в случае для Way и Name).
Теперь перейдём в командную строку, переключимся на директорию с нашим модулем и скомпилируем
его:
$ ghc -O --make Speed.hs
Флаг -O говорит ghc, что не обходимо провести оптимизацию кода. Появится исполняемый файл Speed.
Что мы можем делать с этим файлом? Узнать это можно, запустив его с флагом –help:
Мы можем узнать какие функции нам доступны, набрав:
$ ./Speed --help
I don’t know what version I am.
Usage: Speed [OPTIONS] [BENCHMARKS]
-h, -?
--help
print help, then exit
-G
--no-gc
do not collect garbage between iterations
-g
--gc
collect garbage between iterations
-I CI
--ci=CI
bootstrap confidence interval
-l
--list
print only a list of benchmark names
-o FILENAME
--output=FILENAME
report file to write to
-q
--quiet
print less output
--resamples=N
number of bootstrap resamples to perform
-s N
--samples=N
number of samples to collect
-t FILENAME
--template=FILENAME
template file to use
-u FILENAME
--summary=FILENAME
produce a summary CSV file of all results
-V
--version
display version, then exit
-v
--verbose
print more output
If no benchmark names are given, all are run
Otherwise, benchmarks are run by prefix match
Из этих настроек самые интресные, это -s и -o. -s указывает число сэмплов выборке (столько раз будет
запущен каждый тест). а -o говорит, о том в какой файл поместить результаты. Результаты представлены в
виде графиков, формируется файл, который можно открыть в любом браузере. Записать данные в таблицу
(например для отчёта) можно с помощью флага -u.
Проверим результаты:
./Speed -o res. html -s 100
Откроем файл res. html и посмотрим на графики. Оказалось, что для данных двух случаев первый алго-
ритм работал немного лучше. Но выборку из двух вариантов вряд ли можно считать убедительной. Давайте
расширим выборку с помощью QuickCheck. Мы запустим проверку какого-нибудь свойства тем и другим
методом. В итоге QuickCheck сам сгенерирует достаточное число случайных данных, а criterion оценит
быстродействие. Мы проверим самое первое свойство (о перевёрнутых маршрутах) на том и другом алгорит-
ме.
module Main where
import Control.Applicative
import Test.QuickCheck
import Metro
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
prop :: (Station -> Station -> Maybe [Station])
-> Station -> Station -> Bool
286 | Глава 19: Ориентируемся по карте
prop search a b = search a b == (reverse <$> search b a)
main = defaultMain [
bench ”Set”
$ quickCheck (prop connectSet),
bench ”Hash” $ quickCheck (prop connectHashSet)]
В этом тесте метод Set также оказался совсем немного быстрее.
Как интерпретировать результаты? С левой стороны мы видим оценку плотности вероятности распреде-
ления быстродействия. Под графиком мы видим среднее (mean) и дисперсию значения (std dev). Показаны
три числа. Это нижняя грань доверительного интервала, оценка величины и верхняя грань доверительного
интервала (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-библиотеки, это графическая библио-
тека OpenGL и физический движок Chipmunk.
Описание игры
Игра происходит на бильярдной доске. Игрок управляет красным шаром, кликнув в любую точку экрана,
он может изменить направление вектора скорости красного шара. Шар покатится туда, куда кликнул пользо-
ватель в последний раз. Из луз будут вылетать шары трёх типов: синие, зелёные и оранжевые. Столкновение
красного шара с синим означает минус одну жизнь, с зелёным – плюс одну жизнь, оранжевый шар означает
бонус. Если шар игрока сталкивается с оранжевым шаром все шары в определённом радиусе от места столк-
новения исчезают и записываются в бонусные очки, за каждый шар по одному очку, при этом шар с которым
произошло столкновение не считается. Все столкновения – абсолютно упругие, поэтому при столкновении
энергия сохраняется и шары никогда не остановятся. Если шар попадает в лузу, то он исчезает. Если в лузу
попал шар игрока – это означает, что игра окончена. Игрок стартует с несколькими жизнями, когда их чис-
ло подходит к нулю игра останавливается. После столкновения с зелёным шаром, шар пропадает, а после
столкновения с синим – нет. В итоге все против игрока, кроме зелёных и оранжевых шаров.
20.1 Основные библиотеки
Контролировать физику игрового мира будет библиотека Chipmunk, а библиотека OpenGL будет рисовать
(конечно если мы её этому научим). Пришло время с ними познакомится.
288 | Глава 20: Императивное программирование
Изменяемые значения
Перед тем как мы перейдём к библиотекам нам нужно узнать ещё кое-что. В Haskell мы не можем изменять
значения. Но в С это делается постоянно, а соответственно и в библиотеках написанных на С тоже. Для того
чтобы имитировать в Haskell механизм обновления значений были придуманы специальные типы. Мы можем
объявить изменяемое значение и обновлять его, но только в пределах типа IO.
IORef
Тип IORef из модуля Data.IORef описывает изменяемые значения:
newIORef :: a -> IO IORef
readIORef
:: IORef a -> IO a
writeIORef
:: IORef a -> a -> IO ()
modifyIORef :: IORef a -> (a -> a) -> IO ()
Функция newIORef создаёт изменяемое значение и инициализирует его некоторым значением, кото-
рые мы можем считать с помощью функции readIORef или обновить с помощью функций writeIORef или
modifyIORef. Посмотрим как это работает:
module Main where
import Data.IORef
main = var >>= (\v ->
readIORef v >>= print
>> writeIORef v 4
>> readIORef v >>= print)
where var = newIORef 2
Теперь посмотрим на ответ ghci:
*Main> :l HelloIORef
[1 of 1] Compiling Main
( HelloIORef. hs, interpreted )
Ok, modules loaded: Main.
*Main> main
2
4
Самое время вернуться к главе 17 и вспомнить о do-нотации. Такой императивный код гораздо нагляднее
писать так:
main = do
var <- newIORef 2
x <- readIORef var
print x
writeIORef var 4
x <- readIORef var
print x
Эта запись выглядит как последовательность действий. Не правда ли очень похоже на обычный импера-
тивный язык. Такие переменные встречаются очень часто в библиотеках, заимствованных из~С.
StateVar
В модуле Data.StateVar определены типы, которые накладывают ограничение на права по чтению и
ТЕЛЕГРАМКанал с обзорами, анонсами новинок и книжными подборками
Книжный Вестник
Бот для удобного поиска книг (если не нашлось на сайте)
Поиск книг
Свежие любовные романы в удобных форматах
Любовные романы
О психологии, саморазвитии и личностном росте
Саморазвитие
Детективы и триллеры, все новинки
Детективы
Фантастика и фэнтези, все новинки
Фантастика
Отборные классические книги
Классика
ВКОНТАКТЕБиблиотека с любовными романами, которая наверняка придётся по вкусу женской части аудитории
Любовные романы
Библиотека с фантастикой и фэнтези, а также смежных жанров
Фантастика
Самые популярные книги в формате фб2
Топ фб2
книги