Учебник по Haskell

⊥. Это тривиальные сравнения и мы их будем лишь подразумевать.

Считается, что если два значения определены полностью, то мы не можем сказать какое из них информатив-

нее. Так к примеру для логических значений мы не можем сказать какое значение более определено T rue

или F alse.

Рассмотрим пример по-сложнее. Частично определённые значения:

data M aybe a = N othing | Just a

Индуктивные и коиндуктивные типы | 245

⊥

N othing

⊥

J ust ⊥

⊥

J ust a

J ust a

J ust b,

если a

b

Если вспомнить как происходит вычисление значения, то значение a менее определено чем b, если взрыв-

ное значение ⊥ в a находится ближе к корню значения, чем в b. Итак получается, что в категории Hask объ-

екты это множества с частичным порядком. Что означает требование монотонности функции?

Монотонность в контексте операции

говорит о том, что чем больше определён вход функции тем больше

определён выход:

a

b

⇒ f a

f b

Это требование накладывает запрет на возможность проведения сопоставления с образцом по значению

⊥. Иначе мы можем определять немонотонные функции вроде:

isBot :: Bool -> Bool

isBot undefined = True

isBot _

= undefined

Полнота частично упорядоченного множества означает, что у любой последовательности xn

x 0

x 1

x 2

...

есть значение x, к которому она сходится. Это значение называют супремумом множества. Что такое

полные частично упорядоченные множества мы разобрались. А что такое полиномиальный функтор?

Полиномиальный функтор

Полиномиальный функтор – это функтор который построен лишь с помощью операций суммы, произве-

дения, постоянных функторов, тождественного фуктора и композиции функторов. Определим эти операции:

• Сумма функторов F и G определяется через операцию суммы объектов:

( F + G) X = F X + GX

• Произведение функторов F и G определяется через операцию произведения объектов:

( F × G) X = F X × GX

• Постоянный функтор отображает все объекты категории в один объект, а стрелки в тождественнубю

стрелку этого объекта, мы будем обозначать постоянный функтор подчёркиванием:

AX

=

A

Af

=

idA

• Тождественный функтор оставляет объекты и стрелки неизменными:

IX

=

X

If

=

f

• Композиция функторов F и G это последовательное применение функторов

F GX = F ( GX)

246 | Глава 16: Категориальные типы

По определению функции построенные с помощью этих операций называют полиномиальными. Опреде-

лим несколько типов данных с помощью полиномиальных функторов. Определим логические значения:

Bool = µ(1 + 1)

Объект 1 обозначает любую константу, это конечный объект исходной категории. Нам не важны имена

конструкторов, но важна структура типа. µ обозначает начальный объект в F -алгебре.

Определим натуральные числа:

N at = µ(1 + I)

Эта запись обозначает начальный объект для F -алгебры с функтором F = 1 + I. Посмотрим на опреде-

ление списка:

ListA = µ(1 + A × I)

Список это начальный объект F -алгебры 1 + A × I. Также можно определить бинарные деревья:

BT reeA = µ( A + I × I)

Определим потоки:

StreamA = ν( A × I)

Потоки являются конечным объектом F -коалгебры, где F = A × I.

16.3 Гиломорфизм

Оказывается, что с помощью катаморфизма и анаморфизма мы можем определить функцию fix, то есть

мы можем выразить любую рекурсивную функцию с помощью структурной рекурсии.

Функция fix строит бесконечную последовательность применений некоторой функции f.

f (f (f ... )))

Сначала с помощью анаморфизма мы построим бесконечный список, который содержит функцию f во

всех элементах:

repeat f = f : f : f : ...

А затем заменим конструктор : на применение. В итоге мы получим такую функцию:

fix :: (a -> a) -> a

fix = foldr ($) undefined . repeat

Убедимся, что эта функция работает:

Prelude> let fix = foldr ($) undefined . repeat

Prelude> take 3 $ y (1:)

[1,1,1]

Prelude> fix (\f n -> if n==0 then 0 else n + f (n-1)) 10

55

Теперь давайте определим функцию fix через функции cata и ana:

fix :: (a -> a) -> a

fix = cata (\(Cons f a) -> f a) . ana (\a -> Cons a a)

Эта связка анаморфизм с последующим катаморфизмом встречается так часто, что ей дали специальное

имя. Гиломорфизмом называют функцию:

hylo :: Functor f => (f b -> b) -> (a -> f a) -> (a -> b)

hylo phi psi = cata phi . ana psi

Отметим, что эту функцию можно выразить и по-другому:

Гиломорфизм | 247

hylo :: Functor f => (f b -> b) -> (a -> f a) -> (a -> b)

hylo phi psi = phi . (fmap $ hylo phi psi) . psi

Этот вариант более эффективен по расходу памяти, мы не строим промежуточное значение Fix f, а сразу

обрабатываем значения в функции phi по ходу их построения в функции psi. Давайте введём инфиксную

операцию гиломорфизм для этого определения:

(>> ) :: Functor f => (a -> f a) -> (f b -> b) -> (a -> b)

psi >> phi = phi . (fmap $ hylo phi psi) . psi

Теперь давайте скроем одноимённую функцию из Prelude и определим несколько рекурсивных функций

с помощью гиломорфизма. Начнём с функции вычисления суммы чисел от нуля до данного числа:

sumInt :: Int -> Int