требуется модуль 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.
Применение в этом мире происходит особенным образом. Необходимо помнить о том, что второй аргу-
