Unknown - haskell-notes

буква заменяется на новую последовательность букв, согласно определённым правилам. Так организм живёт

и развивается. Приведём пример:

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 of2] Compiling Kleisli

( Kleisli.hs, interpreted )

Ok, modules loaded : Kleisli, Nat.

*Kleisli> letgen 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) или

кортежа с нулём элементов. Единичный тип имеет всего одно значение, которым мы и воспользовались в