Unknown - haskell-notes

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

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> letfix =foldr ( $) undefined .repeat

Prelude>take 3 $y (1 :)

[1,1,1]

Prelude>fix (\f n -> ifn ==0 then0 elsen +f (n -1)) 10

55

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

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

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

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

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

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

hylo phi psi =cata phi .ana psi

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

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

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

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

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

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

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

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