типа:
(a -> m b) -> (b -> c) -> (a -> m c)
Оказывается мы можем составить её из методов класса Kleisli. Мы назовём эту функцию композиции
(+> ).
(+> ) :: Kleisli m => (a -> m b) -> (b -> c) -> (a -> m c)
f +> g = f *> (g >> idK)
С помощью метода idK мы можем погрузить в мир специальных функций любую обычную функцию.
Композиция функций | 87
Три композиции
У нас появилось много композиций целых три:
аргументы
|
результат
обычная
>>
обычная
==
обычная
специальная
+>
обычная
==
специальная
специальная
*>
специальная
==
специальная
При этом важно понимать, что по смыслу это три одинаковые функции. Они обозначают операцию по-
следовательного применения функций. Разные значки отражают разные типы функций аргументов.
Обобщённая формулировка категории Клейсли
Отметим, что мы могли бы сформулировать класс Kleisli и в более общем виде с помощью класса
Category:
class Kleisli m where
idK
:: Category cat => cat a (m a)
(*> ) :: Category cat => cat a (m b) -> cat b (m c) -> cat a (m c)
(+> ) :: (Category cat, Kleisli m)
=> cat a (m b) -> cat b c -> cat a (m c)
f +> g = f *> (g >> idK)
Мы заменили функциональный тип на его обобщение. Для наглядности мы будем пользоваться специ-
альной формулировкой со стрелочным типом.
Для этого мы определим модуль Kleisli. hs
module Kleisli where
import Prelude hiding (id, (>> ))
class Category cat where
id
:: cat a a
(>> ) :: cat a b -> cat b c -> cat a c
class Kleisli m where
idK
:: a -> m a
(*> ) :: (a -> m b) -> (b -> m c) -> (a -> m c)
(+> ) :: Kleisli m => (a -> m b) -> (b -> c) -> (a -> m c)
f +> g = f *> (g >> idK)
-- Экземпляр для функций
instance Category (-> ) where
id
= \x -> x
f >> g
= \x -> g (f x)
Мы не будем импортировать функцию id, а определим её в классе Category. Также в Prelude уже опре-
делена функция (>> ) мы спрячем её с помощью специальной директивы hiding для того, чтобы она нам не
мешалась. Далее мы будем дополнять этот модуль экземплярами класса Kleisli и примерами.
6.2 Примеры специальных функций
Частично определённые функции
Частично определённые функции – это такие функции, которые определены не для всех значений аргу-
ментов. Примером такой функции может быть функция поиска предыдущего числа для натуральных чисел.
Поскольку числа натуральные, то для нуля такого числа нет. Для описания этого поведения мы можем вос-
пользоваться специальным типом Maybe. Посмотрим на его определение:
data Maybe a = Nothing | Just a
deriving (Show, Eq, Ord)
88 | Глава 6: Функторы и монады: теория
a
f
b
Nothing
Рис. 6.2: Частично определённая функция
Частично определённая функция имеет тип a -> Maybe b (рис. 6.2), если всё в порядке и значение было
вычислено, она вернёт (Just a), а в случае ошибки будет возвращено значение Nothing. Теперь мы можем
определить нашу функцию так:
pred :: Nat -> Maybe Nat
pred Zero
= Nothing
pred (Succ a)
= Just a
Для Zero предыдущий элемент не определён .
Составляем функции вручную
Значение функции pred завёрнуто в упаковку Maybe, и для того чтобы воспользоваться им нам придётся
разворачивать его каждый раз. Как будет выглядеть функция извлечения дважды предыдущего натурального
числа:
pred2 :: Nat -> Maybe Nat
pred2 x =
case pred x of
Just (Succ a) -> Just a
_
-> Nothing
Если мы захотим определить pred3, мы заменим pred в case-выражении на pred2. Вроде не такое уж и
длинное решение. Но всё же мы теряем все преимущества гибких функций, все преимущества бесточечного
стиля. Нам бы хотелось написать так:
pred2 :: Nat -> Maybe Nat
pred2 = pred >> pred
pred3 :: Nat -> Maybe Nat
pred3 = pred >> pred >> pred
Но компилятор этого не допустит.
Композиция
Для того чтобы понять как устроена композиция частично определённых функций изобразим её вычисле-
ние графически (рис. 6.3). Сверху изображены две частично определённых функции. Если функция f вернула
значение, то оно подставляется в следующую частично определённую функцию. Если же первая функция не
смогла вычислить результат и вернула Nothing, то считается что вся функция (f*> g) вернула Nothing.
Теперь давайте закодируем это определение в Haskell. При этом мы воспользуемся нашим классом
Kleisli. Аналогом функции id для частично определённых функций будет функция, которая просто за-
ворачивает значение в конструктор Just.
instance Kleisli Maybe where
idK
= Just
f *> g = \a -> case f a of
Nothing -> Nothing
Just b
-> g b
Смотрите, в case-выражении мы возвращаем Nothing, если функция f вернула Nothing, а если ей удалось
вычислить значение и она вернула (Just b) мы передаём это значение в следующую функцию, то есть
составляем выражение (g b).
Сохраним это определение в модуле Kleisli, а также определение для функции pred и загрузим модуль
в интерпретатор. Перед этим нам придётся добавить в список функций, которые мы не хотим импортировать
из Prelude функцию pred, она также уже определена в Prelude. Для определения нашей функции нам по-
требуется модуль Nat, который мы уже определили. Скопируем файл Nat. hs в ту же директорию, в которой
содержится файл Kleisli. hs и подключим этот модуль. Шапка модуля примет вид:
Примеры специальных функций | 89
a
f
b
b
g
c
Nothing
Nothing
b
a
g
f
c
Nothing
a
f*>g
c
Nothing
Рис. 6.3: Композиция частично определённых функций
module Kleisli where
import Prelude hiding(id, (>> ), pred)
import Nat
Добавим определение экземпляра Kleisli для Maybe в модуль Kleisli а также определение функции
pred. Сохраним обновлённый модуль и загрузим в интерпретатор.
*Kleisli> :load Kleisli
[1 of 2] Compiling Nat
( Nat. hs, interpreted )
[2 of 2] Compiling Kleisli
( Kleisli. hs, interpreted )
Ok, modules loaded: Kleisli, Nat.
*Kleisli> let pred2 = pred *> pred
*Kleisli> let pred3 = pred *> pred *> pred
*Kleisli> let two
= Succ (Succ Zero)
*Kleisli>
*Kleisli> pred two
Just (Succ Zero)
*Kleisli> pred3 two
Nothing
Обратите внимание на то, как легко определяются производные функции. Желаемое поведение для ча-
стично определённых функций закодировано в функции (*> ) теперь нам не нужно заворачивать значения и
разворачивать их из типа Maybe.
Приведём пример функции, которая составлена из частично определённой функции и обычной. Опреде-
лим функцию beside, которая вычисляет соседей для данного числа Пеано.
*Kleisli> let beside = pred +> \a -> (a, a + 2)
*Kleisli> beside Zero
Nothing
*Kleisli> beside two
Just (Succ Zero, Succ (Succ (Succ Zero)))
*Kleisli> (pred *> beside) two
Just (Zero, Succ (Succ Zero))
В выражении
pred +> \a -> (a, a + 2)
Мы сначала вычисляем предыдущее число, и если оно есть составляем пару из \a -> (a, a+2), в пару
попадёт данное число и число, следующее за ним через одно. Поскольку сначала мы вычислили предыдущее
число в итоговом кортеже окажется предыдущее число и следующее.
90 | Глава 6: Функторы и монады: теория
Итак с помощью функций из класса Kleisli мы можем составлять частично определённые функции в
бесточечном стиле. Обратите внимание на то, что все функции кроме pred были составлены в интерпрета-
торе.Отметим, что в Prelude определена специальная функция maybe, которая похожа на функцию foldr для
списков, она заменяет в значении типа Maybe конструкторы на функции. Посмотрим на её определение:
maybe
:: b -> (a -> b) -> Maybe a -> b
maybe n f Nothing
=
n
maybe n f (Just x) =
f x
С помощью этой функции мы можем переписать определение экземпляра Kleisli так:
instance Kleisli Maybe where
idM
= Just
f *> g
= f >> maybe Nothing g
Многозначные функции
Многозначные функции ветрены и непостоянны. Для некоторых значений аргументов они возвращают
одно значение, для иных десять, а для третьих и вовсе ничего. В Haskell такие функции имеют тип a -> [b].
Функция возвращает список ответов. На (рис. 6.4) изображена схема многозначной функции.
a
f
b
Рис. 6.4: Многозначная функция
Приведём пример. Системы Линденмайера (или L-системы) моделируют развитие живого организма.
Считается, что организм состоит из последовательности букв (или клеток). В каждый момент времени одна
буква заменяется на новую последовательность букв, согласно определённым правилам. Так организм живёт
и развивается. Приведём пример:
a → ab
b → a
a
ab
aba
abaab
abaababa
У нас есть два правила размножения клеток-букв в организме. На каждом этапе мы во всём слове заме-
няем букву a на слово ab и букву b на a. Начав с одной буквы a, мы за несколько шагов пришли к более
сложному слову.
Опишем этот процесс в Haskell. Для этого определим правила развития организма в виде многозначной
функции:
next :: Char -> String
next ’a’ = ”ab”
next ’b’ = ”a”
Напомню, что строки в Haskell являются списками символов. Теперь нам нужно применить многозначную
функцию к выходу многозначной функции. Для этого мы воспользуемся классом Kleisli.
Композиция
Определим экземпляр класса Kleisli для списков. На (рис. 6.5) изображена схема композиции в случае
многозначных функций. После применения первой функции f мы применяем функцию к каждому элементу
списка, который был получен из f. Так у нас получится список списков. Но нам нужен список, для этого
мы после применения g объединяем все значения в один большой список. Отметим, что функции f и g в
зависимости от значений могут возвращать разное число значений, поэтому на выходе у функций g разное
число стрелок.
Закодируем эту схему в Haskell:
Примеры специальных функций | 91
a
f
b
b
g
c
g
c
b
b
a
g
f
c
b
g
c
a
f*>g
c
Рис. 6.5: Композиция многозначных функций
instance Kleisli [] where
idK
= \a -> [a]
f *> g
= f >> map g >> concat
Функция тождества принимает одно значение и погружает его в список. В композиции мы сначала при-
меняем f, затем к каждому элементу списка результата применяем g, так у нас получается список списков.
После чего мы сворачиваем его в один список с помощью функции concat.
Вспомним тип функций map и concat:
map
:: (a -> b) -> [a] -> [b]
concat
:: [[a]] -> [a]
С помощью композиции мы можем получить n-тое поколение так:
generate :: Int -> (a -> [a]) -> (a -> [a])
generate 0 f = idK
generate n f = f *> generate (n - 1) f
Или мы можем воспользоваться функцией iterate и написать это определение так:
generate :: Int -> (a -> [a]) -> (a -> [a])
generate n f = iterate (*> f) idK !! n
Функция iterate принимает функцию вычисления следующего элемента и начальное значение и строит
бесконечный список итераций:
iterate :: (a -> a) -> a -> [a]
iterate f a = [a, f a, f (f a), f (f (f a)), ... ]
Если мы подставим наши аргументы то мы получим список:
[id, f, f*> f, f*> f*> f, f*> f*> f*> f, ... ]
Проверим как работает эта функция в интерпретаторе. Для этого мы сначала дополним наш модуль
Kleisli определением экземпляра для списков и функциями next и generate:
*Kleisli> :reload
[2 of 2] Compiling Kleisli
( Kleisli. hs, interpreted )
Ok, modules loaded: Kleisli, Nat.
*Kleisli> let gen n = generate n next ’a’
*Kleisli> gen 0
”a”
92 | Глава 6: Функторы и монады: теория
*Kleisli> gen 1
”ab”
*Kleisli> gen 2
”aba”
*Kleisli> gen 3
”abaab”
*Kleisli> gen 4
”abaababa”
Правила L-системы задаются многозначной функцией. Функция generate позволяет по такой функции
строить произвольное поколение развития буквенного организма.
6.3 Применение функций
Давайте определим в терминах композиции ещё одну полезную функцию. А именно функцию примене-
ния. Вспомним её тип:
($) :: (a -> b) -> a -> b
Эту функцию можно определить через композицию, если у нас есть в наличии постоянная функция и
единичный тип. Мы будем считать, что константа это функция из единичного типа в значение. Превратив
константу в функцию мы можем составить композицию:
($) :: (a -> b) -> a -> b
f $ a = (const a >> f) ()
В самом конце мы подставляем специальное значение (). Это значение единичного типа (unit type) или
кортежа с нулём элементов. Единичный тип имеет всего одно значение, которым мы и воспользовались в
этом определении. Зачем такое запутанное определение, вместо привычного (f a)? Оказывается точно таким
же способом мы можем определить применение в нашем мире специальных функций a -> m b.
Применение в этом мире происходит особенным образом. Необходимо помнить о том, что второй аргу-
мент функции применения, значение, которое мы подставляем в функцию, также было получено из какой-то
другой функции. Поэтому оно будет иметь такую же форму, что и значения справа от стрелки. В нашем
случае это m b.
Посмотрим на типы специальных функций применения:
(*$) :: (a -> m b) -> m a -> m b
(+$) :: (a -> b)
-> m a -> m b
Функция *$ применяет специальную функцию к специальному значению, а функция +$ применяет обыч-
ную функцию к специальному значению. Определения выглядят также как и в случае обычной функции
применения, мы только меняем знаки для композиции:
f
$ a = (const a >> f) ()
f *$ a = (const a *> f) ()
f +$ a = (const a +> f) ()
Теперь мы можем не только нанизывать специальные функции друг на друга но и применять их к значе-
ниям. Добавим эти определения в модуль Kleisli и посмотрим как происходит применение в интерпрета-
торе. Одна тонкость заключается в том, что мы определяли применение в терминах класса Kleisli, поэтому
правильно было написать типы новых функций так:
infixr 0 +$, *$
(*$) :: Kleisli m => (a -> m b) -> m a -> m b
(+$) :: Kleisli m => (a -> b)
-> m a -> m b
Также мы определили приоритет выполнения операций.
Загрузим в интерпретатор:
*Kleisli> let three = Succ (Succ (Succ Zero))
*Kleisli> pred *$ pred *$ idK three
Just (Succ Zero)
*Kleisli> pred *$ pred *$ idK Zero
Nothing
Применение функций | 93
Обратите внимание на то как мы погружаем в мир специальных функций обычное значение с помощью
функции idK.
Вычислим третье поколение L-системы:
*Kleisli> next *$ next *$ next *$ idK ’a’
”abaab”
Мы можем использовать и другие функции на списках:
*Kleisli> next *$ tail $ next *$ reverse $ next *$ idK ’a’
”aba”
Применение функций многих переменных
С помощью функции +$ мы можем применять к специальным значениям обычные функции одного аргу-
мента. А что если нам захочется применить функцию двух аргументов?
Например если мы захотим сложить два частично определённых числа:
?? (+) (Just 2) (Just 2)
На месте ?? должна стоять функция типа:
?? :: (a -> b -> c) -> m a -> m b -> m c
Оказывается с помощью методов класса Kleisli мы можем определить такую функцию для любой обыч-
ной функции, а не только для функции двух аргументов. Мы будем называть такие функции словом liftN,
где N – число, указывающее на арность функции. Функция (liftN f) “поднимает” (от англ. lift) обычную
функцию f в мир специальных функций.
Функция lift1 у нас уже есть, это просто функция +$. Теперь давайте определим функцию lift2:
lift2 :: Kleisli m => (a -> b -> c) -> m a -> m b -> m c
lift2 f a b = ...
Поскольку функция двух аргументов на самом деле является функцией одного аргумента мы можем
применить первый аргумент с помощью функции lift1, посмотрим что у нас получится:
lift1
:: (a’ -> b’) -> m’ a’ -> m’ b’
f
:: (a -> b -> c)
a
:: m a
lift1 f a
:: m (b -> c)
-- m’ == m, a’ == a, b’ == b -> c
Теперь в нашем определении для lift2 появится новое слагаемое g:
lift2 :: Kleisli m => (a -> b -> c) -> m a -> m b -> m c
lift2 f a b = ...
where g = lift1 f a
Один аргумент мы применили, осталось применить второй. Нам нужно составить выражение (g b), но
для этого нам нужна функция типа:
m (b -> c) -> m b -> m c
Эта функция применяет к специальному значению функцию, которая завёрнута в тип m. Посмотрим на
определение этой функции, мы назовём её $$:
($$) :: Kleisli m => m (a -> b) -> m a -> m b
mf $$ ma = ( +$ ma) *$ mf
Вы можете убедиться в том, что это определение проходит проверку типов. Посмотрим как эта функция
работает в интерпретаторе на примере частично определённых и многозначных функций, для этого давайте
добавим в модуль Kleisli это определение и загрузим его в интерпретатор:
94 | Глава 6: Функторы и монады: теория
*Kleisli> :reload Kleisli
Ok, modules loaded: Kleisli, Nat.
*Kleisli> Just (+2) $$ Just 2
Just 4
*Kleisli> Nothing $$ Just 2
Nothing
*Kleisli> [(+1), (+2), (+3)] $$ [10,20,30]
[11,21,31,12,22,32,13,23,33]
*Kleisli> [(+1), (+2), (+3)] $$ []
[]
Обратите внимание на то, что в случае списков были составлены все возможные комбинации применений.
Мы применили первую функцию из списка ко всем аргументам, потом вторую функцию, третью и объединили
все результаты в список.
Теперь мы можем закончить наше определение для lift2:
lift2 :: Kleisli m => (a -> b -> c) -> m a -> m b -> m c
lift2 f a b = f’ $$ b
where f’ = lift1 f a
Мы можем записать это определение более кратко:
lift2 :: Kleisli m => (a -> b -> c) -> m a -> m b -> m c
lift2 f a b = lift1 f a $$ b
Теперь давайте добавим это определение в модуль Kleisli и посмотрим в интерпретаторе как работает
эта функция:
*Kleisli> :reload
[2 of 2] Compiling Kleisli
( Kleisli. hs, interpreted )
Ok, modules loaded: Kleisli, Nat.
*Kleisli> lift2 (+) (Just 2) (Just 2)
Just 4
*Kleisli> lift2 (+) (Just 2) Nothing
Nothing
Как на счёт функций трёх и более аргументов? У нас уже есть функции lift1 и lift2 определим функцию
lift3:
lift3 :: Kleisli m => (a -> b -> c -> d) -> m a -> m b -> m c -> m d lift3 f a b c = ...
Первые два аргумента мы можем применить с помощью функции lift2. Посмотрим на тип получивше-
гося выражения:
lift2
:: Kleisli m => (a’ -> b’ -> c’) -> m a’ -> m b’ -> m c’
f
:: a -> b -> c -> d
lift2 f a b :: m (c -> d)
-- a’ == a, b’ == b, c’ == c -> d
У нас опять появился тип m (c -> d) и к нему нам нужно применить значение m c, чтобы получить m d.
Этим как раз и занимается функция $$. Итак итоговое определение примет вид:
lift3 :: Kleisli m => (a -> b -> c -> d) -> m a -> m b -> m c -> m d lift3 f a b c = lift2 f a b $$ c
Так мы можем определить любую функцию liftN через функции liftN-1 и $$.
Несколько полезных функций
Теперь мы умеем применять к специальным значениям произвольные обычные функции. Определим ещё
несколько полезных функций. Первая функция принимает список специальных значений и собирает их в
специальный список:
Применение функций | 95
import Prelude hiding (id, (>> ), pred, sequence)
sequence :: Kleisli m => [m a] -> m [a]
sequence = foldr (lift2 (:)) (idK [])
Мы “спрячем” из Prelude одноимённую функцию sequence. Посмотрим на примеры:
*Kleisli> sequence [Just 1, Just 2, Just 3]
Just [1,2,3]
*Kleisli> sequence [Just 1, Nothing, Just 3]
Nothing
Во второй команде вся функция вернула Nothing потому что при объединении списка встретилось зна-
чение Nothing, это равносильно тому, что мы объединяем в один список, значения полученные из функций,
которые могут не вычислить результат. Поскольку значение одного из элементов не определено, весь список
не определён.
Посмотрим как работает эта функция на списках:
*Kleisli> sequence [[1,2,3], [11,22]]
[[1,11],[1,22],[2,11],[2,22],[3,11],[3,22]]
Она составляет список всех комбинаций элементов из всех подсписков.
С помощью этой функции мы можем определить функцию mapK. Эта функция является аналогом обычной
функции map, но она применяет специальную функцию к списку значений.
mapK :: Kleisli m => (a -> m b) -> [a] -> m [b]
mapK f = sequence . map f
6.4 Функторы и монады
В этой главе мы выписали вручную все определения для класса Kleisli. Мы сделали это потому, что на
самом деле в арсенале стандартных средств Haskell такого класса нет. Класс Kleisli строит замкнутый мир
специальных функций a -> m b. Его цель построить язык в языке и сделать программирование со специ-
альными функциями таким же удобным как и с обычными функциями. Мы пользовались классом Kleisli
исключительно в целях облегчения понимания этого мира. Впрочем никто не мешает нам определить этот
класс и пользоваться им в наших программах.
А пока посмотрим, что есть в Haskell и как это соотносится с тем, что мы уже увидели. С помощью класса
Kleisli
мы научились делать три различных операции применения:
Применение:
• обычных функций одного аргумента к специальным значениям (функция +$).
• обычных функций произвольного числа аргументов к специальным значениям (функции +$ и $$)
• специальных функций к специальным значениям (функция *$).
В Haskell для решения этих задач предназначены три отдельных класса. Это функторы, аппликативные
функторы и монады.
Функторы
Посмотрим на определение класса Functor:
class Functor f where
fmap :: (a -> b) -> f a -> f b
Тип метода fmap совпадает с типом для функции +$:
(+$) :: Kleisli m => (a -> b) -> m a -> m b
Нам только нужно заменить m на f и зависимость от Kleisli на зависимость от Functor:
Итак в Haskell у нас есть базовая операция fmap применения обычной функции к значению из мира спе-
циальных функций. В модуле Control.Applicative определён инфиксный синоним <$> для этой функции.
96 | Глава 6: Функторы и монады: теория
Аппликативные функторы
Посмотрим на определение класса Applicative:
class Functor f => Applicative f where
pure
:: a -> f a
(<*> )
:: f (a -> b) -> f a -> f b
Если присмотреться к типам методов этого класса, то мы заметим, что это наши старые знакомые idK и
$$. Если для данного типа f определён экземпляр класса Applicative, то из контекста следует, что для него
также определён и экземпляр класса Functor.
Значит у нас есть функции fmap (или lift1) и <*> (или $$). С их помощью мы можем составить функции
liftN, которые поднимают обычные функции произвольного числа аргументов в мир специальных значений.
Класс Applicative определён в модуле Control.Applicative, там же мы сможем найти и функции liftA,
liftA2, liftA3 и символьный синоним <$> для функции fmap. Функции liftAn определены так:
liftA2 f a b
= f <$> a <*> b
liftA3 f a b c = f <$> a <*> b <*> c
Видно что эти определения с точностью до обозначений совпадают с теми, что мы уже писали для класса
Kleisli.
Монады
Посмотрим на определение класса Monad
class Monad m where
return :: a -> m a
(>>=)
:: m a -> (a -> m b) -> m b
Присмотримся к типам методов этого класса:
return :: a -> m a
Их типа видно, что это ни что иное как функция idK. В классе Monad у неё точно такой же смысл. Теперь
функция >>=, она читается как функция связывания (bind).
(>>=)
:: m a -> (a -> m b) -> m b
Так возможно совпадение не заметно, но давайте “перевернём” эту функцию:
(=<< )
:: Monad m => (a -> m b) -> m a -> m b
(=<< ) = flip (>>=)
Поменяв аргументы местами, мы получили знакомую функцию *$. Итак функция связывания это функция
применения специальной функции к специальному значению. У неё как раз такой смысл.
В Prelude определены экземпляры класса Monad для типов Maybe и [].
Они определены по такому же принципу, что и наши определения для Kleisli только не для композиции, а
для применения.
Отметим, что в модуле Control.Monad определены функции sequence и mapM, они несут тот же смысл,
что и функции sequence и mapК, которые мы определяли для класса Kleisli.
Свойства классов
Посмотрим на свойства функторов и аппликативных функторов.
Функторы и монады | 97
Свойства класса Functor
fmap id x
== x
-- тождество
fmap f . fmap g
== fmap (f . g)
-- композиция
Первое свойство говорит о том, что если мы применяем fmap к функции тождества, то мы должны снова
получить функцию тождества, или по другому можно сказать, что применение функции тождества к специ-
альному значению не изменяет это значение. Второе свойство говорит о том, что последовательное примене-
ние к специальному значению двух обычных функций можно записать в виде применения композиции двух
обычных функций к специальному значению.
Если всё это звучит туманно, попробуем переписать эти свойства в терминах композиции:
mf +> id
== mf
(mf +> g) +> h
== mf +> (g >> h)
Первое свойство говорит о том, что тождественная функция не изменяет значение при композиции. Вто-
рое свойство указывает на ассоциативность композиции одной специальной функции mf и двух обычных
функций g и h.
Свойства класса Applicative
Свойства класса Applicative, для наглядности они сформулированы не через методы класса, а через
производные функции.
fmap f x
== liftA f x
-- связь с Functor
liftA
id x
== x
-- тождество
liftA3 (. ) f g x
== f <*> (g <*> x)
-- композиция
liftA
f (pure x)
== pure (f x)
-- гомоморфизм
Первое свойство говорит о том, что применение специальной функции одного аргумента совпадает с
методом fmap из класса Functor. Свойство тождества идентично аналогичному свойству для класса Functor.
Свойство композиции сформулировано хитро, но давайте посмотрим на типы аргументов:
(. ) :: (b -> c) -> (a -> b) -> (a -> c)
f
:: m (b -> c)
g
:: m (a -> b)
x
:: m a
liftA3 (. ) f g x :: m c
g <*> x
:: m b
f (g <*> x)
:: m c
Слева в свойстве стоит liftA3, а не liftA2, потому что мы сначала применяем композицию (. ) к двум
функциям f и g, а затем применяем составную функцию к значению x.
Последнее свойство говорит о том, что если мы возьмём обычную функцию и обычное значение и подни-
мем их в мир специальных значений с помощью lift и pure, то это тоже самое если бы мы просто применили
бы функцию f к значению в мире обычных значений и затем подняли бы результат в мир специальных зна-
чений.
Полное определение классов
На самом деле я немного схитрил. Я рассказал вам только об основных методах классов Applicative
и Monad. Но они содержат ещё несколько дополнительных методов, которые выражаются через остальные.
Посмотрим на них, начнём с класса Applicative.
class Functor f => Applicative f where
-- | Поднимаем значение в мир специальных значений.
pure :: a -> f a
-- | Применение специального значения-функции.
(<*> ) :: f (a -> b) -> f a -> f b
-- | Константная функция. Отбрасываем первое значение.
98 | Глава 6: Функторы и монады: теория
(*> ) :: f a -> f b -> f b
(*> ) = liftA2 (const id)
-- | Константная функция, Отбрасываем второе значение.
(<*) :: f a -> f b -> f a
(<*) = liftA2 const
Два новых метода (*> ) и (<*) имеют смысл константных функций. Первая функция игнорирует значение
слева, а вторая функция игнорирует значение справа. Посмотрим как они работают в интерпретаторе:
Prelude Control.Applicative> Just 2 *> Just 3
Just 3
Prelude Control.Applicative> Nothing *> Just 3
Nothing
Prelude Control.Applicative> (const id) Nothing
Just 3
Just 3
Prelude Control.Applicative> [1,2] <* [1,2,3]
[1,1,1,2,2,2]
Значение игнорируется, но способ комбинирования специальных функций учитывается. Так во втором
выражении не смотря на то, что мы не учитываем конкретное значение Nothing, мы учитываем, что если один
из аргументов частично определённой функции не определён, то не определено всё значение. Сравните с
результатом выполнения следующего выражения.
По той же причине в последнем выражении мы получили три копии первого списка. Так произошло
потому, что второй список содержал три элемента. К каждому из элементов была применена функция const
x, где x пробегает по элементам списка слева от (<*).
Аналогичный метод есть и в классе Monad:
class
Monad m
where
return
:: a -> m a
(>>=)
:: m a -> (a -> m b) -> m b
(>> )
:: m a -> m b -> m b
fail
:: String -> m a
m >> k
= m >>= const k
fail s
= error s
Функция >> в классе Monad, которую мы прятали из-за символа композиции, является аналогом постоян-
ной функции в классе Monad. Она работает так же как и *> . Функция fail используется для служебных нужд
Haskell при выводе ошибок. Поэтому мы её здесь не рассматриваем. Для определения экземпляра класса
Monad достаточно определить методы return и >>=.
Исторические замечания
Напрашивается вопрос. Зачем нам функции return и pure или *> и >> ? Если вы заглянете в документа-
цию к модулю Control.Monad, то там вы найдёте функции liftM, liftM2, liftM3, которые выполняют те же
операции, что и аналогичные функции из модуля Control.Applicative.
Стандартные библиотеки устроены так, потому что класс Applicative появился гораздо позже класса
Monad. И к появлению этого нового класса уже накопилось огромное число библиотек, которые рассчитаны
на прежние имена. Но в будущем возможно прежние классы будут заменены на такие классы:
class Functor f where
fmap :: (a -> b) -> f a -> f b
class Pointed f where
pure :: a -> f a
class (Functor f, Pointed f) => Applicative f where
(<*> ) :: f (a -> b) -> f a -> f b
(*> )
:: f a -> f b -> f b
(<*)
:: f a -> f b -> f a
class Applicative f => Monad f where
(>>=) :: f a -> (a -> f b) -> f b
Функторы и монады | 99
6.5 Краткое содержание
В этой главе мы долгой обходной дорогой шли к понятию монады и функтора. Эти классы служат для
облегчения работы в мире специальных функций вида a -> m b, в категории Клейсли
С помощью класса Functor можно применять специальные значения к обычным функциям одного аргу-
мента:
class Functor f where
fmap :: (a -> b) -> f a -> f b
С помощью класса Applicative можно применять специальные значения к обычным функциям любого
числа аргументов:
class Functor f => Applicative f where
pure
:: a -> f a
<*>
:: f (a -> b) -> f a -> f b
liftA
:: Applicative f => (a -> b) -> f a -> f b
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
...
С помощью класса Monad можно применять специальные значения к специальным функциям.
class Monad m where
return
:: a -> m a
(>>=)
:: m a -> (a -> m b) -> m b
Функция return является функцией id в мире специальных функций, а функция >>= является функцией
применения ($), с обратным порядком следования аргументов. Вспомним также класс Kleisli, на примере
котором мы узнали много нового из жизни специальных функций:
class Kleisli m where
idK
:: a -> m a
(*> )
:: (a -> m b) -> (b -> m c) -> (a -> m c)
Мы узнали несколько стандартных специальных функций:
Частично определённые функции
a -> Maybe b
data Maybe a = Nothing | Just a
Многозначные функции
a -> [b]
data [a] = [] | a : [a]
6.6 Упражнения
В первых упражнениях вам предлагается по картинке специальной функции написать экземпляр классов
Kleisli и Monad.
Функции с состоянием
b
a
f
s
s
Рис. 6.6: Функция с состоянием
100 | Глава 6: Функторы и монады: теория
В Haskell нельзя изменять значения. Новые сложные значения описываются в терминах базовых значе-
ний. Но как же тогда мы сможем описать функцию с состоянием? Функцию, которая принимает на вход
значение, составляет результат на основе внутреннего состояния и значения аргумента и обновляет состоя-
ние. Поскольку мы не можем изменять состояние единственное, что нам остаётся – это принимать значение
состояния на вход вместе с аргументом и возвращать обновлённое состояние на выходе. У нас получится
такой тип:
a -> s -> (b, s)
Функция принимает одно значение типа a и состояние типа s, а возвращает пару, которая состоит из
результата типа b и обновлённого состояния. Если мы введём синоним:
type State s b = s -> (b, s)
И вспомним о частичном применении, то мы сможем записать тип функции с состоянием так:
a -> State s b
В Haskell пошли дальше и выделили для таких функций специальный тип:
data State s a = State (s -> (a, s))
runState :: State s a -> s -> (a, s)
runState (State f) = f
b
c
a
f
b
g
s
s
s
s
b
c
a
g
f
s
s
s
c
a
f*>g
s
s
Рис. 6.7: Композиция функций с состоянием
Функция runState просто извлекает функцию из оболочки State.
На (рис. 6.6) изображена схема функции с состоянием. В сравнении с обычной функцией у такой функции
один дополнительный выход и один дополнительный вход типа s. По ним течёт и изменяется состояние.
Попробуйте по схеме композиции для функций с состоянием написать экземпляры для классов Kleisli
и Monad для типа State s (рис. 6.7).
Подсказка: В этом определении есть одна хитрость, в отличае от типов Maybe и [a] у типа State два
параметра, это параметр состояния и параметр значения. Но мы делаем экземпляр не для State, а для State
s, то есть мы свяжем тип с некоторым произвольным типом s.
instance Kleisli (State s) where
...
Упражнения | 101
a
f
b
env
Рис. 6.8: Функция с окружением
Функции с окружением
Сначала мы рассмотрим функции с окружением. Функции с окружением – это такие функции, у которых
есть некоторое хранилище данных или окружение, из которых они могут читать информацию. Но в отличие
от функций с состоянием они не могут это окружение изменять. Функция с окружением похожа на функцию
с состоянием без одного выхода для состояния (рис. 6.8).
Функция с окружением принимает аргумент a и окружение env и возвращает результат b:
a -> env -> b
Как и в случае функций с состоянием выделим для функции с окружением отдельный тип. В Haskell он на-
зывается Reader (от англ. чтец). Все функции с окружением имеют возможность читать из общего хранилища
данных. Например они могут иметь доступ на чтение к общей базе данных.
data Reader env b = Reader (env -> b)
runReader :: Reader env b -> (env -> b)
runReader (Reader f) = f
Теперь функция с окружением примет вид:
a -> Reader env b
Определите для функций с окружением экземпляр класса Kleisli. У нас возникнет цепочка функций,
каждая из которых будет нуждаться в значении окружения. Поскольку окружение общее для всех функций
мы всем функциям передадим одно и то же значение (рис. 6.9).
a
f
b
b
g
c
env
env
b
a
g
f
c
env
a
f*>g
c
env
Рис. 6.9: Функция с окружением
Функции-накопители
Функции-накопители при вычислении за ширмой накапливают некоторое значение. Функция-накопитель
похожа на функцию с состоянием но без стрелки, по которой состояние подаётся в функцию (рис. 6.10).
Функция-накопитель имеет тип: a -> (b, msg)
Выделим результат функции в отдельный тип с именем Writer.
102 | Глава 6: Функторы и монады: теория
a
f
b
Msg
Рис. 6.10: Функция-накопитель
data Writer msg b = Writer (b, msg)
runWriter :: Writer msg b -> (b, msg)
runWriter (Writer a) = a
Тип функции примет вид:
a -> Writer msg b
Значения типа msg мы будем называть сообщениями. Смысл функций a -> Writer msg b заключается
в том, что при вычислении они накапливают в значении msg какую-нибудь информацию. Это могут быть
отладочные сообщения. Или база данных, которая открыта для всех функций на запись.
Класс Monoid
Как мы будем накапливать результат? Пока мы умеем лишь возвращать из функции пару значений. Одно
из них нам нужно передать в следующую функцию, а что делать с другим?
На помощь нам придёт класс Monoid, он определён в модуле Data.Monoid:
class Monoid a where
mempty
:: a
mappend :: a -> a -> a
В этом классе определено пустое значение mempty и бинарная функция соединения двух значений в одно.
Этот класс очень похож на класс Category и Kleisli. Там тоже было значение, которое ничего не делает и
операция составления нового значения из двух простейших значений. Даже свойства класса похожи:
mempty
‘mappend‘ f
= f
f
‘mappend‘ mempty
= f
f ‘mappend‘ (g ‘mappend‘ h) =
(f ‘mappend‘ g) ‘mappend‘ h
a
g
f
b
b
c
msg
msg
b
a
g
f
c
MsgG
++
MsgF ++ MsgG
MsgF
a
f*>g
c
msg
Рис. 6.11: Композиция функций-накопителей
Упражнения | 103
Первые два свойства говорят о том, что значение mempty и вправду является пустым элементом отно-
сительно операции mappend. А третье свойство говорит о том, что порядок при объединении элементов не
важен.
Посмотрим на определение экземпляра для списков:
instance Monoid [a] where
mempty
= []
mappend = (++)
Итак пустой элемент это пустой список, а объединение это операция конкатенации списков. Проверим в
интерпретаторе:
*Kleisli> :m Data.Monoid
Prelude Data.Monoid> [1 .. 4] ‘mappend‘ [4, 3 .. 1]
[1,2,3,4,4,3,2,1]
Prelude Data.Monoid> ”Hello” ‘mappend‘ ” World” ‘mappend‘ mempty
”Hello World”
Напишите экземпляр класса Kleisli для функций накопителей по (рис. 6.11). При этом будем считать,
что тип msg является экземпляром класса Monoid.
Экземпляры для функторов и монад
Представьте, что у нас нет класса Kleisli, а есть лишь Functor, Applicative и Monad. Напишите экзем-
пляры для этих классов для всех рассмотренных в этой главе специальных функций (в том числе и для Reader
и Writer). Экземпляры Functor и Applicative могут быть определены через Monad. Но для тренировки опре-
делите экземпляры полностью. Сначала Functor, затем Applicative и в последнюю очередь Monad.
Деревья
Напишите экземпляры классов Kleisli и Monad для двух типов, которые описывают деревья. Бинарные
деревья:
data BTree a = BList a | BNode a (BTree a) (BTree a)
Деревья с несколькими узлами:
data Tree a = Node a [Tree a]
Считайте, что списки являются частными случаями деревьев. В этом смысле деревья будут описывать
многозначные функции, которые возвращают несколько значений, организованных в иерархическую струк-
туру.
Стандартные функции
Почитайте документацию к модулям Control.Monad и Control.Applicative. Присмотритесь к функциям,
попробуйте применить их в интерпретаторе.
Эквивалентность классов Kleisli и Monad
Покажите, что классы Kleisli и Monad эквивалентны. Для этого нужно для произвольного типа c с одним
параметром m определить два экземпляра:
instance Kleisli m => Monad
m where
instance Monad
m => Kelisli m where
Нужно определить экземпляр одного класса с помощью методов другого.
Свойства класса Monad
Если класс Monad эквивалентен Kleisli, то в нём должны выполнятся точно такие же свойства. Запишите
свойства класса Kleisli через методы класса Monad
104 | Глава 6: Функторы и монады: теория
Глава 7
Функторы и монады: примеры
В этой главе мы закрепим на примерах то, что мы узнали о монадах и функторах. Напомню, что с по-
мощью монад и функторов мы можем комбинировать специальные функции вида (a -> m b) с другими
специальными функциями.
У нас есть функции тождества и применения:
class Functor f where
fmap :: (a -> b) -> f a -> f b
class Functor f => Applicative f where
pure
:: a -> f a
(<*> )
:: f (a -> b) -> f a -> f b
class Monad m where
return
:: a -> m a
(>>=)
:: m a -> (a -> m b) -> m b
(=<< ) :: (a -> m b) -> m a -> m b
(=<< ) = flip (>>=)
Вспомним основные производные функции для этих классов:
Или в терминах класса Kleisli:
-- Композиция
(>=> ) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
(<=< ) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
-- Константные функции
(*> ) :: Applicative f => f a -> f b -> f b
(<*) :: Applicative f => f a -> f b -> f a
-- Применение обычных функций к специальным значениям
(<$> )
:: Functor f => (a -> b) -> f a -> f b
liftA
:: Applicative f => (a -> b)
-> f a -> f b
liftA2 :: Applicative f => (a -> b -> c)
-> f a -> f b -> f c
liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
-- Преобразование элементов списка специальной функцией
mapM
:: Monad m => (a -> m b) -> [a] -> m [b]
Нам понадобится модуль с определениями типов и экземпляров монад для всех типов, которые мы рас-
смотрели в предыдущей главе. Экземпляры для [] и Maybe уже определены в Prelude, а типы State, Reader
и Writer можно найти в библиотеках mtl и transformers. Пока мы не знаем как устанавливать библиотеки
определим эти типы и экземпляры для Monad самостоятельно. Возможно вы уже определили их, выполняя
одно из упражнений предыдущей главы, если это так сейчас вы можете сверить ответы. Определим модуль
Types:
module Types(
State(.. ), Reader(.. ), Writer(.. ),
runState, runWriter, runReader,
| 105
module Control.Applicative,
module Control.Monad,
module Data.Monoid)
where
import Data.Monoid
import Control.Applicative
import Control.Monad
-------------------------------------------------
-- Функции с состоянием
--
--
a -> State s b
data State s a = State (s -> (a, s))
runState :: State s a -> s -> (a, s)
runState (State f) = f
instance Monad (State s) where
return a
= State $ \s -> (a, s)
ma >>= mf = State $ \s0 ->
let (b, s1) = runState ma s0
in
runState (mf b) s1
---------------------------------------------------
-- Функции с окружением
--
--
a -> Reader env b
data Reader env a = Reader (env -> a)
runReader :: Reader env a -> env -> a
runReader (Reader f) = f
instance Monad (Reader env) where
return a
= Reader $ const a
ma >>= mf
= Reader $ \env ->
let b = runReader ma env
in
runReader (mf b) env
---------------------------------------------------
-- Функции-накопители
--
--
Monoid msg => a -> Writer msg b
data Writer msg a = Writer (a, msg)
deriving (Show)
runWriter :: Writer msg a -> (a, msg)
runWriter (Writer f) = f
instance Monoid msg => Monad (Writer msg) where
return a
= Writer (a, mempty)
ma >>= mf
= Writer (c, msgA ‘mappend‘ msgF)
where (b, msgA) = runWriter ma
(c, msgF) = runWriter $ mf b
Я пропустил определения для экземпляров классов Functor и Applicative, их можно получить из экзем-
пляра для класса Monad с помощью стандартных функций liftM, return и ap из модуля Control.Monad.
Нам встретилась новая запись в экспорте модуля. Для удобства мы экспортируем модули
Control.Applicative, Control.Monad и Data.Monoid целиком. Для этого мы написали ключевое слово
module перед экспортируемым модулем. Теперь если мы в каком-нибудь другом модуле импортируем
модуль Types нам станут доступными все функции из этих модулей.
Мы определили экземпляры для Functor и Applicative с помощью производных функций класса Monad.
106 | Глава 7: Функторы и монады: примеры
7.1 Случайные числа
С помощью монады State можно имитировать случайные числа. Мы будем генерировать случайные числа
из интервала от 0 до 1 с помощью алгоритма:
nextRandom :: Double -> Double
nextRandom = snd . properFraction . (105.947 * )
Функция properFraction возвращает пару, которая состоит из целой части и остатка числа. Взяв второй
элемент пары с помощью snd, мы выделяем остаток. Функция nextRandom представляет собой генератор
случайных чисел, который принимает значение с предыдущего шага и строит по нему следующее значение.
Построим тип для случайных чисел:
type Random a = State Double a
next :: Random Double
next = State $ \s -> (s, nextRandom s)
Теперь определим функцию, которая прибавляет к данному числу случайное число из интервала от 0 до
1:
addRandom :: Double -> Random Double
addRandom x = fmap (+x) next
Посмотрим как эта функция работает в интерпретаторе:
*Random> runState (addRandom 5) 0.5
(5.5,0.9735000000000014)
*Random> runState (addRandom 5) 0.7
(5.7,0.16289999999999338)
*Random> runState (mapM addRandom [1 .. 5]) 0.5
([1.5,2.9735000000000014,3.139404500000154,4.769488561516319,
5.5250046269694195],0.6226652135290891)
В последней строчке мы с помощью функции mapM прибавили ко всем элементам списка разные случайные
числа, обновление счётчика происходило за кадром, с помощью функции mapM и экземпляра Monad для State.
Также мы можем определить функцию, которая складывает два случайных числа, одно из интервала
[-1+a, 1+a], а другое из интервала [-2+b,2+b]:
addRandom2 :: Double -> Double -> Random Double
addRandom2 a b = liftA2 add next next
where add
a b = \x y -> diap a 1 x + diap b 1 y
diap c r = \x
-> x * 2 * r - r + c
Функция diap перемещает интервал от 0 до 1 в интервал от c-r до c+r. Обратите внимание на то как мы
сначала составили обычную функцию add, которая перемещает значения из интервала от 0 до 1 в нужный
диапазон и складывает. И только в самый последний момент мы применили к этой функции случайные
значения. Посмотрим как работает эта функция:
*Random> runState (addRandom2 0 10) 0.5
(10.947000000000003,0.13940450000015403)
*Random> runState (addRandom2 0 10) 0.7
(9.725799999999987,0.2587662999992979)
Прибавим два списка и получим сумму:
*Random> let res = fmap sum $ zipWithM addRandom2 [1.. 3] [11 .. 13]
*Random> runState res 0.5
(43.060125804029965,0.969511377766409)
*Random> runState res 0.7
(39.86034841613788,0.26599261421101517)
Функция zipWithM является аналогом функции zipWith. Она устроена также как и функция mapM, сначала
применяется обычная функция zipWith, а затем функция sequence.
С помощью типа Random мы можем определить функцию подбрасывания монетки:
Случайные числа | 107
data Coin = Heads | Tails
deriving (Show)
dropCoin :: Random Coin
dropCoin = fmap drop’ next
where drop’ x
| x < 0.5
= Heads
| otherwise = Tails
У монетки две стороны орёл (Heads) и решка (Tails). Поскольку шансы на выпадание той или иной
стороны равны, мы для определения стороны разделяем интервал от 0 до 1 в равных пропорциях.
Подбросим монетку пять раз:
*Random> let res = sequence $ replicate 5 dropCoin
Функция replicate n a составляет список из n повторяющихся элементов a. Посмотрим что у нас полу-
чилось:
*Random> runState res 0.4
([Heads, Heads, Heads, Heads, Tails],0.5184926967068364)
*Random> runState res 0.5
([Tails, Tails, Heads, Tails, Tails],0.6226652135290891)
7.2 Конечные автоматы
С помощью монады State можно описывать конечные автоматы (finite-state machine). Конечный автомат
находится в каком-то начальном состоянии. Он принимает на вход ленту событий. Одно событие происходит
за другим. На каждое событие автомат реагирует переходом из одного состояния в другое.
type FSM s = State s s
fsm :: (ev -> s -> s) -> (ev -> FSM s)
fsm transition = \e -> State $ \s -> (s, transition e s)
Функция fsm принимает функцию переходов состояний transition и возвращает функцию, которая при-
нимает состояние и возвращает конечный автомат. В качестве значения конечный автомат FSM будет возвра-
щать текущее состояние.
С помощью конечных автоматов можно описывать различные устройства. Лентой событий будет ввод
пользователя (нажатие на кнопки, включение/выключение питания).
Приведём простой пример. Рассмотрим колонки, у них есть розетка, кнопка вкл/выкл и регулятор гром-
кости. Возможные состояния:
type Speaker = (SpeakerState, Level)
data SpeakerState = Sleep | Work
deriving (Show)
data Level
= Level Int
deriving (Show)
Тип колонок складывается из двух значений: состояния и уровня громкости. Колонки могут быть вы-
ключенными (Sleep) или работать на определённой громкости (Work). Считаем, что максимальный уровень
громкости составляет 10 единиц, а минимальный ноль единиц. Границы диапазона громкости описываются
такими функциями:
quieter :: Level -> Level
quieter (Level n) = Level $ max 0 (n-1)
louder :: Level -> Level
louder (Level n) = Level $ min 10 (n+1)
Мы будем обновлять значения уровня громкости не напрямую, а с помощью вспомогательных функций
louder и quieter. Так мы не сможем выйти за пределы заданного диапазона.
Возможные события:
108 | Глава 7: Функторы и монады: примеры
data User = Button | Quieter | Louder
deriving (Show)
Пользователь может либо нажать на кнопку вкл/выкл или повернуть реле громкости влево, чтобы при-
глушить звук (Quieter) или вправо, чтобы сделать погромче (Louder). Будем считать, что колонки всегда
включены в розетку.
Составим функцию переходов:
speaker :: User -> FSM Speaker
speaker = fsm $ trans
where trans Button
(Sleep, n) = (Work, n)
trans Button
(Work,
n) = (Sleep, n)
trans Louder
(s,
n) = (s, louder n)
trans Quieter
(s,
n) = (s, quieter n)
Мы считаем, что при выключении колонок реле остаётся некотором положении, так что при следующем
включении они будут работать на той же громкости. Реле можно крутить и в состоянии Sleep. Посмотрим
на типичную сессию работы колонок:
*FSM> let res = mapM speaker [Button, Louder, Quieter, Quieter, Button]
Сначала мы включаем колонки, затем прибавляем громкость, затем дважды делаем тише и в конце вы-
ключаем. Посмотрим что получилось:
*FSM> runState res (Sleep, Level 2)
([(Sleep, Level 2),(Work, Level 2),(Work, Level 3),(Work, Level 2),
(Work, Level 1)],(Sleep, Level 1))
*FSM> runState res (Sleep, Level 0)
([(Sleep, Level 0),(Work, Level 0),(Work, Level 1),(Work, Level 0),
(Work, Level 0)],(Sleep, Level 0))
Смотрите, изменив начальное значение, мы изменили весь список значений. Обратите внимание на то,
что во втором прогоне мы не ушли в минус по громкости, не смотря на то, что пытались крутить реле за
установленный предел.
Определим колонки другого типа. Наши новые колонки будут безопаснее предыдущих. Представьте си-
туацию, что мы выключили колонки на высоком уровне громкости. Мы слушали домашнюю запись с низким
уровнем звука. Мы выключили и забыли. Потом мы решили послушать другую мелодию, которая записана
с нормальным уровнем звука. При включении колонок нас оглушил шквал звука. Чтобы этого избежать мы
решили воспользоваться другими колонками.
Колонки при выключении будут выставлять уровень громкости на ноль и реле можно будет крутить
только если колонки включены.
safeSpeaker :: User -> FSM Speaker
safeSpeaker = fsm $ trans
where trans Button
(Sleep, _) = (Work,
Level 0)
trans Button
(Work,
_) = (Sleep, Level 0)
trans Quieter (Work,
n) = (Work,
quieter n)
trans Louder
(Work,
n) = (Work,
louder n)
trans _
(Sleep, n) = (Sleep, n)
При нажатии на кнопку вкл/выкл уровень громкости выводится в положение 0. Колонки реагируют на
запросы изменения уровня громкости только в состоянии Work. Посмотрим как работают наши новые колон-
ки:
*FSM> let res = mapM safeSpeaker [Button, Louder, Quieter, Button, Louder]
Мы включаем колонки, делаем по-громче, затем по-тише, затем выключаем и пытаемся изменить гром-
кость после выключения. Посмотрим как они сработают, представим, что мы выключили колонки на уровне
громкости 10:
*FSM> runState res (Sleep, Level 10)
([(Sleep, Level 10),(Work, Level 0),(Work, Level 1),(Work, Level 0),
(Sleep, Level 0)],(Sleep, Level 0))
Конечные автоматы | 109
Первое значение в списке является стартовым состоянием, которое мы задали. После этого колонки вклю-
чаются и мы видим, что уровень громкости переключился на ноль. Затем мы увеличиваем громкость, сбав-
ляем её и выключаем. Попытка изменить громкость выключенных колонок не проходит. Это видно по по-
следнему элементу списка и итоговому состоянию колонок, которое находится во втором элементе пары.
Предположим, что колонки работают с самого начала, тогда первым действием мы выключаем их. По-
смотрим, что случится дальше:
*FSM> runState res (Work, Level 10)
([(Work, Level 10),(Sleep, Level 0),(Sleep, Level 0),(Sleep, Level 0),
(Work, Level 0)],(Work, Level 1))
Дальше мы пытаемся изменить громкость но у нас ничего не выходит.
7.3 Отложенное вычисление выражений
В этом примере мы будем выполнять арифметические операции на целых числах. Мы будем их скла-
дывать, вычитать и умножать. Но вместо того, чтобы сразу вычислять выражения мы будем составлять их
описание. Мы будем кодировать операции конструкторами.
data Exp
= Var String
| Lit Int
| Neg Exp
| Add Exp Exp
| Mul Exp Exp
deriving (Show, Eq)
У нас есть тип Exp, который может быть либо переменной Var с данным строчным именем, либо целочис-
ленной константой Lit, либо одной из трёх операций: вычитанием (Neg), сложением (Add) или умножением
(Mul).
Такие типы называют абстрактными синтаксическими деревьями (abstract syntax tree, AST). Они содержат
описание выражений. Теперь вместо того чтобы сразу проводить вычисления мы будем собирать выражения
в значении типа Exp. Сделаем экземпляр для Num:
instance Num Exp where
negate
= Neg
(+)
= Add
(*)
= Mul
fromInteger = Lit . fromInteger
abs
= undefined
signum
= undefined
Также определим вспомогательные функции для обозначения переменных:
var :: String -> Exp
var = Var
n :: Int -> Exp
n = var . show
Функция var составляет переменную с данным именем, а функция n составляет переменную, у которой
имя является целым числом. Сохраним эти определения в модуле Exp. Теперь у нас всё готово для составле-
ния выражений:
*Exp> n 1
Var ”1”
*Exp> n 1 + 2
Add (Var ”1”) (Lit 2)
*Exp> 3 * (n 1 + 2)
Mul (Lit 3) (Add (Var ”1”) (Lit 2))
*Exp> - n 2 * 3 * (n 1 + 2)
Neg (Mul (Mul (Var ”2”) (Lit 3)) (Add (Var ”1”) (Lit 2)))
110 | Глава 7: Функторы и монады: примеры
Теперь давайте создадим функцию для вычисления таких выражений. Она будет принимать выражение
и возвращать целое число.
eval :: Exp -> Int
eval (Lit n)
= n
eval (Neg n)
= negate $ eval n
eval (Add a b)
= eval a + eval b
eval (Mul a b)
= eval a * eval b
eval (Var name) = ???
Как быть с конструктором Var? Нам нужно откуда-то узнать какое значение связано с переменной. Функ-
ция eval должна также принимать набор значений для всех переменных, которые используются в выражении.
Этот набор значений мы будем называть окружением.
Обратите внимание на то, что в каждом составном конструкторе мы рекурсивно вызываем функцию eval,
мы словно обходим всё дерево выражения. Спускаемся вниз, до самых листьев в которых расположены либо
значения (Lit), либо переменные (Var). Нам было бы удобно иметь возможность пользоваться окружением
из любого узла дерева. В этом нам поможет тип Reader.
Представим что у нас есть значение типа Env и функция, которая позволяет читать значения переменных
по имени:
value :: Env -> String -> Int
Теперь определим функцию eval:
eval :: Exp -> Reader Env Int
eval (Lit n)
= pure n
eval (Neg n)
= liftA
negate $ eval n
eval (Add a b)
= liftA2 (+) (eval a) (eval b)
eval (Mul a b)
= liftA2 (*) (eval a) (eval b)
eval (Var name) = Reader $ \env -> value env name
Определение сильно изменилось, оно стало не таким наглядным. Теперь значение eval стало специаль-
ным, поэтому при рекурсивном вызове функции eval нам приходится поднимать в мир специальных функций
обычные функции вычитания, сложения и умножения. Мы можем записать это выражение
немного по другому:
eval :: Exp -> Reader Env Int
eval (Lit n)
= pure n
eval (Neg n)
= negateA $ eval n
eval (Add a b)
= eval a ‘addA‘ eval b
eval (Mul a b)
= eval a ‘mulA‘ eval b
eval (Var name) = Reader $ \env -> value env name
addA
= liftA2 (+)
mulA
= liftA2 (*)
negateA
= liftA negate
Тип Map
Для того чтобы закончить определение функции eval нам нужно определить тип Env и функцию value.
Для этого мы воспользуемся типом Map, он предназначен для хранения значений по ключу.
Этот тип живёт в стандартном модуле Data.Map. Посмотрим на его описание:
data Map k a = ..
Первый параметр типа k это ключ, а второй это значение. Мы можем создать значение типа Map из списка
пар ключ значение с помощью функции fromList.
Посмотрим на основные функции:
-- Создаём значения типа Map
-- создаём
empty :: Map k a
-- пустой Map
fromList :: Ord k => [(k, a)] -> Map k a
-- по списку (ключ, значение)
-- Узнаём значение по ключу
(! )
:: Ord k => Map k a -> k -> a
Отложенное вычисление выражений | 111
lookup
:: Ord k => k -> Map k a -> Maybe a
-- Добавляем элементы
insert :: Ord k => k -> a -> Map k a -> Map k a
-- Удаляем элементы
delete :: Ord k => k -> Map k a -> Map k a
Обратите внимание на ограничение Ord k в этих функциях, ключ должен быть экземпляром класса Ord.
Посмотрим как эти функции работают:
*Exp> :m +Data.Map
*Exp Data.Map> :m -Exp
Data.Map> let v = fromList [(1, ”Hello”), (2, ”Bye”)]
Data.Map> v ! 1
”Hello”
Data.Map> v ! 3
”*** Exception: Map.find: element not in the map
Data.Map> lookup 3 v
Nothing
Data.Map> let v1 = insert 3 ” Yo” v
Data.Map> v1 ! 3
” Yo”
Функция lookup является стабильным аналогом функции ! . В том смысле, что она определена с помощью
Maybe. Она не приведёт к падению программы, если для данного ключа не найдётся значение.
Теперь мы можем определить функцию value:
import qualified Data.Map as M(Map, lookup, fromList)
...
type Env = M.Map String Int
value :: Env -> String -> Int
value env name = maybe errorMsg $ M. lookup env name
where errorMsg = error $ ”value is undefined for ” ++ name
Обычно функции из модуля Data.Map включаются с директивой qualified, поскольку имена многих
функций из этого модуля совпадают с именами из модуля Prelude. Теперь все определения из модуля
Data.Map пишутся с приставкой M. .
Создадим вспомогательную функцию, которая упростит вычисление выражений:
runExp :: Exp -> [(String, Int)] -> Int
runExp a env = runReader (eval a) $ M. fromList env
Сохраним определение новых функций в модуле Exp. И посмотрим что у нас получилось:
*Exp> let env a b = [(”1”, a), (”2”, b)]
*Exp> let exp = 2 * (n 1 + n 2) - n 1
*Exp> runExp exp (env 1 2)
5
*Exp> runExp exp (env 10 5)
20
Так мы можем пользоваться функциями с окружением для того, чтобы читать значения из общего ис-
точника. Впрочем мы можем просто передавать окружение дополнительным аргументом и не пользоваться
монадами:
eval :: Env -> Exp -> Int
eval env x = case x of
Lit n
-> n
Neg n
-> negate $ eval’ n
Add a b
-> eval’ a + eval’ b
Mul a b
-> eval’ a + eval’ b
Var name
-> value env name
where eval’ = eval env
112 | Глава 7: Функторы и монады: примеры
7.4 Накопление результата
Рассмотрим по-подробнее тип Writer. Он выполняет задачу обратную к типу Reader. Когда мы пользова-
лись типом Reader, мы могли в любом месте функции извлекать данные из окружения. Теперь же мы будем
не извлекать данные из окружения, а записывать их.
Рассмотрим такую задачу нам нужно обойти дерево типа Exp и подсчитать все бинарные операции. Мы
прибавляем к накопителю результата единицу за каждый конструктор Add или Mul. Тип сообщений будет
числом. Нам нужно сделать экземпляр класса Monoid для чисел.
Напомню, что тип накопителя должен быть экземпляром класса Monoid:
class Monoid a where
mempty
:: a
mappend :: a -> a -> a
mconcat :: [a] -> a
mconcat = foldr mappend mempty
Но для чисел возможно несколько вариантов, которые удовлетворяют свойствам. Для сложения:
instance Num a => Monoid a where
mempty
= 0
mappend = (+)
И умножения:
instance Num a => Monoid a where
mempty
= 1
mappend = (*)
Для нашей задачи подойдёт первый вариант, но не исключена возможность того, что для другой зада-
чи нам понадобится второй. Но тогда мы уже не сможем определить такой экземпляр. Для решения этой
проблемы в модуле Data.Monoid определено два типа обёртки:
newtype Sum
a = Sum
{ getSum
:: a }
newtype Prod a = Prod { getProd :: a }
В этом определении есть два новых элемента. Первый это ключевое слово newtype, а второй это фигурные
скобки. Что всё это значит?
Тип-обёртка newtype
Ключевое слово newtype вводит новый тип-обёртку. Тип-обёртка может иметь только один конструктор,
у которого лишь одни аргумент. Запись:
newtype Sum a = Sum a
Это тоже самое, что и
data Sum a = Sum a
Единственное отличие заключается в том, что в случае newtype вычислитель не видит разницы между
Sum a и a. Её видит лишь компилятор. Это означает, что на разворачивание и заворачивание такого значения
в тип обёртку не тратится никаких усилий. Такие типы подходят для решения двух задач:
• Более точная проверка типов.
Например у нас есть типы, которые описывают физические величины, все они являются числами, но у
них также есть и размерности. Мы можем написать:
type Velocity
= Double
type Time
= Double
type Length
= Double
velocity :: Length -> Time -> Velocity
velocity leng time = leng / time
Накопление результата | 113
В этом случае мы спокойно можем подставить на место времени путь и наоборот. Но с помощью типов
обёрток мы можем исключить эти случаи:
newtype Velocity
= Velocity
Double
newtype Time
= Time
Double
newtype Length
= Length
Double
velocity :: Length -> Time -> Velocity
velocity (Length leng) (Time time) = Velocity $ leng / time
В этом случае мы проводим проверку по размерностям, компилятор не допустит смешивания данных.
• Определение нескольких экземпляров одного класса для одного типа. Этот случай мы как раз и рас-
сматриваем для класса Monoid. Нам нужно сделать два экземпляра для одного и того же типа Num a
=> a.
Сделаем две обёртки!
newtype Sum
a = Sum
a
newtype Prod a = Prod a
Тогда мы можем определить два экземпляра для двух разных типов:
Один для Sum:
instance Num a => Monoid (Sum a) where
mempty
= Sum 0
mappend (Sum a) (Sum b) = Sum (a + b)
А другой для Prod:
instance Num a => Monoid (Prod a) where
mempty
= Prod 1
mappend (Prod a) (Prod b) = Prod (a * b)
Записи
Вторая новинка заключалась в фигурных скобках. С помощью фигурных скобок в Haskell обозначаются
записи (records). Запись это произведение типа, но с выделенными именами для полей.
Например мы можем сделать тип для описания паспорта:
data Passport
= Person {
surname
:: String,
-- Фамилия
givenName
:: String,
-- Имя
nationality
:: String,
-- Национальность
dateOfBirth
:: Date,
-- Дата рождения
sex
:: Bool,
-- Пол
placeOfBirth
:: String,
-- Место рождения
authority
:: String,
-- Место выдачи документа
dateOfIssue
:: Date,
-- Дата выдачи
dateOfExpiry
:: Date
-- Дата окончания срока
} deriving (Eq, Show)
--
действия
data Date
= Date {
day
:: Int,
month
:: Int,
year
:: Int
} deriving (Show, Eq)
В фигурных скобках через запятую мы указываем поля. Поле состоит из имени и типа. Теперь нам до-
ступны две операции:
• Чтение полей
hello :: Passport -> String
hello p = ”Hello, ” ++ givenName p ++ ”!”
114 | Глава 7: Функторы и монады: примеры
Для чтения мы просто подставляем в имя поля данное значение. В этой функции мы приветствуем
человека и обращаемся к нему по имени. Для того, чтобы узнать его имя мы подсмотрели в паспорт, в
поле givenName.
• Обновление полей. Для обновления полей мы пользуемся таким синтаксисом:
value { fieldName1 = newValue1, fieldName2 = newValue2, ... }
Мы присваиваем в значении value полю с именем fieldName новое значение newFieldValue. К примеру
продлим срок действия паспорта на десять лет:
prolongate :: Passport -> Passport
prolongate p = p{ dateOfExpiry = newDate }
where newDate = oldDate { year = year oldDate + 10 }
oldDate = dateOfExpiry p
Вернёмся к типам Sum и Prod:
newtype Sum
a = Sum
{ getSum
:: a }
newtype Prod a = Prod { getProd :: a }
Этой записью мы определили два типа-обёртки. У нас есть две функции, которые заворачивают обычное
значение, это Sum и Prod. С помощью записей мы тут же в определении типа определили функции которые
разворачивают значения, это getSum и getProd.
Вспомним определение для типа State:
data State s a = State (s -> (a, s))
runState :: State s a -> (s -> (a, s))
runState (State f) = f
Было бы гораздо лучше определить его так:
newtype State s a = State{ runState :: s -> (a, s) }
Накопление чисел
Но вернёмся к нашей задаче. Мы будем накапливать сумму в значении типа Sum. Поскольку нас интере-
сует лишь значение накопителя, наша функция будет возвращать значение единичного типа ().
countBiFuns :: Exp -> Int
countBiFuns = getSum . execWriter . countBiFuns’
countBiFuns’ :: Exp -> Writer (Sum Int) ()
countBiFuns’ x = case x of
Add a b -> tell (Sum 1) *> bi a b
Mul a b -> tell (Sum 1) *> bi a b
Neg a
-> un a
_
-> pure ()
where bi a b = countBiFuns’ a *> countBiFuns’ b
un
= countBiFuns’
tell :: Monoid a => a -> Writer a ()
tell a = Writer ((), a)
execWriter :: Writer msg a -> msg
execWriter (Writer (a, msg)) = msg
Первая функция countBiFuns извлекает значение из типов Writer и Sum. А вторая функция countBiFuns’
вычисляет значение.
Мы определили две вспомогательные функции tell, которая записывает сообщение в накопитель и
execWriter, которая возвращает лишь сообщение. Это стандартные для Writer функции.
Посмотрим как работает эта функция:
*Exp> countBiFuns (n 2)
0
*Exp> countBiFuns (n 2 + n 1 + 2 + 3)
3
Накопление результата | 115
Накопление логических значений
В модуле Data.Monoid определены два типа для накопления логических значений. Это типы All и Any. С
помощью типа All мы можем проверить выполняется ли некоторое свойство для всех значений. А с помощью
типа Any мы можем узнать, что существует хотя бы один элемент, для которых это свойство выполнено.
Посмотрим на определение экземпляров класса Monoid для этих типов:
newtype All = All { getAll :: Bool }
instance Monoid All where
mempty = All True
All x ‘mappend‘ All y = All (x && y)
В типе All мы накапливаем значения с помощью логического “и”. Нейтральным элементом является кон-
структор True. Итоговое значение накопителя будет равно True только в том случае, если все накапливаемые
сообщения были равны True.
В типе Any всё наоборот:
instance Monoid Any where
mempty = Any False
Any x ‘mappend‘ Any y = Any (x || y)
Посмотрим как работают эти типы. Составим функцию, которая проверяет отсутствие оператора минус
в выражении:
noNeg :: Exp -> Bool
noNeg = not . getAny . execWriter . anyNeg
anyNeg :: Exp -> Writer Any ()
anyNeg x = case x of
Neg _
-> tell (Any True)
Add a b -> bi a b
Mul a b -> bi a b
_
-> pure ()
where bi a b = anyNeg a *> anyNeg b
Функция anyNeg проверяет есть ли в выражении хотя бы один конструктор Neg. В функции noNeg мы
извлекаем результат и берём его отрицание, чтобы убедиться в том что в выражении не встретилось ни
одного конструктора Neg.
*Exp> noNeg (n 2 + n 1 + 2 + 3)
True
*Exp> noNeg (n 2 - n 1 + 2 + 3)
False
Накопление списков
Экземпляр класса Monoid определён и для списков. Предположим у нас есть дерево, в каждом узле кото-
рого находятся числа, давайте соберём все числа больше 5, но меньше 10. Деревья мы возьмём из модуля
Data.Tree:
data Tree a
= Node
{ rootLabel :: a
-- значение метки
, subForest :: Forest a
-- ноль или несколько дочерних деревьев
}
type Forest a = [Tree a]
Интересный тип. Тип Tree определён через Forest, а Forest определён через Tree. По этому типу мы
видим, что каждый узел содержит некоторое значение типа a, и список дочерних деревьев.
Составим дерево:
*Exp> :m Data.Tree
Prelude Data.Tree> let t a = Node a []
Prelude Data.Tree> let list a = Node a []
Prelude Data.Tree> let bi v a b = Node v [a, b]
Prelude Data.Tree> let un v a
= Node v [a]
Prelude Data.Tree>
Prelude Data.Tree> let tree1 = bi 10 (un 2 $ un 6 $ list 7) (list 5)
Prelude Data.Tree> let tree2 = bi 12 tree1 (bi 8 tree1 tree1)
116 | Глава 7: Функторы и монады: примеры
Теперь составим функцию, которая будет обходить дерево, и собирать числа из заданного диапазона:
type Diap a = (a, a)
inDiap :: Ord a => Diap a -> Tree a -> [a]
inDiap d = execWriter . inDiap’ d
inDiap’ :: Ord a => Diap a -> Tree a -> Writer [a] ()
inDiap’ d (Node v xs) = pick d v *> mapM_ (inDiap’ d) xs
where pick (a, b) v
| (a <= v) && (v <= b)
= tell [v]
| otherwise
= pure ()
Как и раньше у нас две функции, одна выполняет вычисления, другая извлекает результат из Writer. В
функции pick мы проверяем число на принадлежность интервалу, если это так мы добавляем число к резуль-
тату, а если нет пропускаем его, добавляя нейтральный элемент (в функции pure). Обратите внимание на то
как мы обрабатываем список дочерних поддервьев. Функция mapM_ является аналогом функции mapM, Она ис-
пользуется, если результат функции не важен, а важны те действия, которые происходят при преобразовании
списка. В нашем случае это накопление результата. Посмотрим на определение этой функции:
mapM_ :: Monad m => (a -> m b) ->
[a] -> m ()
mapM_ f = sequence_ . map f
sequence_ :: Monad m => [m a] -> m ()
sequence_ = foldr (>> ) (return ())
Основное отличие состоит в функции sequence_. Раньше мы собирали значения в список, а теперь отбра-
сываем их с помощью константной функции >> . В конце мы возвращаем значение единичного типа ().
Теперь сохраним в модуле Tree определение функции и вспомогательные функции создания деревьев
un, bi, и list и посмотрим как наша функция работает:
*Tree> inDiap (4, 10) tree2
[10,6,7,5,8,10,6,7,5,10,6,7,5]
*Tree> inDiap (5, 8) tree2
[6,7,5,8,6,7,5,6,7,5]
*Tree> inDiap (0, 3) tree2
[2,2,2]
7.5 Монада изменяемых значений ST
Возможно читатели, для которых “родным” является один из императивных языков, немного заскучали
по изменяемым значениям. Мы говорили, что в Haskell ничего не изменяется, мы даём всё более и более
сложные имена статическим значениям, а потом вычислитель редуцирует имена к настоящим значениям.
Но есть алгоритмы, которые очень элегантно описываются в терминах изменяемых значений. Примером
такого алгоритма может быть быстрая сортировка. Задача состоит в перестановке элементов массива так,
чтобы на выходе любой последующий элемент массива был больше предыдущего (для списков эту задачу
решают функции sort и sortBy).
Само по себе явление обновления значения является побочным эффектом. Оно ломает представление о
статичности мира, у нас появляются фазы: до обновления и после обновления. Но представьте, что обнов-
ление происходит локально, мы постоянно меняем только одно значение, при этом за время обновления ни
одна другая переменная не может пользоваться промежуточными значениями и обновления происходят с
помощью чистых функций. Представьте функцию, которая принимает значение, выделяет внутри себя па-
мять, и при построении результата начинает обновлять значение внутри этой памяти (с помощью чистых
функций) и считать что-то ещё полезное на основе этих обновлений, как только вычисления закончатся, па-
мять стирается, и возвращается значение. Будет ли такая функция чистой? Интуиция подсказывает, что да.
Это было доказано, но для реализации этого требуется небольшой трюк на уровне типов. Получается, что
не смотря на то, что функция содержит побочные эффекты, она является чистой, поскольку все побочные
эффекты локальны, они происходят только внутри вызова функции и только в самой функции.
Для симуляции обновления значения в Haskell нам нужно решить две проблемы. Как упорядочить обнов-
ление значения? И как локализовать его? В императивных языках порядок вычисления выражений строго
связан с порядком следования выражений, на примитивном уровне, грубо упрощая, можно сказать, что вы-
числитель читает код как ленту и выполняет выражение за выражением. В Haskell всё совсем по-другому. Мы
можем писать функции в любом порядке, также в любом порядке мы можем объявлять локальные перемен-
ные в where или let-выражениях. Компилятор определяет порядок редукции синонимов по функциональным
Монада изменяемых значений ST | 117
зависимостям. Синоним f не будет раскрыт раньше синонима g только в том случае, если результат g тре-
буется в f. Но с обновлением значения этот вариант не пройдёт, посмотрим на выражение:
fun :: Int -> Int
fun arg =
let mem = new arg
x
= read mem
y
= x + 1
??
= write mem y
z
= read mem
in z
Предполагается, что в этой функции мы получаем значение arg, выделяем память mem c помощью спе-
циальной функции new, которая принимает начальное значение, которое будет храниться в памяти. Затем
читаем из памяти, прибавляем к значению единицу, снова записываем в память, потом опять читаем из па-
мяти, сохранив значение в переменной z, и в самом конце возвращаем ответ. Налицо две проблемы: z не
зависит от y, поэтому мы можем считать значение z в любой момент после инициализации памяти и вторая
проблема: что должна возвращать функция write?
Для того чтобы упорядочить эти вычисления мы воспользуемся типом State. Каждое выражение будет
принимать фиктивное состояние и возвращать его. Тогда функция fun запишется так:
fun :: Int -> State s Int
fun arg = State $ \s0 ->
let (mem, s1)
= runState (new arg)
s0
((),
s2)
= runState (write mem arg)
s1
(x,
s3)
= runState (read mem)
s2
y
= x + 1
((),
s4)
= runState (write mem y)
s3
(z,
s5)
= runState (read mem)
s4
in (z, s5)
new
:: a -> State s (Mem a)
write
:: Mem a -> a -> State s ()
read
:: Mem a -> State s a
Тип Mem параметризован типом значения, которое хранится в памяти. В этом варианте мы не можем
изменить порядок следования выражений, поскольку нам приходится передовать состояние. Мы могли бы
записать это выражение гораздо короче с помощью методов класса Monad, но мне хотелось подчеркнуть как
передача состояния навязывает порядок вычисления. Функция write теперь возвращает пустой кортеж. Но
порядок не теряется за счёт состояния. Пустой кортеж намекает на то, что единственное назначение функции
write – это обновление состояния.
Однако этого не достаточно. Мы хотим, чтобы обновление значения было скрыто от пользователя в чистой
функции. Мы хотим, чтобы тип функции fun не содержал типа State. Для этого нам откуда-то нужно взять
начальное значение состояния. Мы можем решить эту проблему, зафиксировав тип s. Пусть это будет тип
FakeState, скрытый от пользователя.
module Mutable(
Mutable, Mem, purge,
new, read, write)
where
newtype Mutable a = Mutable (State FakeState a)
data FakeState = FakeState
purge :: Mutable a -> a
purge (Mutable a) = fst $ runState a FakeState
new
:: a -> Mutable (Mem a)
read
:: Mem a -> Mutable a
write
:: Mem a -> a -> Mutable ()
Мы предоставим пользователю лишь тип Mutable без конструктора и функцию purge, которая “очища-
ет” значение от побочных эффектов и примитивные функции для работы с памятью. Также мы определим
экземпляры классов типа State для Mutable, сделать это будет совсем не трудно, ведь Mutable – это просто
118 | Глава 7: Функторы и монады: примеры
обёртка. С помощью этих экземпляров пользователь сможет комбинировать вычисления, которые связаны с
изменением памяти. Пока вроде всё хорошо, но обеспечиваем ли мы локальность изменения значений? Нам
важно, чтобы, один раз начав работать с памятью типа Mem, мы не смогли бы нигде воспользоваться этой па-
мятью после выполнения функции purge. Оказывается, что мы можем разрушить локальность. Посмотрите
на пример:
let mem = purge allocate
in
purge (read mem)
Мы возвращаем из функции purge ссылку на память и спокойно пользуемся ею в другой ветке Mutable-
вычислений. Можно ли этого избежать? Оказывается, что можно. Причём решение весьма элегантно. Мы
можем построить типы Mem и Mutable так, чтобы ссылке на память не удалось просочиться через функцию
purge. Для этого мы вернёмся к общему типу State c двумя параметрами. Причём первый первый параметр
мы прицепим и к Mem:
data
Mem
s a = ..
newtype Mutable s a = ..
new
:: a -> Mutable s (Mem s a)
write
:: Mem s a -> a -> Mutable s ()
read
:: Mem s a -> Mutable s a
Теперь при создании типы Mem и Mutable связаны общим параметром s. Посмотрим на тип функции purge
purge :: (forall s. Mutable s a) -> a
Она имеет необычный тип. Слово forall означает “для любых”. Это слово называют квантором всеобщ-
ности. Этим мы говорим, что функция извлечения значения не может делать никаких предположений о типе
фиктивного состояния. Как дополнительный forall может нам помочь? Функция purge забывает тип фик-
тивного состояния s из типа Mutable, но в случае типа Mem, этот параметр продолжает своё путешествие по
программе в типе значения v :: Mem s a. По типу v компилятор может сказать, что существует такое s,
для которого значение v имеет смысл (правильно типизировано). Но оно не любое! Функцию purge с трю-
ком интересует не некоторый тип, а все возможные типы s, поэтому пример не пройдёт проверку типов.
Компилятор будет следить за “чистотой” наших обновлений.
При таком подходе остаётся вопрос: откуда мы возьмём начальное значение, ведь теперь у нас нет типа
FakeState? В Haskell специально для этого типа было сделано исключение. Мы возьмём его из воздуха. Это
чисто фиктивный параметр, нам главное, что он скрыт от пользователя, и он нигде не может им воспользо-
ваться. Поскольку у нас нет конструктора Mutable мы никогда не сможем добраться до внутренней функции
типа State и извлечь состояние. Состояние скрыто за интерфейсом класса Monad и отбрасывается в функции
purge.
Тип ST
Выше я пользовался вымышленными типами для упрощения объяснений, на самом деле в Haskell за об-
новление значений отвечает тип ST (сокращение от state transformer). Он живёт в модуле Control.Monad.ST.
Из документации видно, что у него два параметра, и нет конструкторов:
data ST s a
Это наш тип Mutable, теперь посмотрим на тип Mem. Он называется ST-ссылкой и определён в модуле
Data.STRef (сокращение от ST reference). Посмотрим на основные функции:
newSTRef
:: a -> ST s (STRef s a)
readSTRef
:: STRef s a -> ST s a
writeSTRef
:: STRef s a -> a -> ST s ()
Такие функции иногда называют смышлёными конструкторами (smart constructors) они позволяют строить
значение, но скрывают от пользователя реализацию за счёт скрытия конструкторов типа (модуль экспорти-
рует лишь имя типа STRef).
Для иллюстрации этих функций реализуем одну вспомогательную функцию из модуля Data.STRef, функ-
цию обновления значения по ссылке:
modifySTRef :: STRef s a -> (a -> a) -> ST s ()
modifySTRef ref f = writeSTRef . f =<< readSTRef ref
Мы воспользовались тем, что ST является экземпляром Monad. Также как и для State для ST определены
экземпляры классов Functor, Applicative и Monad. Какое совпадение! Посмотрим на функцию purge:
runST :: (forall s. ST s a) -> a
Монада изменяемых значений ST | 119
Императивные циклы
Реализуем for цикл из языка C:
Result s;
for (i = 0 ; i < n; i++)
update(i, s);
return s;
У нас есть стартовое значение счётчика и результата, функция обновления счётчика, предикат останова и
функция обновления результата. Мы инициализируем счётчик и затем обновляем счётчик и состояние до тех
пор пока предикат счётчика не станет ложным. Напишем чистую функцию, которая реализует этот процесс. В
этой функции мы воспользуемся специальным синтаксическим сахаром, который называется do-нотация, не
пугайтесь это всё ещё Haskell, для понимания этого примера загляните в раздел “сахар для монад” главы~17.
module Loop where
import Control.Monad
import Data.STRef
import Control.Monad.ST
forLoop ::
i -> (i -> Bool) -> (i -> i) -> (i -> s -> s) -> s -> s
forLoop i0 pred next update s0 = runST $ do
refI <- newSTRef i0
refS <- newSTRef s0
iter refI refS
readSTRef refS
where iter refI refS = do
i <- readSTRef refI
s <- readSTRef refS
when (pred i) $ do
writeSTRef refI $ next i
writeSTRef refS $ update i s
iter refI refS
Впрочем код выше можно понять если читать его как обычный императивный код. Выражения do-блока
выполняются последовательно, одно за другим. Сначала мы инициализируем два изменяемых значения, для
счётчика цикла и для состояния. Затем в функции iter мы читаем значения и выполняем проверку предиката
pred. Функция when – это стандартная функция из модуля Control.Monad. Она проверяет предикат, и если
он возвращает True выполняет серию действий, в которых мы записываем обновлённые значения. Обратите
внимание на то, что связка when-do это не специальная конструкция языка. Как было сказано when – это
просто функция, но она ожидает одно действие, а мы хотим выполнить сразу несколько. Следующее за ней
do начинает блок действий (границы блока определяются по отступам), который будет интерпретироваться
как одно действие. В настоящем императивном цикле в обновлении и предикате счётчика может участвовать
переменная результата, но это считается признаком дурного стиля, поэтому наши функции определены на
типе счётчика. Решим типичную задачу, посчитаем числа от одного до десяти:
*Loop> forLoop 1 (<=10) succ (+) 0
55
Посчитаем факториал:
*Loop> forLoop 1 (<=10) succ (*) 1
3628800
*Loop> forLoop 1 (<=100) succ (*) 1
9332621544394415268169923885626670049071596826
4381621468592963895217599993229915608941463976
1565182862536979208272237582511852109168640000
00000000000000000000
Теперь напишем while-цикл:
120 | Глава 7: Функторы и монады: примеры
Result s;
while (pred(s))
update(s);
return s;
В этом цикле участвует один предикат и одна функция обновления результата, мы обновляем результат
до тех пор пока предикат не станет ложным.
whileLoop :: (s -> Bool) -> (s -> s) -> s -> s
whileLoop pred update s0 = runST $ do
ref <- newSTRef s0
iter ref
readSTRef ref
where iter ref = do
s <- readSTRef ref
when (pred s) $ do
writeSTRef ref $ update s
iter ref
Посчитаем сумму чисел через while-цикл:
*Loop> whileLoop ((> 0) . fst) (\(n, s) -> (pred n, n + s)) (10, 0)
(0,55)
Первый элемент пары играет роль счётчика, а во втором мы накапливаем результат.
Быстрая сортировка
Реализуем императивный алгоритм быстрой сортировки. Алгоритм быстрой сортировки хорош не только
тем, что он работает очень быстро, но и минимальным расходом памяти. Сортировка проводится в самом
массиве, с помощью обмена элементов местами. Но для этого нам понадобятся изменяемые массивы. Этот
тип определён в модуле Data.Array.ST. В Haskell есть несколько типов изменяемых массивов (как впрочем и
неизменяемых), это связано с различными нюансами размещения элементов в массивах, о которых мы пока
умолчим. Для предостваления общего интерфейса к различным массивам был определён класс:
class (HasBounds a, Monad m) => MArray a e m where
newArray
:: Ix i => (i, i) -> e -> m (a i e)
newArray_ :: Ix i => (i, i) -> m (a i e)
MArray – это сокращение от mutable (изменяемый) array. Метод newArray создёт массив типа a, который
завёрнут в тип-монаду m. Первый аргумент указывает на диапазон значений индексов массива, а вторым
аргументом передаётся элемент, который будет записан во все ячейки массива. Вторая функция записывает
в массив элемент undefined.
Посмотрим на вспомогательные классы:
class Ord a => Ix a where
range :: (a, a) -> [a]
index :: (a, a) -> a -> Int
inRange :: (a, a) -> a -> Bool
rangeSize :: (a, a) -> Int
class HasBounds a where
bounds :: Ix i => a i e -> (i, i)
Класс Ix описывает тип индекса из непрерывного диапазона значений. Наверняка по имени функции
и типу вы догадаетесь о назначении методов (можете свериться с интерпретатором на типах Int или (Int,
Int)). Класс HasBounds обозначает массивы размер, которых фиксирован. Но вернёмся к массивам. Мы можем
не только выделять память под массив, но и читать элементы и обновлять их:
readArray
:: (MArray a e m, Ix i) => a i e -> i -> m e
writeArray :: (MArray a e m, Ix i) => a i e -> i -> e -> m ()
В случае ST-ссылок у нас была функция runST. Она возвращала значение из памяти, но что будет возвра-
щать аналогичная функция для массива? Посмотрим на неё:
Монада изменяемых значений ST | 121
freeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
Возможно за всеми классами схожесть с функцией runST прослеживается не так чётко. Новый класс
IArray обозначает неизменяемые (immutable) массивы. Функцией freeze мы превращаем изменяемый мас-
сив в неизменяемый, но завёрнутый в специальный тип-монаду. В нашем случае этим типом будет ST. В
модуле Data.Array.ST определена специальная версия этой функции:
runSTArray :: Ix i => (forall s . ST s (STArray s i e)) -> Array i e
Здесь Array – это обычный неизменяемый массив. Он живёт в модуле Data.Array мы можем строить
массивы из списков значений, преобразовывать их разными способами, превращать в обратно в списки и
многое другое. Об о всём этом можно узнать из документации к модулю. Обратите на появление слова
forall и в этой функции. Оно несёт тот же смысл, что и в функции runST.
Для тренировки напишем функцию, которая меняет местами два элемента массива:
module Qsort where
import Data.STRef
import Control.Monad.ST
import Data.Array
import Data.Array.ST
import Data.Array.MArray
swapElems :: Ix i => i -> i -> STArray s i e -> ST s ()
swapElems i j arr = do
vi <- readArray arr i
vj <- readArray arr j
writeArray arr i vj
writeArray arr j vi
Протестируем на небольшом массиве:
test :: Int -> Int -> [a] -> [a]
test i j xs = elems $ runSTArray $ do
arr <- newListArray (0, length xs - 1) xs
swapElems i j arr
return arr
Тир функции test ничем не выдаёт её содержание. Вроде функция как функция:
test :: Int -> Int -> [a] -> [a]
Посмотрим на то, как она работает:
*Qsort> test 0 3 [0,1,2,3,4]
[3,1,2,0,4]
*Qsort> test 0 4 [0,1,2,3,4]
[4,1,2,3,0]
Теперь перейдём к сортировке. Суть метода в том, что мы выбираем один элемент массива, называемый
осью (pivot) и переставляем остальные элементы массива так, чтобы все элементы меньше осевого были сле-
ва от него, а все, что больше оказались справа. Затем мы повторяем эту процедуру на массивах поменьше,
тех, что находятся слева и справа от осевого элемента и так пока все элементы не отсортируются. В алго-
ритме очень хитрая процедура перестановки элементов, наша задача переставить элементы в массиве, то
есть не пользуясь никакими дополнительными структурами данных. Я не буду говорить как это делается,
просто выпишу код, а вы можете почитать об этом где-нибудь, в любом случае из кода будет понятно как это
происходит:
qsort :: Ord a => [a] -> [a]
qsort xs = elems $ runSTArray $ do
arr <- newListArray (left, right) xs
qsortST left right arr
return arr
where left
= 0
122 | Глава 7: Функторы и монады: примеры
right = length xs - 1
qsortST :: Ord a => Int -> Int -> STArray s Int a -> ST s ()
qsortST left right arr = do
when (left <= right) $ do
swapArray left (div (left + right) 2) arr
vLeft <- readArray arr left
(last, _) <- forLoop (left + 1) (<= right) succ
(update vLeft) (return (left, arr))
swapArray left last arr
qsortST left (last - 1) arr
qsortST (last + 1) right arr
where update vLeft i st = do
(last, arr) <- st
vi <- readArray arr i
if (vi < vLeft)
then do
swapArray (succ last) i arr
return (succ last, arr)
else do
return (last, arr)
Это далеко не самый быстрый вариант быстрой сортировки, но самый простой. Мы просто учимся обра-
щаться с изменяемыми массивами. Протестируем:
*Qsort> qsort ”abracadabra”
”aaaaabbcdrr”
*Qsort> let x = 1000000
*Qsort> last $ qsort [x, pred x .. 0]
-- двадцать лет спустя
1000000
7.6 Краткое содержание
Мы посмотрели на примерах как применяются типы State, Reader и Writer. Также мы познакомились
с монадой изменяемых значений ST. Она позволяет писать в имеративном стиле на Haskell. Мы узнали два
новых элемента пострения типов:
• Типы-обёртки, которые определяются через ключевое слово newtype.
• Записи, они являются произведением типов с именованными полями.
Также мы узнали несколько полезных типов:
• Map – хранение значений по ключу (из модуля Data.Map).
• Tree – деревья (из модуля Data.Tree).
• Array – массивы (из модуля Data.Array).
• Типы для накопления результата (из модуля Data.Monoid).
Отметим, что экземпляр класса Monad определён и для функций. Мы можем записать функцию двух ар-
гументов (a -> b -> c) как (a -> (-> ) b c). Тогда тип (-> ) b будет типом с одним параметром, как раз
то, что нужно для класса Monad. По смыслу экземпляр класса Monad для функций совпадает с экземпляром
типа Reader. Первый аргумент стрелочного типа b играет роль окружения.
7.7 Упражнения
• Напишите с помощью типа Random функцию игры в кости, два игрока бросают по очереди кости (два
кубика с шестью гранями, грани пронумерованы от 1 до 6). Они бросают кубики 10 раз выигрывает тот,
у кого в сумме выпадет больше очков. Функция принимает начальное состояние и выводит результат
игры: суммарные баллы игроков.
Краткое содержание | 123
• Напишите с помощью типа Random функцию, которая будет создавать случайные деревья заданной
глубины. Значение в узле является случайным числом от 0 до 100, также число дочерних деревьев в
каждом узле случайно, оно изменяется от 0 до 10.
• Опишите в виде конечного автомата поведение амёбы. Амёба может двигаться на плоскости по четырём
направлениям. Если она чувствует свет в определённой стороне, то она ползёт туда. Если по-близости
нет света, она ползает в произвольном направлении. Амёба улавливает интенсивность света, если по
всем четырём сторонам интенсивность одинаковая, она стоит на месте и греется.
• Казалось бы, зачем нам сохранять вычисления в выражениях, почему бы нам просто не вычислить их
сразу? Если у нас есть описание выражения мы можем применить различные техники оптимизации, ко-
торые могут сокращать число вычислений. Например нам известно, что двойное отрицание не влияет
на аргумент, мы можем выразить это так:
instance Num Exp where
negate (Neg a)
= a
negate x
= Neg x
...
...
Так мы сократили вычисления на две операции. Возможны и более сложные техники оптимизации.
Мы можем учесть ноль и единицу при сложении и умножении или дистрибутивность сложения отно-
сительно умножения.
В этом упражнении вам предлагается провести подобную оптимизацию для логических значений. У
нас есть абстрактное синтаксическое дерево:
data Log
= True
| False
| Not Log
| Or
Log Log
| And Log Log
Напишите функцию, которая оптимизирует выражение Log. Эта функция приводит Log к конъюнктив-
ной нормальной форме (КНФ). Дерево в КНФ обладает такими свойствами: все узлы с Or находятся
ближе к корню чем узлы с And и все узлы с And находятся ближе к корню чем узлы с Not. В КНФ выра-
жения имеют вид:
(True ‘And‘ Not False ‘And‘ True) ‘Or‘ True ‘Or‘ (True ‘And‘ False)
(True ‘And‘ True ‘And‘ False) ‘Or‘ True
Как бы мы не шли от корня к листу сначала нам будут встречаться только операции Or, затем только
операции And, затем только Not.
КНФ замечательна тем, что её вычисление может пройти досрочно. КНФ можно представить так:
data Or’
a = Or’
[a]
data And’ a = And’ [a]
data Not’ a = Not’
a
data Lit
= True’ | False’
type CNF = Or’ (And’ (Not’ Lit))
Сначала идёт список выражений разделённых конструктором Or (вычислять весь список не нужно, нам
нужно найти первый элемент, который вернёт True). Затем идёт список выражений, разделённых And
(опять же его не надо вычислять целиком, нам нужно найти первое выражение, которое вернёт False).
В самом конце стоят отрицания.
В нашем случае приведение к КНФ состоит из двух этапов:
– Сначала построим выражение, в котором все конструкторы Or и And стоят ближе к корню чем
конструктор Not. Для этого необходимо воспользоваться такими правилами:
-- удаление двойного отрицания
Not (Not a)
==> a
-- правила де Моргана
Not (And a b) ==> Or
(Not a) (Not b)
Not (Or
a b) ==> And (Not a) (Not b)
124 | Глава 7: Функторы и монады: примеры
– Делаем так чтобы все конструкторы Or были бы ближе к корню чем конструкторы And. Для этого
мы воспользуемся правилом дистрибутивности:
And a (Or b c)
==> Or (And a b) (And a c)
При этом мы будем учитывать коммутативность And и Or:
And a b
== And b a
Or
a b
== Or
b a
• Когда вы закончите определение функции:
transform :: Log -> CNF
Напишите функцию, которая будет сравнивать вычисление исходного выражения напрямую и вычис-
ление через КНФ. Эта функция будет принимать исходное значение типа Log и будет возвращать два
числа, число операций необходимых для вычисления выражения:
evalCount :: Log -> (Int, Int)
evalCount a = (evalCountLog a, evalCountCNF a)
evalCountLog :: Log -> Int
evalCountLog a = ...
evalCountCNF :: Log -> Int
evalCountCNF a = ...
При написании этих функций воспользуйтесь функциями-накопителями.
• В модуле Data.Monoid определён специальный тип с помощью которого можно накапливать функции.
Только функции должны быть специального типа. Они должны принимать и возвращать значения од-
ного типа. Такие функции называют эндоморфизмами.
Посмотрим на их определение:
newtype Endo a = Endo { appEndo :: a -> a }
instance Monoid (Endo a) where
mempty = Endo id
Endo f ‘mappend‘ Endo g = Endo (f . g)
В качестве нейтрального элемента выступает функция тождества, а функцией объединения значений
является функция композиции. Попробуйте переписать примеры из главы накопление чисел с помощью
этого типа.
• Реализуйте с помощью монады ST какой-нибудь алгоритм в императивном стиле. Например алгоритм
поиска корней уравнения методом деления пополам. Если функция f непрерывна и в двух точках a и b
( a < b) значения функции имеют разные знаки, то это говорит о том, что где-то на отрезке [ a, b] урав-
нение f( x) = 0 имеет решение. Мы можем найти его так. Посмотрим какой знак у значения функции в
середине отрезка. Если значение равно нулю, то нам повезло и мы нашли решение, если нет, то из двух
концов отрезка выбрем тот, у которого знак значения функции f отличается от знака значения в сере-
дине отрезка. Далее повторим эту процедуру на новом отрезке. И так пока мы не найдём корень или
отрезок не стянется в точку. Внутри функции выделите память под концы отрезка и последовательно
изменяйте их внутри типа ST.
Упражнения | 125
Глава 8
IO
Пока мы не написали ещё ни одной программы, которой можно было бы пользоваться вне интерпретато-
ра. Предполагается, что программа как-то взаимодействует с пользователем (ожидает ввода с клавиатуры)
и изменяет состояние компьютера (выводит сообщения на экран, записывает данные в файлы). Но пока что
мы не знаем как взаимодействовать с окружающим миром.
Самое время узнать! Сначала мы посмотрим какие проблемы связаны с реализацией взаимодействия с
пользователем. Как эти проблемы решаются в Haskell. Потом мы научимся решать несколько типичных задач,
связанных с вводом/выводом.
8.1 Чистота и побочные эффекты
Когда мы определяем новые функции или константы мы лишь даём новые имена комбинациям значений.
В этом смысле у нас ничего не изменяется. По-другому это называется функциональной чистотой (referential
transparency). Это свойство говорит о том, что мы свободно можем заменить в тексте программы любой
синоним на его определение и это никак не скажется на результате.
Функция является чистой, если её выход зависит только от её входов. В любой момент выполнения про-
граммы для одних и тех же входов будет один и тот же выход. Это свойство очень ценно. Оно облегчает
понимание поведения функции. Оно говорит о том, что функция может зависеть от других функций толь-
ко явно. Если мы видим, что другая функция используется в данной функции, то она используется в этой
функции. У нас нет таинственных глобальных переменных, в которые мы можем записывать данные из од-
ной функции и читать их с помощью другой. Мы вообще не можем ничего записывать и ничего читать. Мы
не можем изменять состояния, мы можем лишь давать новые имена или строить новые выражения из уже
существующих.
Но в этот статичный мир описаний не вписывается взаимодействие с пользователем. Предположим, что
мы хотим написать такую программу: мы набираем на клавиатуре имя файла, нажимаем Enter и программа
показывает на экране содержимое этого файла, затем мы набираем текст, нажимаем Enter и текст дописыва-
ется в конец файла, файл сохраняется. Это описание предполагает упорядоченность действий. Мы не можем
сначала сохранить текст, затем прочитать обновления. Тогда текст останется прежним.
Ещё один пример. Предположим у нас есть функция getChar, которая читает букву с клавиатуры. И
функция print, которая выводит строку на экран И посмотрим на такое выражение:
let c = getChar
in
print $ c : c : []
О чём говорит это выражение? Возможно, прочитай с клавиатуры букву и выведи её на экран дважды.
Но возможен и другой вариант, если в нашем языке все определения это синонимы мы можем записать это
выражение так:
print $ getChar : getChar : []
Это выражение уже говорит о том, что читать с клавиатуры необходимо дважды! А ведь мы сделали обыч-
ное преобразование, заменили вхождения синонима на его определение, но смысл изменился. Взаимодей-
ствие с пользователем нарушает чистоту функций, нечистые функции называются функциями с побочными
эффектами.
Как быть? Можно ли внести в мир описаний порядок выполнения, сохранив преимущества функциональ-
ной чистоты? Долгое время этот вопрос был очень трудным для чистых функциональных языков. Как можно
пользоваться языком, который не позволяет сделать такие базовые вещи как ввод/вывод?
126 | Глава 8: IO
8.2 Монада IO
Где-то мы уже встречались с такой проблемой. Когда мы говорили о типе ST и обновлении значений. Там
тоже были проблемы порядка вычислений, нам удалось преодолеть их с помощью скрытой передачи фиктив-
ного состояния. Тогда наши обновления были чистыми, мы могли безболезненно скрыть их от пользователя.
Теперь всё гораздо труднее. Нам всё-таки хочется взаимодействовать с внешним миром. Для обозначения
внешнего мира мы определим специальный тип и назовём его RealWorld:
module IO(
IO
) where
data RealWorld = RealWorld
newtype IO a = IO (ST RealWorld a)
instance Functor
IO where ...
instance Applicative
IO where ...
instance Monad
IO where ...
Тип IO (от англ. input-output или ввод-вывод) обозначает взаимодействие с внешним миром. Внешний
мир словно является состоянием наших вычислений. Экземпляры классов композиции специальных функций
такие же как и для ST (а следовательно и для State). Но при этом, поскольку мы конкретизировали первый
параметр типа ST, мы уже не сможем воспользоваться функцией runST.
Тип RealWorld определён в модуле Control.Monad.ST, там же можно найти и функцию:
stToIO :: ST RealWorld a -> IO a
Интересно, что класс Monad был придуман как раз для решения проблемы ввода-вывода. Классы типов
изначально задумывались для решения проблемы определения арифметических операций на разных числах
и функции сравнения на равенство для разных типов, мало кто тогда догадывался, что классы типов сыграют
такую роль, станут основополагающей особенностью языка.
a
f
IO b
b
g
IO c
До
После
a
g
f
IO c
a
f>>g
IO c
Рис. 8.1: Композиция для монады IO
Посмотрим на (рис. 8.1). Это рисунок для класса Kleisli. Здесь под >> понимается композиция, как мы
её определяли в главе 6, а не метод класса Monad, вспомним определение:
class Kleisli m where
idK
:: a -> m a
(>> ) :: (a -> m b) -> (b -> m c) -> (a -> m c)
Монада IO | 127
Композиция специальных функций типа a -> IO b вносит порядок вычисления. Считается, что сначала
будет вычислена функция слева от композиции, а затем функция справа от композиции. Это происходит за
счёт скрытой передачи фиктивного состояния. Теперь перейдём к классу Monad. Там композиция заменяется
на применение или операция связывания:
ma >>= mf
Для типа IO эта запись говорит о том, что сначала будет выполнено выражение ma и результат будет под-
ставлен в выражение mf и только затем будет выполнено mf. Оператор связывания для специальных функций
вида:
a -> IO b
раскалывает наш статический мир на “до” и “после”. Однажды попав в сети IO, мы не можем из них
выбраться, поскольку теперь у нас нет функции runST. Но это не так страшно. Тип IO дробит наш статический
мир на кадры. Но мы спокойно можем создавать статические чистые функции и поднимать их в мир IO лишь
там где это действительно нужно.
Рассмотрим такой пример, программа читает с клавиатуры начальное значение, затем загружает файл
настроек. Потом запускается, какая-то сложная функция и в самом конце мы выводим результат на экран.
Схематично мы можем записать эту программу так:
program = liftA2 algorithm readInit (readConfig ”file”) >>= print
-- функции с побочными эффектами
readInit
:: IO Int
readConfig :: String -> IO Config
:: Show a => a -> IO ()
-- большая и сложная, но !чистая! функция
algorithm
:: Int -> Config -> Result
Функция readInit читает начальное значение, функция readConfig читает из файла наcтройки, функ-
ция print выводит значение на экран, если это значение можно преобразовать в строку. Функция algorithm
это большая функция, которая вычисляет какие-то данные. Фактически наше программа это и есть функция
algorithm. В этой схеме мы добавили взаимодействие с пользователем лишь в одном месте, вся функция
algorithm построена по правилам мира описаний. Так мы внесли порядок выполнения в программу, сохра-
нив возможность определения чистых функций.
Если у нас будет ещё один “кадр”, ещё одно действие, например как только функция algorithm закончила
вычисления ей нужны дополнительные данные от пользователя, на основе которых мы сможем продолжить
вычисления с помощью какой-нибудь другой функции. Тогда наша программа примет вид:
program =
liftA2 algorithm2 readInit
(liftA2 algorithm1 readInit (readConfig ”file”))
-- функции с побочными эффектами
readInit
:: IO Int
readConfig :: String -> IO Config
:: Show a => a -> IO ()
-- большие и сложные, но !чистые! функции
algorithm1
:: Int -> Config -> Result1
algorithm2
:: Int -> Result1 -> Result2
Теперь у нас два кадра, программа выполняется в два этапа. Каждый из них разделён участками взаимо-
действия с пользователем. Но тип IO присутствует лишь в первых шести строчках, остальные два миллиона
строк написаны в мире описаний, исключительно чистыми функциями, которые поднимаются в мир специ-
альных функций с помощью функций liftA2 и стыкуются с помощью операции связывания >>=.
Попробуем тип IO в интерпретаторе. Мы будем пользоваться двумя стандартными функциями getChar и
-- читает символ с клавиатуры
getChar :: IO Char
-- выводит значение на экран
print :: IO ()
128 | Глава 8: IO
Функция print возвращает значение единичного типа, завёрнутое в тип IO, поскольку нас интересует не
само значение а побочный эффект, который выполняет эта функция, в данном случае это вывод на экран.
Закодируем два примера из первого раздела. В первом мы читаем один символ и печатаем его дважды:
Prelude> :m Control.Applicative
Prelude Control.Applicative> let res = (\c -> c:c:[]) <$> getChar >>= print
Prelude Control.Applicative> res
q”qq”
Мы сначала вызываем функцию getChar удваиваем результат функцией \c -> c:c:[] и затем выводим
на экран.
Во втором примере мы дважды запрашиваем символ с клавиатуры а затем печатаем их:
Prelude Control.Applicative> let res = liftA2 (\a b -> a:b:[]) getChar getChar >>= print
Prelude Control.Applicative> res
qw”qw”
8.3 Как пишутся программы
Мы уже умеем читать с клавиатуры и выводить значения на экран. Давайте научимся писать самостоя-
тельные программы. Программа обозначается специальным именем:
main :: IO ()
Если модуль называется Main или в нём нет директивы module ... where и в модуле есть функция main
:: IO (), то после компиляции будет сделан исполняемый файл. Его можно запускать независимо от ghci.
Просто нажимаем дважды мышкой или вызываем из командной строки.
Напишем программу Hello world. Единственное, что она делает это выводит на экран приветствие:
main :: IO ()
main = print ”Hello World!”
Теперь сохраним эти строчки в файле Hello. hs, перейдём в директорию файла и скомпилируем файл:
ghc --make Hello
Появились объектный и интерфейсный файлы, а также появился третий бинарный файл. Это либо Hello
без расширения (в Linux) или Hello. exe (в Windows). Запустим этот файл:
$ ./Hello
”Hello World!”
Получилось! Это наша первая программа. Теперь напишем программу, которая принимает три символа
с клавиатуры и выводит их в обратном порядке:
import Control.Applicative
f :: Char -> Char -> Char -> String
f a b c = reverse $ [a,b,c]
main :: IO ()
main = print =<< f <$> getChar <*> getChar <*> getChar
Сохраним в файле ReverseIO. hs и скомпилируем:
ghc --make ReverseIO -o rev3
Дополнительным флагом -o мы попросили компилятор чтобы он сохранил исполняемый файл под име-
нем rev3. Теперь запустим в командной строке:
$ ./rev3
qwe
”ewq”
Как пишутся программы | 129
Набираем три символа и нажимаем ввод. И программа переворачивает ответ. Обратите внимание на то,
что с помощью print мы выводим не просто строку на экран, а строку как значение. Поэтому добавляются
двойные кавычки. Для того чтобы выводить строку существует функция putStr. Заменим print на putStr,
перекомпилируем и посмотрим что получится:
$ ghc --make ReverseIOstr -o rev3str
[1 of 1] Compiling Main
( ReverseIOstr.hs, ReverseIOstr.o )
Linking rev3str ...
$ ./rev3str
123
321$
Видно, что после вывода не произошёл перенос каретки, терминал приглашает нас к вводу команды сразу
за ответом, если перенос нужен, можно воспользоваться функцией putStrLn. Обратите внимание на то, что
кроме бинарного файла появились ещё два файла с расширениями . hi и . o. Первый файл называется ин-
терфейсным он описывает какие в модуле определения, а второй файл называется объектным. Он содержит
скомпилированный код модуля.
Стоит отметить команду runhaskell. Она запускает программу без создания дополнительных файлов.
Но в этом случае выполнение программы будет происходить медленнее.
8.4 Типичные задачи IO
Вывод на экран
Нам уже встретилось несколько функций вывода на экран. Это функции: print (вывод значения из эк-
земпляра класса Show), putStr (вывод строки) и putStrLn (вывод строки с переносом). Каждый раз когда мы
набираем какое-нибудь выражение в строке интерпретатора и нажимаем Enter, интерпретатор применяет к
выражению функцию print и мы видим его на экране.
Из простейших функций вывода на экран осталось не рассмотренной лишь функция putChar, но я думаю
вы без труда догадаетесь по типу и имени чем она занимается:
putChar :: Char -> IO ()
Функции вывода на экран также можно вызывать в интерпретаторе:
Prelude> putStr ”Hello” >> putChar ’ ’ >> putStrLn ”World!”
Hello World!
Обратите внимание на применение постоянной функции для монад >> . В этом выражении нас интересует
не результат, а те побочные эффекты, которые выполняются при композиции специальных функций. Также
мы пользовались функцией >> в сочетании с монадой Writer для накопления результата.
Ввод пользователя
Мы уже умеем принимать от пользователя буквы. Это делается функцией getChar. Функцией getLine мы
можем прочитать целую строчку. Строка читается до тех пор пока мы не нажмём Enter.
Prelude> fmap reverse $ getLine
Hello-hello!
”!olleh-olleH”
Есть ещё одна функция для чтения строк, она называется getContents. Основное отличие от getLine
заключается в том, что содержание не читается сразу, а откладывается на потом, когда содержание дей-
ствительно понадобится. Это ленивый ввод. Для задачи чтения символов с терминала эта функция может
показаться странной. Но часто в символы вводятся не вручную, а передаются из другого файла. Например
если мы направим на ввод данные из-какого-нибудь большого-большого файла, файл не будет читаться сра-
зу, и память не будет заполнена не нужным пока содержанием. Вместо этого программа отложит считывание
на потом и будет заниматься им лишь тогда, когда оно понадобится в вычислениях. Это может существенно
снизить расход памяти. Мы читаем файл в 2Гб моментально (мы делаем вид, что читаем его). А на самом
деле сохраняем себе задачу на будущее: читать ввод, когда придёт пора.
130 | Глава 8: IO
Чтение и запись файлов
Для чтения и записи файлов есть три простые функции:
ТЕЛЕГРАМКанал с обзорами, анонсами новинок и книжными подборками
Книжный Вестник
Бот для удобного поиска книг (если не нашлось на сайте)
Поиск книг
Свежие любовные романы в удобных форматах
Любовные романы
О психологии, саморазвитии и личностном росте
Саморазвитие
Детективы и триллеры, все новинки
Детективы
Фантастика и фэнтези, все новинки
Фантастика
Отборные классические книги
Классика
ВКОНТАКТЕБиблиотека с любовными романами, которая наверняка придётся по вкусу женской части аудитории
Любовные романы
Библиотека с фантастикой и фэнтези, а также смежных жанров
Фантастика
Самые популярные книги в формате фб2
Топ фб2
книги