Учебник по Haskell - [44]

разворачивать их из типа 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 Применение функций

Давайте определим в терминах композиции ещё одну полезную функцию. А именно функцию примене-

ния. Вспомним её тип:

(