Учебник по 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)