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 разное
число стрелок.
Закодируем эту схему в Haskelclass="underline"
Примеры специальных функций | 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])