Функтори (глава книги «Теорія категорій для програмістів»)

Це сьома стаття з циклу «Теорія категорій для програмістів». Попередні статті вже публікувалися на Хабре:

Функтори

За поняттям функтора стоїть дуже проста, але потужна ідея (як би заїжджено це не прозвучало). Просто теорія категорій повне простих і потужних ідей. Функтор є відображення між категоріями. Нехай дано дві категорії C та D, а функтор F відображає об'єкти з C в об'єкти з D — це функція над об'єктами. Якщо a — це об'єкт з C, то будемо позначати його образ з D F a (без дужок). Але ж категорія — це не тільки об'єкти, але ще і з'єднують їх морфизмы. Функтор також відображає і морфизмы — це функція над морфизмами. Але морфизмы відображаються не як попало, а так, щоб зберігати зв'язку. А саме, якщо морфизм f з C пов'язує об'єкт a з об'єктом b
f : a - > b

то образ f D, F f, пов'язує образ a з образом b:
F f :: F a -> F b

(Сподіваємося, що така суміш математичних позначень і синтаксису Haskell зрозуміла читачеві. Ми не писатимемо дужки, застосовуючи функтори до об'єктів або морфизмам.)

Як бачите, функтор зберігає структуру: що було пов'язано у вхідний категорії, буде пов'язано і у вихідний. Але цим структура не вичерпується: необхідно також підтримати композицію морфізмів. Якщо
h
— композиція
f
та
g
:
то зажадаємо, щоб його образ під дією F був композицією образів f і g:
F h = F g . F f


Нарешті, зажадаємо, щоб всі одиничні(тотожні) морфизмы з C відображалися в поодинокі морфизмы з D:
F id(a) = id(F a)

Тут ida — це одиничний морфизм об'єкта a, idF a — одиничний морфизм об'єкта F a.

Зауважимо, що всі ці умови суттєво обмежують коло функцій, які підходять як морфізмів. Функтори повинні зберігати структуру категорії. Якщо уявити собі категорію як набір об'єктів, переплетених морфизмами, то функтор не має права обірвати ні однієї нитки цього мережива. Він може об'єднати кілька об'єктів, він може склеїти морфизмы в один, але ніколи не розриває зв'язків. Це обмеження аналогічно поняттю безперервності з математичного аналізу. У цьому сенсі функтори "безперервні" (хоча існує ще більш обмежувального визначення безперервності функторів). Як і будь-яка функція, функтор може бути і склеюють, і які вкладають. Аспект вкладення найбільш яскраво проявляється, коли вихідна категорія набагато менше цільової. У граничному випадку вихідна категорія являє собою категорію 1, що складається з одного об'єкта і одного (одиничного) морфизма. Функтор з категорії 1 в будь-яку іншу категорію, просто вибирає певний об'єкт з цієї категорії. Має місце повна аналогія з морфизмами з сінглтона, вибирають елементи з цільових множин. Аспект склеювання, доведений до абсурду, спостерігається в константному функторе Δc. Він відображає кожен об'єкт вихідної категорії в певний об'єкт c цільової категорії, а всякий морфизм — в одиничний морфизм idc. Це як чорна діра, засмоктує все в точку сингулярності. Ми повернемося до розгляду цього функтора при обговоренні меж і копределов.
Функтори в програмуванні
Повернемося на землю, в світ програмування. Отже, у нас є категорія типів та функцій. Розглянемо функтори, що відображають цю категорію в себе — так звані эндофункторы. Що являє собою эндофунктор в категорії типів? В першу чергу, він зіставляє одним типам інші. Подібні відображення насправді нам знайомі, це типи, параметризрвані іншими типами. Розглянемо кілька прикладів.
Функтор Maybe
Визначення Maybe є відображення типу
a
тип
Maybe
a:
data Maybe a = Nothing | Just a

Важлива деталь:
Maybe
сам по собі — це не тип, а конструктор типу. Він приймає в якості аргументу тип, такий як
Int
або
Bool
, і повертає інший тип.
Maybe
без аргументів являє собою функцію на типах. Але є
Maybe
функтором? (Тут і далі, говорячи про функторах в контексті програмування, майже завжди маються на увазі эндофункторы.) Адже функтор — це не тільки відображення об'єктів (тут — типів), але і відображення морфізмів (тут — функцій). Для будь-якої функції
a
на
b

f : a - > b

хотілося б отримати функцію
Maybe a
на
Maybe b
. Щоб визначити таку функцію, потрібно розглянути два випадки, відповідні двом конструкторам
Maybe
. У разі
Nothing
ми просто повертаємо
Nothing
назад. Якщо ж аргумент є
Just
, то застосуємо функцію
f
до його вмісту. Отже, образ
f
під дією
Maybe
— це функція
f' :: Maybe a -> b Maybe
f' Nothing = Nothing
f' (Just x) = Just (f x)

(до Речі, в Haskell дозволено використовувати апостроф в іменах змінних, що дуже зручно в подібних випадках.) В Haskell обличчі функтора, що відповідає за відображення морфізмів, реалізується функцією вищого порядку
fmap
. Для
Maybe
вона має наступну сигнатуру:
fmap :: (a -> b) -> (Maybe a -> Maybe b)


Часто кажуть, що
fmap
підносить (піднімає, lifts) функцію. Піднесена функція працює на
Maybe
значеннях. Як завжди, з-за каррирования ця риса може трактуватися двояко: або як функція однієї змінної, яка сама є функцією
(a->b)
повертає функцію
(Maybe a -> Maybe b)
, або як функція двох змінних, яка повертає
Maybe b
:
fmap :: (a -> b) -> Maybe a -> Maybe b 

Слідуючи сказаного вище, дамо визначення
fmap
,
Maybe
:
fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)

Щоб показати, що конструктор типів
Maybe
разом з функцією
fmap
складають функтор, залишилося довести, що
fmap
зберігає поодинокі морфизмы і композицію. Ці твердження називаються "функториальными законами", але вони просто засвідчують збереження структури категорії.
Метод еквівалентних перетворень
Доведемо функториальные закони методом еквівалентних перетворень, який є типовою технікою доказів в Haskell. Метод спирається на те, що функції в Haskell визначені набором рівностей: ліва частина дорівнює правій, обидві вони можуть бути підставлені один замість одного (можливо, при підстановці потрібно перейменувати змінні щоб уникнути конфліктів). Можна підставити тіло функції замість її виклику (инлайнинг), так і виклик функції замість її тіла (рефакторинг). Розглянемо в якості прикладу тотожну функцію:
id x = x

Якщо ми зустрінемо де-небудь, скажімо,
id y
, то його завжди можна замінити на
y
(инлайнинг). І взагалі будь-яке входження
id
, застосованого до висловом, наприклад,
id (y + 2)
, можна замінити на саме це вираз
(y + 2)
. У зворотний бік: будь-який вираз
e
можна замінити на
id e
(рефакторинг). У разі функцій, визначених за допомогою зіставлення із зразком, можна використовувати кожне визначення незалежно. Наприклад, відповідно до даного вище визначення
fmap
можна замінити
fmap f Nothing
на
Nothing
або навпаки. Розглянемо цей підхід на практиці. Почнемо з збереження тотожності:
fmap id = id

Слід розглянути два випадки:
Nothing
та
Just
. Почнемо з
Nothing
(Я описую трансформацію лівій частині рівності в праву використовуючи псевдо-Haskell):
fmap id Nothing 
= { щодо визначення fmap }
Nothing 
= { щодо визначення id }
id Nothing

Зауважте, що на другому кроці ми підставили
id Nothing
замість
Nothing
, використовуючи визначення
id
у зворотний бік. На практиці подібні докази робляться методом "підпалювання гніту з двох кінців", аж до зустрічі в середині на одному і тому ж вираженні,
Nothing
в даному випадку. Другий випадок також нескладний:
fmap id (Just x) 
= { щодо визначення fmap }
Just (id x) 
= { щодо визначення id }
Just x
= { щодо визначення id }
id (Just x)

Тепер покажемо, що
fmap
зберігає композицію:
fmap (g . f) = fmap g . fmap f

Почнемо з випадку
Nothing
:
fmap (g . f) Nothing 
= { щодо визначення fmap }
Nothing 
= { щодо визначення fmap }
fmap g Nothing
= { щодо визначення fmap }
fmap g (fmap f Nothing)

Тепер прийшов час
Just
:
fmap (g . f) (Just x)
= { щодо визначення fmap }
Just ((g . f) x)
= { за визначенням композиції }
Just (g (f x))
= { щодо визначення fmap }
fmap g (Just (f x))
= { щодо визначення fmap }
fmap g (fmap f (Just x))
= { за визначенням композиції }
(fmap g . fmap f) (Just x)

Варто підкреслити, що для функцій з побічними ефектами у стилі С++, метод еквівалентних перетворень не працює. Розглянемо приклад:
int square(int x) {
return x * x;
}
int counter() {
static int c = 0;
return c++;
}
double y = square(counter());

Метод еквівалентних перетворень дозволив би розгорнути
square
і отримати
double y = counter() * counter();

Безумовно, така трансформація некоректна і змінює результат виразу. Незважаючи на це, якщо визначити
square
макрос, препроцесор C++ скористається методом еквівалентних перетворень з катастрофічним результатом.
Знову Maybe
Функтори легко виражаються в Haskell, але описувати їх можна на будь-якій мові, що підтримує узагальнене програмування і функції вищого порядку. Розглянемо С++ -ний аналог Maybe, шаблонний тип
optional
. Ось начерк реалізації (повна реалізація багато складніше, оскільки явно описує різні способи передачі аргументів, семантику копіювання та інші питання характерного для С++ управління ресурсами):
template < class T>
class optional {
bool _isValid; // the tag
T _v;
public:
optional() : _isValid(false) {} // Nothing
optional(T x) : _isValid(true) , іv(x) {} // Just
bool isValid() const { return _isValid; }
T val() const { return _v; }
}; 

Наведений шаблон забезпечує половину опису функтора: відображення типів. Він зіставляє новий тип
optional<T>
кожному типу
T
. Тепер опишемо його дія над функціями:
template < class A, class B>
std::function<optional<B>(optional<A>)> 
fmap(std::function<B(A)> f) 
{
return [f](optional<A> opt) {
if (!opt.isValid())
return optional<B>{};
else
return optional<B>{ f(opt.val()) };
};
}

Це функція вищого порядку, яка набуває функцію як аргумент і повертає функцію. А ось інший варіант, без каррирования:
template < class A, class B>
optional<B> fmap(std::function<B(A)> f, optional<A> opt) {
if (!opt.isValid())
return optional<B>{};
else
return optional<B>{ f(opt.val()) };
}

З іншого боку, можна реалізувати
fmap
як шаблонний метод
optional
. Така неоднозначність у виборі робить абстракцію патерну "функтор" в С++ проблемою. Повинен функтор бути інтерфейсом, щоб від нього успадковуватись (на жаль, шаблонні функції не можуть бути віртуальними)? А може бути, вільної шаблонної функцією, каррированной чи ні? Чи зможе компілятор С++ коректно вивести відсутні типи, або їх треба задавати явно? Уявіть, що вхідна функція
f
перетворює
int
на
bool
. Як компілятор визначить тип
g
:
auto g = fmap(f);

особливо, якщо в майбутньому з'являться безліч функторів зі своїми версіями
fmap
? (З іншими видами функторів ми скоро познайомимося.)
Класи типів
Як же абстракція функтора реалізована в Haskell? Використовується механізм класів типів. Клас типів задає сімейство типів, що підтримують єдиний інтерфейс. Наприклад, клас об'єктів, схожих на рівність визначається так:
class Eq a where
( = = ) : a -> a -> Bool

Тут затверджується, що тип
a
належить до класу Eq якщо він підтримує оператор
(==)
, який приймає два аргументи типу
a
повертає
Bool
. Щоб переконати Haskell що певний тип відноситься до
Eq
, вам знадобиться оголосити його примірником (инстансом, реалізацією) класу, і надати реалізацію
(==)
. Наприклад, маючи таке визначення точки на площині (тип-добуток двох
Float
):
data Point = Pt Float Float

можна визначити рівність точок:
instance Eq Point where
(Pt x y) == (Pt x' y') = x == x' && y == y'

Тут визначається оператор
(==)
розташований инфиксно, між двома зразками
(Pt x y)
та
(Pt x' y')
. Тіло функції вміщується праворуч від знака
=
. Після того, як
Point
оголошений примірником
Eq
, можна безпосередньо порівнювати точки на рівність. Зверніть увагу, що на відміну від C++ або Java ви не зобов'язані надавати клас або навіть інтерфейс
Eq
в момент визначення
Point
, — це можна зробити пізніше. Зауважу, що класи типів, — єдиний механізм для перевантаження функцій і операторів) в Haskell. Він Нам знадобиться, щоб перевантажувати
fmap
для різних функторів. Є одна тонкість: функтор визначається не як тип, а як функція над типами, конструктор типів. Наш клас типів повинен описувати сімейство конструкторів типів, а не просто типів, як було у випадку з
Eq
. На щастя, механізм класів типів Haskell працює з конструкторами типів також як і з простими типами (ПП: хороший приклад прямування функціональній парадигмі навіть у світі типів функції нічим не гірше об'єктів). Нижче визначення класу
Functor
:
class Functor f where
fmap :: (a -> b) -> f a -> f b 

Воно стверджує, що
f
є Functor в тому випадку, якщо є функція
fmap
з даної сигнатурою. Тут
f
тповая мінлива, того ж роду що і тповые змінні
a
та
b
. Але компілятор здатний зрозуміти, що
f
представляє собою конструктор типів, відстежуючи її використання: застосування інших типів, тут
f a
та
f b
. Відповідно, саме конструктор типів ми оголошуємо примірником функтора, як у випадку Maybe:
instance Functor Maybe where
fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)

Зауважу, що клас
Functor
, а також оголошення багатьох загальновживаних типів включаючи
Maybe
його примірниками, входять в стандартну бібліотеку Prelude.
Функтори в C++
ми Можемо застосувати той же підхід в C++? Конструктору типів відповідає шаблонний клас, такий як
optional
, відповідно, нам треба завдний
fmap
двічі шаблонним параметр
F
. Записується це так:
template<template < class> F, class A, class B>
F<B> fmap(std::function<B(A)>, F<A>);

Але як нам спеціалізувати цей шаблон для різних функторів? На жаль, часткова спеціалізація шаблонних функцій C++ заборонена. Не можна написати:
template < class A, class B>
optional<B> fmap<optional>(std::function<B(A)> f, optional<A> opt)

Замість цього доводиться повернутися до перевантаження функцій, в результаті ми повертаємося до початкового визначення
fmap
(без каррирования):
template < class A, class B>
optional<B> fmap(std::function<B(A)> f, optional<A> opt) 
{
if (!opt.isValid())
return optional<B>{};
else
return optional<B>{ f(opt.val()) };
}

Це визначення працює, але для правильної перевантаження вимагається другий аргумент. Більш загальне визначення
fmap
просто ігнорується.
Функтор List
Для кращого розуміння значущості функторів в програмуванні варто розглянути більше прикладів. Будь-який тип, параметризуемый іншим типом — кандидат на роль функтора. Приміром, узагальнені контейнери параметризуются типом своїх елементів, розглянемо список, дуже простий контейнер:
data List a = Nil | Cons a (a List)

Тут у нас конструктор типів
List
, що представляє собою відображення будь-якого типу
a
тип
List a
. Щоб показати, що
List
є функтор, нам необхідно визначити підняття функцій вздовж функтора. Для заданої функції
a->b
визначимо
a List -> List b
:
fmap :: (a -> b) -> (a List -> List b)

Функція, яка діє на
List
має розглянути два випадки, відповідно двом конструкторам списку. Випадок
Nil
тривіальний, —
Nil
ж і повертаємо, з порожнього списку багато не вичавиш. Випадок
Cons
хитріше, оскільки зачіпає рекурсію. Подумаємо: отже, у нас є список
a
, функція
f
перетворює
a
на
b
, і ми хочемо отримати список
b
. Очевидно, слід використовувати
f
, для перетворення кожного елементу списку з
a
на
b
. Що саме потрібно зробити, якщо наш (непорожній список визначений як
Cons
голови і хвоста? Застосувати
f
на голові і застосувати підняте (fmap-нутое)
f
до хвоста. Це визначення рекурсивне, ми визначаємо підняте
f
через підняте
f
:
fmap f (Cons x t) = Cons (f x) (fmap f t) 

Важливо, що в правій частині
fmap f
застосовується до списку більш коротким, ніж визначений нами — а саме до останнього хвоста. Ми застосовуємо рекурсію до все більш коротким списками, тому неминуче приходимо до порожнього списку, або
Nil
. Але як ми вже визначили,
fmap f
Nil
дає
Nil
, тим самим завершуючи рекурсію. Остаточний результат отримуємо комбінуванням нової голови (
f x
) з новим хвостом (
fmap f t
) використовуючи конструктора Cons. В результаті, ось наше оголошення списку примірником функтора повністю:
instance Functor List where
fmap _ Nil = Nil
fmap f (Cons x t) = Cons (f x) (fmap f t) 

Якщо для вас звичніше C++, має сенс розглянути
std::vector
, по суті, базовий контейнер C++. Реалізація
fmap
,
std::vector
— просто обгортка навколо
std::transform
:
template < class A, class B>
std::vector<B> fmap(std::function<B(A)> f, std::vector<A> v)
{
std::vector<B> w;
std::transform( std::begin(v)
, std::end(v)
, std::back_inserter(w)
, f);
return w;
}

З її допомогою ми можемо, наприклад, звести в квадрат ряд чисел:
std::vector < int> v{ 1, 2, 3, 4 };
auto w = fmap([](int i) { return i*i; }, v);
std::copy( std::begin(w)
, std::end(w)
, std::ostream_iterator(std::cout, ", "));

Більшість контейнерів C++ по суті функтори. Це забезпечено наявністю ітераторів, які можна передати
std::transform
, — примітивного родичу
fmap
. На жаль, простота функтора втрачається під мотлохом ітераторів і тимчасових змінних (як в реалізації
fmap
). З хороших новин — планована до включення в C++ бібліотека інтервалів (ranges) значно виявляє їх, інтервалів, функціональну природу.
Функтор Reader
Тепер, коли ми розвинули якусь інтуїцію, зокрема про те, що функтори це свого роду контейнери, ось вам приклад, на перший погляд виглядає зовсім інакше. Розглянемо відображення типу
a
на тип функцій, які повертають
a
. Ми ще не добралися до обговорення функціональних типів на належному теоретико-категорном рівні, але у нас, як програмістів, є їх певне розуміння. В Haskell функціональні типи будуються з допомогою конструктора типів — стрілки
(->)
, який приймає два типи: тип аргументу і тип результату. Ви його вже зустрічали в инфиксной запису,
a->b
, але з допомогою дужок можна нітрохи не гірше використовувати і префиксную запис:
(->) a b

Як і звичайні функції, тповые функції декількох аргументів можна застосовувати частково. І коли ми даємо стрілкою один аргумент, вона все ще чекає інший. Тобто,
(->) a

представляє собою конструктор типів; потрібен ще один тип
b
щоб вийшов повноцінний тип
a->b
. Таким чином, стрілка визначає ціле сімейство конструкторів типів, параметризованих
a
. Давайте з'ясуємо, чи є воно також сімейством функторів. Щоб не плутати два параметра, перейменуємо їх, підкресливши ролі. Згідно з нашими попередніми визначеннями функторів, тип аргументу назвемо
r
, а тип результату
a
. Отже, наш конструктор бере будь-який тип
a
, і відображає його на тип
r->a
. Щоб обґрунтувати функторность, нам треба підняти функцію
a->b
до функції приймаючої
r->a
повертає
r->b
. Це типи, створювані дією конструктора
(->) r
на
a
та
b
відповідно. Ось така виходить сигнатура
fmap
:
fmap :: (a -> b) -> (r -> a) -> (r -> b)

Отримуємо свого роду головоломку: маючи функції
f: a- > b
та функції
g::r->a
,
r->b
. Є тільки один спосіб їх композиції, і результат такий, як нам треба. Виходить така реалізація
fmap
:
instance Functor ((->) r) where
fmap f g = f . g

Спрацювало! Мінімаліст може ще скоротити запис, скориставшись префиксной формою:
fmap f g = (.) f g

тепер аргументи можна опустити, отримуючи ототожнення двох функцій:
fmap = (.)

Комбінацію конструктора типів
(->) r
і такої реалізації
fmap
називають "reader".
Функтори як контейнери
Ми познайомилися з прикладами використання функторів в програмуванні для визначення контейнерів загального призначення, або хоча би об'єктів, що містять якісь значення того типу, яким функтор параметризован. Функтор reader здається винятком, оскільки ми не думаємо про функції як про даних. Але як ми бачили, до функцій застосовна мемоизация, коли обчислення зводиться до пошуку в таблиці. Таблиця це вже дані. З іншого боку, оскільки Haskell ледачий, традиційний контейнер зразок списку може на ділі реалізовуватися як функція. Подивіться, наприклад, на нескінченний список натуральних чисел, який можна описати так:
nats :: [Integer]
nats = [1..]

Пара квадратних дужок у першому рядку, — вбудований тповый конструктор Haskell для списків. У другому рядку з допомогою дужок формується списковый літерал. Очевидно, подібний нескінченний список в пам'яті розмістити неможливо. Компілятор замість цього створити функцію, яка генерує
Integer
-и за запитом. Haskell фактично розмиває межу між кодом і даними: список можна вважати функцією, а функцію можна вважати таблицею, сопоставляющей аргументів результати. Це іноді навіть практично, за умови, що область визначення скінченна, і не занадто велика. Але ось реалізувати
strlen
як табличну функцію було б не практично, оскільки різних рядків нескінченно багато. Програмісти зазвичай не люблять нескінченності, але теорія категорій навчить вас клацати їх як горішки. Багато це всіх можливих рядків, або всіх станів всесвіту, минулого, теперішнього або майбутнього, ми можемо працювати з цим! Так що я думаю про функторных об'єктах (об'єктах типу сконструйованого з допомогою эндофунктора) як містять значення початкового типу (аргументу функтора), навіть якщо таке значення не представлено фізично. Приклад функтора в C++, —
std::future
, який, можливо, коли-небудь буде містити значення, якщо пощастить, і якщо вам потрібно це значення, можливо, доведеться зупинитися і почекати, поки інший потік завершить обчислення. Інший приклад-це об'єкт
IO
в Haskell, який може містити введене користувачем, або майбутні версії нашого всесвіту з «Hello World!» надрукованим в консолі. При такій інтерпретації, функтор є щось, здатне утримувати значення або значення того типу, яким воно параметризовано. Або містити рецепт створення таких значень. Нас не турбує, чи можемо ми поглянути на це значення, — це не відноситься до обов'язкових властивостями функтора. Все що нас цікавить, — можливість маніпулювати такими значеннями за допомогою функцій. Якщо значення було доступно, — ми зможемо побачити і результат застосування функції, якщо ні, нам достатньо того, щоб маніпуляції підпорядковувалися композиції, а маніпуляція з тотожною функцією нічого не змінювала. Просто щоб показати, наскільки нам байдужий доступ до значень всередині функторного об'єкта, ось вам конструктор, який повністю ігнорує свій аргумент
a
:
data Const c a = Const c

тповый конструктор
Const
приймає два типи,
c
та
a
. Щоб створити функтор, нам треба його частково застосувати, так само, як ми робили з конструктором стрілки
(->)
.
fmap :: (a -> b) -> Const c a -> Const c b

Оскільки наш функтор ігнорує свій тповый аргумент, буде природним у реалізації
fmap
ігнорувати функціональний аргумент, — функцію не до чого застосовувати:
instance Functor (Const c) where
fmap _ (Const v) = Const v

В C++ це виглядає трохи наочніше (ось вже не думав, що скажу таке!), за рахунок більш чіткої відмінності між тповыми аргументами, які працюють на етапі компіляції, і значеннями, які працюють під час виконання.
template < class C, class A>
Const struct {
Const(C v) : іv(v) {}
C _v;
};

C++ -реалізація
fmap
також ігнорує функціональний аргумент, і по суті перетворює тип
Const
, не чіпаючи значення.
template < class C, class A, class B>
Const<C, B> fmap(std::function<B(A)> f, Const<C, A> c) {
return Const<C, B>{c.Іv};
}

Незважаючи на дивний вигляд, функтор
Const
грає важливу роль у багатьох побудовах. В теорії категорій це приватний випадок функтора Δc, згаданого раніше — эндофункторной різновиди чорної діри. В майбутньому ми познайомимося з ним ближче.
Композиція функторів
Нескладно переконатися, що для функторів між категоріями композиція працює точно також, як для функцій між множинами. Композиція двох функторів, при дії на об'єкти, є просто композиція відповідних відображень об'єктів, аналогічна ситуація з дією на морфизмы. Після стрибка уздовж двох функторів, поодинокі морфизмы залишаються одиничними, також як і композиція морфізмів залишається такою для образів. Нічого особливого. Зокрема, легко поєднуються эндофункторы. Пам'ятайте функцію
maybeTail
(ПП: з попередньої глави)? Давайте перепишемо її, стосовно до стандартних списками Haskell:
maybeTail :: [a] -> Maybe [a]
maybeTail [] = Nothing
maybeTail (x:xs) = Just xs

(Конструктор порожнього списку, який ми позначили
Nil
замінений порожній парою квадратних дужок
[]
. Конструктор
Cons
замінений инфиксным оператором
:
(двокрапка).) Результат
maybeTail
має тип композиції двох функторів,
Maybe
та
[]
, що діють на
a
. Кожен з цих функторів забезпечений власною версією
fmap
, але що якщо ми хочемо застосувати деяку функцію
f
до вмісту композиції:
Maybe list
? Необхідно пролізти крізь два шари функторів. Використовуючи
fmap
можна пройти крізь зовнішній,
Maybe
. Але ми не можемо відправити
f
всередину
Maybe
, оскільки
f
не працює зі списками. Нам потрібно послати (
fmap f
), для дії на внутрішній список. Наприклад, давайте зведемо в квадрат елементи
Maybe list
цілих чисел:
square x = x * x

mis :: Maybe [Int]
mis = Just [1, 2, 3]

mis2 = fmap (fmap square) mis

Компілятор, проаналізувавши типи з'ясує, що для зовнішнього
fmap
слід використовувати реалізацію екземпляра
Maybe
, а для внутрішнього — реалізацію від функтора
list
. Можливо, не зовсім очевидно, що код вище можна переписати так:
mis2 = (fmap . fmap) square mis

Але згадайте, що про
fmap
можна думати як про функції єдиного аргументу:
fmap :: (a -> b) -> (f a -> f b)

У нашому випадку, другий
fmap
на
(fmap . fmap)
приймає на вхід
square :: Int -> Int

і повертає функцію типу
[Int] -> [Int]

Потім перший
fmap
бере отриману функцію і в свою чергу повертає
Maybe [Int] -> Maybe [Int]

І нарешті ця функція застосовується до
mis
. Таким чином, композиція двох функторів це функтор, чий
fmap
є композиція відповідних
fmap
. Повертаючись до теорії категорій: досить очевидно, що композиція функторів ассоциативна (і відображення об'єктів асоціативно, і відображення функторів). Крім того, в кожній категорії є одиничний функтор, який відображає кожен об'єкт в нього ж, і аналогічно діє з морфизмами. Тобто, функтори мають всі необхідні властивості морфізмів деякої категорії. Але що це буде за категорія? Це повинна бути категорія, в якій об'єкти це категорії, а морфизмы це функтори. Це категорія категорій. Але категорія усіх категорій повинна включати в себе також, що веде до появи парадоксів того ж типу, що роблять безліч всіх множин неможливим. Однак, існує категорія всіх малих категорій
Cat
(яка велика, і відповідно своїм членом не є). "Мала" це така категорія, об'єкти якої складають безліч, в протилежність чогось, більшого, ніж безліч. Зауважте, що в теорії категорій навіть нескінченне незліченну безліч вважається "малим". Напевно, я розповідаю вам це, оскільки вважаю вражаючим, як одні і ті ж структури повторюються на різних рівнях абстракції. Пізніше ми побачимо, що функтори теж складають категорію.
Вправи
  1. Можна перетворити типовий конструктор `Maybe` в функтор, визначивши
    fmap _ _ = Nothing
    який ігнорує обидва своїх аргументу? (Підказка: перевірте функторні закони)
  2. Доведіть функторні закони для функтора `reader` (Підказка: там все просто).
  3. Реалізуйте функтор reader на вашому другому улюбленому мовою (перший, природно, Haskell).
  4. Доведіть закони функторів списку. Почніть з припущення, що закони виконуються для хвостовій частині списку (тобто використовувати індукцію).
Подяки
Гершем Базерман люб'язно продовжує рецензування тексту. Автор вдячний йому за терпіння і висловлені ідеї.

leshabirukov: приблизно перша половина голови переведена спільно мною і Bodigrim, який також брав участь у редагуванні остаточної версії. Неузгодженість нашого праці лежить на моїй совісті.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.