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])