что такое функторы в c
Функторы в языках программирования
Функторы в C++
Функторы в Standart ML
Сложно сформулировать в терминах ООП: функторы в ML являются общими реализациями интерфейсов. В терминах ML функторы являются частью системы модулей ML и они позволяют компоновать структуры.
structure LoudPlugin :> Plugin =
struct
fun perform ( ) = print «ВЫПОЛНЯЕМ ЗАДАНИЕ ГРОМКО!\n»
end ;
structure SilentPlugin :> Plugin =
struct
fun perform ( ) = print «выполняем задание тихо\n»
end ;
structure LoudPerformer = Performer ( LoudPlugin ) ;
structure SilentPerformer = Performer ( SilentPlugin ) ;
Это, скорее всего, самый простейший пример функторов Standard ML.
Функторы в Haskell
Функторы в Haskell является тем, чем и должны быть настоящие функторы. Функторы Haskell очень напоминают математические функторы из теории категорий. В теории категорий функтор F — это отображение между категориями, такое, что структура категории сохраняется или, другими словами, это гомоморфизм между двумя категориями.
В Haskell это определение реализовано в виде простого класса типа,
Чтобы понять, что он делает, думайте о fmap как о функции, которая применяет операцию к каждому элементу в каком-то контейнере.
instance Functor [ ] where
fmap = map
Но заметьте, что определение Functor ничего не говорит о сохранении структуры! Поэтому любой нормальный функтор должен неявно удовлетворять законам функторов, которые являются частью определения математических функторов. Есть два правила fmap :
fmap > fmap (g. h) = fmap g. fmap h
Первое правило гласит, что отображение тождественной функции на каждый элемент в контейнере не имеет никакого эффекта. Второе правило гласит, что композиция двух функций над каждым элементом в контейнере то же самое, что отображение первой функции, а затем отображение второй.
Другой пример функторов, который иллюстрирует их наиболее ярко, — это операции над деревьями. Подумайте о дереве, как контейнере, а затем примените функцию fmap к значениям дерева, сохраняя структуру дерева.
Давайте, для начала, определим дерево,
data Tree a = Node ( Tree a ) ( Tree a )
| Leaf a
deriving Show
В этом определении сказано, что тип Tree (дерево) является либо Node (ветвью) из двух Tree (левой и правой ветви) или Leaf (листом). Выражение deriving Show позволяет нам осматривать дерево через функцию show.
instance Functor Tree where
fmap g ( Leaf v ) = Leaf ( g v )
fmap g ( Node l r ) = Node ( fmap g l ) ( fmap g r )
Теперь давайте проиллюстрируем, как fmap работает с деревьями. Построим дерево со строковыми ( String ) листьями и применим функцию length над ними, чтобы узнать длину каждого листа.
Prelude> let tree = (Node (Node (Leaf «hello») (Leaf «foo»)) (Leaf «baar»))
Prelude> fmap length tree
Node (Node (Leaf 5) (Leaf 3)) (Leaf 4)
Здесь у нас построено следующее дерево,
И отображение length над ним даёт нам,
Еще один способ сказать, что fmap делает — отображает (в оригинале — поднимает) функцию из «нормального мира» в » f мир».
На самом деле функтором является фундаментальным классом типа в Haskell так как Монады, аппликативные функторы и стрелки — это всё функторы. Я бы сказал, что Haskell начинается там, где начинаются функторы.
Если вы хотите узнать больше о классах типа в Haskell, начните с превосходной статьи Typeclassopedia (начинается со стр. 17).
Функторы в Prolog
И, наконец, функторы в Prolog. Функторы в Prolog самые простые из всех. Можно рассмотреть два примера. Первый — это атом в начале структуры. Например, возьмём выражение,
Вот вам и функторы в Prolog.
Заключение
В данной статье показано, как такой простой термин, как «функтор» может относиться к совершенно к разным вещам в разных языках программирования. Поэтому, когда вы слышите термин «функтор», важно знать контекст, в котором оно используется.
И, тут такое дело… мне тут сказали, что, оказывается, человек, чью статью я перевёл, есть на хабре =)
А ещё говорят, что по часть по Prolog в статье ошибочна.
Что такое функторы в c
Совет 38. Проектируйте классы функторов для передачи по значению
Ни C, ни C++ не позволяют передавать функции в качестве параметров других функций. Вместо этого разрешается передавать указатели на функции. Например, объявление стандартной библиотечной функции qsort выглядит следующим образом:
void qsort(void *base, size_t nmemb, size_t size,
int (*cmpfcn)(const void*, const void*));
Function // Возврат по значению
for_each(InputIterator first, InputIterator last,
Function f);// Передача по значению
Честно говоря, передача по значению не гарантирована полностью, поскольку вызывающая сторона может явно задать типы параметров в точке вызова. Например, в следующем фрагменте for_each получает и возвращает функторы по ссылке:
void operator()(int x) <…>// в совете 40
typedef deque ::iterator DequeIntIter; // Вспомогательное определение
DoSomething d; // Создать объект функции
DoSomethng&>(di.begin(), // параметров DequeIntIter
di.end(), // и DoSomething&; в результате
d); // происходит передача
// и возврат по ссылке.
Пользователи STL почти никогда не используют эту возможность, а в некоторых реализациях алгоритмов STL при передаче объектов функций по ссылке программы даже не компилируются. В продолжение этого совета будем считать, что объекты функций всегда передаются по значению, поскольку на практике это почти всегда так.
Поскольку объекты функций передаются и возвращаются по значению, вы должны позаботиться о том, чтобы объект функции правильно работал при передаче подобным способом (то есть копированием). Для этого необходимо соблюдение двух условий. Во-первых, объекты функций должны быть небольшими, в противном случае копирование обойдется слишком дорого. Во-вторых, объекты функций должны быть мономорфными (то есть не полиморфными), поэтому в них не могут использоваться виртуальные функции. Второе требование связано с тем, что при передаче по значению объектов производных классов в параметрах базового класса происходит отсечение: в процессе копирования удаляются специализированные составляющие (другой пример проблемы отсечения в STL приведен в совете 3).
Бесспорно, эффективность является важным фактором, и предотвратить отсечение тоже необходимо, однако не все функторы малы и мономорфны. Одно из преимуществ объектов функций перед обычными функциями заключается в отсутствии ограничений на объем информации состояния. Некоторые объекты функций от природы «упитанны», и очень важно, чтобы они могли передаваться алгоритмам STL так же просто, как и их «тощие» собратья.
Столь же нереалистичен и запрет на полиморфные функторы. Иерархическое наследование и динамическое связывание относятся к числу важнейших особенностей C++, и при проектировании классов функторов они могут принести такую же пользу, как и в других областях. Что такое классы функторов без наследования? C++ без «++». Итак, необходимы средства, которые бы позволяли легко передавать большие и/или полиморфные объекты функций с соблюдением установленного в STL правила о передаче функторов по значению.
Такие средства действительно существуют. Достаточно взять данные и/или полиморфные составляющие, которые требуется сохранить в классе функтора, перенести их в другой класс и сохранить в классе функтора указатель на этот новый класс. Рассмотрим пример создания класса полиморфного функтора с большим количеством данных:
template // BPFC = «Big Polymorphic
class BPFC: // Functor class»
public // Базовый класс описан
Widget w; // Класс содержит большой объем
int х; // данных, поэтому передача
// была бы неэффективной
virtual void operator()(const T& val) const; // Виртуальная функция.
Мы выделяем все данные и виртуальные функции в класс реализации и создаем компактный, мономорфный класс, содержащий указатель на класс реализации:
template //Новый класс реализации
class BPFCImpl <//для измененного BPFC.
Widget w; // Все данные, ранее находившиеся
int х; // в BPFC, теперь размещаются
BPFCImpl(); // В полиморфных классах нужен
virtual void operator()(const T& val) const;
friend class BPFC ; // Разрешить BPFC доступ к данным
class BPFC: // Компактная, мономорфная версия
BPFCImpl * pImpl; // Все данные BPFC
void operator()(const T& val) const; // Функция не является
Материал изложен довольно кратко, поскольку описанные базовые приемы хорошо известны в кругах C++. В книге «Effective C++» этой теме посвящен совет 34. В книге «Приемы объектно-ориентированного проектирования» [6] соответствующая методика называется «паттерн Bridge». Саттер в своей книге «Exceptional C++» [8] использует термин «идиома Pimpl ».
В сущности, копирующий конструктор BPFC — единственное, о чем вам придется побеспокоиться в контексте данного примера, поскольку при передаче и получении функторов от функций STL всегда происходит копирование (помните, что говорилось выше о передаче по значению?). Из этого вытекают два требования: компактность и мономорфизм.
Совет 39. Реализуйте предикаты в виде «чистых» функций
Для начала разберемся с основными терминами.
• «Чистой» функцией называется функция, возвращаемое значение которой зависит только от параметров. Если f — «чистая» функция, а x и y — объекты, то возвращаемое значение f(x, y) может измениться только в случае изменения х или у.
В C++ все данные, используемые «чистыми» функциями, либо передаются в виде параметров, либо остаются постоянными на протяжении всего жизненного цикла функции (естественно, такие постоянные данные объявляются с ключевым словом const). Если бы данные, используемые «чистой» функцией, могли изменяться между вызовами, то вызов этой функции в разные моменты времени с одинаковыми параметрами мог бы давать разные результаты, что противоречит определению «чистой» функции.
Из сказанного должно быть понятно, что нужно сделать, чтобы предикаты были «чистыми» функциями. Мне остается лишь убедить читателя в том, что эта рекомендация обоснована. Для этого придется ввести еще один термин.
Обещаю, что новых терминов больше не будет. Теперь давайте разберемся, почему следует выполнять рекомендацию данного совета.
В совете 38 объяснялось, что объекты функций передаются по значению, поэтому при проектировании необходимо позаботиться о возможном копировании. Для объектов функций, являющихся предикатами, существует и другой аргумент в пользу специальной поддержки копирования. Алгоритмы могут создавать копии функторов и хранить их определенное время перед применением, причем некоторые реализации алгоритмов этим активно пользуются. Важнейшим следствием этого факта является то, что предикатные функции должны быть «чистыми».
class BadPredicate: // Базовый класс описан
BadPredicate(): timesCalles(0) <> // Переменная timesCalled
bool operator()(const Widget&) <
return ++timesCalled = 3;
Предположим, класс BadPedicate используется для исключения третьего объекта Widget из контейнера vector :
vector vw; // Создать вектор и заполнить его
vww.erase(remove_if(vw.begin(), // Удалить третий объект Widget.
vw.end(), // связь между erase и remove_if
BadPredcate()), // описана в совете 32
Программа выглядит вполне разумно, однако во многих реализациях STL из вектора vw удаляется не только третий, но и шестой элемент!
FwdIterator remove_if(FwdIterator begin, FwdIterator end, Predicate p) <
begin = find_if(begin, end, p);
if (begin==end) return begin;
return remove_copy_if(++next, end, begin, p);
Чтобы обойти эту лингвистическую ловушку, проще всего объявить функцию operator() с ключевым словом const в предикатном классе. В этом случае компилятор не позволит изменить переменные класса:
bool operator()(const Widget&) const <
return ++timesCalled == 3; // Ошибка! Изменение локальных данных
> // в константной функции невозможно
Ранее в этом совете уже упоминалось о том, что всюду, где STL ожидает получить предикатную функцию, может передаваться либо реальная функция, либо объект предикатного класса. Этот принцип действует в обоих направлениях. В любом месте, где STL рассчитывает получить объект предикатного класса, подойдет и предикатная функция (возможно, модифицированная при помощи ptr_fun — см. совет 41). Теперь вы знаете, что функции operator() в предикатных классах должны быть «чистыми» функциями, поэтому ограничение распространяется и на предикатные функции. Следующая функция также плоха в качестве предиката, как и объекты, созданные на основе класса BadPredcate :
bool anotherBadPredicate(const Widget&, const Widget&) <
static int timesCalled = 0; // Нет! Нет! Нет! Нет! Нет! Нет!
return ++timesCalled == 3; // Предикаты должны быть «чистыми»
> // функциями, а «чистые» функции
// не имеют состояния
Как бы вы ни программировали предикаты, они всегда должны быть «чистыми» функциями.
Совет 40. Классы функторов должны быть адаптируемыми
Предположим, у нас имеется список указателей Widget* и функция, которая по указателю определяет, является ли объект Widget «интересным»:
bool isInteresting(const Widget *pw);
list ::iterator i = find_if(widgetPts.begin(), widgetPts.end(),
… // Обработка первого «интересного»
> // указателя на Widget
list ::iterator i = find_if(widgetPtrs.begin(), widgetPtrs.end(),
not1(isInteresting)); // Ошибка! He компилируется
Перед not1 к функции isInteresting необходимо применить ptr_fun :
Впрочем, не совсем так. unary_function и binary_function являются шаблонами, поэтому прямое наследование от них невозможно. Вместо этого при наследовании используются структуры, созданные на основе этих шаблонов, а для этого необходимо указать аргументы типов. Для unary_function задается тип параметра, получаемого функцией operator() вашего класса функтора, а также тип возвращаемого значения. Для binary_function количество типов увеличивается до трех: типы первого и второго параметров operator() и тип возвращаемого значения.
class MeetsThreshold: public std::unary_function <
Meets Threshold(const T& threshold);
bool operator()(const WidgetS) const;
Вернемся к определению WidgetNameCompare:
bool operator()(const Widget* lhs, const Widget* rhs) const;
Помните, что базовые классы unary_function и binary_function выполняют только одну важную функцию — они предоставляют определения типов, необходимые для работы адаптеров, поэтому наследование от этих классов порождает адаптируемые объекты функций. Это позволяет использовать в программах следующие конструкции:
list ::reverse_iterator i1 = // Найти последний объект
find_if(widgets.rbegin(), widgets.rend(), // Widget, не соответствующий
not1(MeetsThreshold (10))); // пороговому критерию 10
//(что бы это ни означало)
Widget w(аргументы конструктора); // Найти первый объект Widget.
list ::iterator i2 = // предшествующий w в порядке
find_if(widgets.begin(), widgets.end(), // сортировки, определенном
bind2nd(WidgetNameCompare(), w)); // WidgetNameCompare
Иногда в классе функтора бывает разумно определить несколько форм вызова, тем самым отказавшись от адаптируемости (примеры таких ситуаций приведены в советах 7, 20, 23 и 25), но это скорее исключение, а не правило. Адаптируемость важна, и о ней следует помнить при разработке классов функторов.
Совет 41. Разберитесь, для чего нужны ptr_fun, mem_fun и mem_fun_ref
Загадочные функции ptr_fun/mem_fun/mem_fun_ref часто вызывают недоумение. В одних случаях их присутствие обязательно, в других они не нужны… но что же они все-таки делают? На первый взгляд кажется, что они бессмысленно загромождают имена функций. Их неудобно вводить и читать, они затрудняют понимание программы. Что это — очередные пережитки прошлого STL (другие примеры приводились в советах 10 и 18) или синтаксическая шутка, придуманная членами Комитета по стандартизации с извращенным чувством юмора?
В C++ существуют три варианта синтаксиса вызова функции f для объекта x :
f(x); // Синтаксис 1: f не является функцией класса
//(вызов внешней функции)
x.f(); // Синтаксис 2: f является функцией класса, а х
// является объектом или ссылкой на объект
p->f(); // Синтаксис 3: f является функцией класса,
// а р содержит указатель на х
Рассмотрим гипотетическую функцию, предназначенную для «проверки» объектов Widget :
void test(Widget& w); // Проверить объект w. Если объект не проходит
// проверку, он помечается как «плохой»
Допустим, у нас имеется контейнер объектов Widget :
vector vw; // vw содержит объекты Widget
Для проверки всех объектов Widget в контейнере vw можно воспользоваться алгоритмом for_each :
for_each(vw.begin(), vw.end(), test); // Вариант 1 (нормально компилируется)
void test(); // Выполнить самопроверку. Если проверка
… // завершается неудачей, объект помечается
В идеальном мире мы могли бы воспользоваться for_each для вызова функции Widget::test всех объектов вектора vw :
Более того, если бы наш мир был действительно идеальным, алгоритм for_each мог бы использоваться и для вызова Widget::test в контейнере указателей Widget* :
list lpw; // Список lpw содержит указатели
for_each(lpw.begin(), lpw.end(), // Вариант 3 (не компилируется!)
Но подумайте, что должно было бы происходить в этом идеальном мире. Внутри функции for_each в варианте 1 вызывается внешняя функция, поэтому должен использоваться синтаксис 1. Внутри вызова for_each в варианте 2 следовало бы использовать синтаксис 2, поскольку вызывается функция класса. А внутри функции for_each в варианте 3 пришлось бы использовать синтаксис 3, поскольку речь идет о функции класса и указателе на объект. Таким образом, нам понадобились бы триразных версии for_each — разве такой мир можно назвать идеальным?
Function for_each(InputIterator begin, InputIterator end, Function f) <
Жирный шрифт используется для выделения того, что при вызове for_each используется синтаксис 1. В STL существует всеобщее правило, согласно которому функции и объекты функций всегда вызываются в первой синтаксической форме (как внешние функции). Становится понятно, почему вариант 1 компилируется, а варианты 2 и 3 не компилируются — алгоритмы STL (в том числе и for_each ) жестко закодированы на использование синтаксиса внешних функций, с которым совместим только вариант 1.
Принцип работы mem_fun и mem_fun_ref прост, хотя для пущей ясности желательно рассмотреть объявление одной из этих функций. В действительности они представляют собой шаблоны функций, причем существует несколько вариантов mem_fun и mem_fun_ref для разного количества параметров и наличия-отсутствия константности адаптируемых ими функций классов. Одного объявления вполне достаточно, чтобы разобраться в происходящем:
template // Объявление mem_fun для неконстантных
// на которую ссылается указатель
list lpw; // См. ранее
mem_fun(&Widget::test)); // Теперь нормально компилируется
for_each(vw.begin(), vw.end(), test); // См. ранее, вариант 1.
компилируется, а следующие конструкции не компилируются:
for_each(vw.begin(), vw.end(), &Widget::test); // См. ранее, вариант 2.
for_each(lpw.begin(), lpw.end(), &Widget::test); // См. ранее, вариант 3.
for_each(vw.begin(), vw.end(), ptr_fun(test)); // Компилируется и работает,
Существует и другой подход — использовать ptr_fun в случае крайней необходимости. Если функция отсутствует там, где необходимы определения типов, компилятор выдает сообщение об ошибке. Тогда вы возвращаетесь к программе и включаете в нее пропущенный вызов.
С mem_fun и mem_fun_ref ситуация принципиально иная. Эти функции всегда должны применяться при передаче функции компонентам STL, поскольку помимо определения типов (необходимых или нет) они адаптируют синтаксис вызова, который обычно используется для функций класса, к синтаксису, принятому в STL. Если не использовать эти функции при передаче указателей на функции класса, программа не будет компилироваться.
Совет 42. Следите за тем, чтобы конструкция less означала operator Widget обладает атрибутами weight и maxSpeed :
size_t weight() const;
size_t maxSpeed() const;
template<> // Специализация std::less
struct std::less : // для Widget: такой подход
public // считается крайне нежелательным!
Widget, // Базовый класс описан
bool operator() (const Widget& lhs, const Widget& rhs) const <
template // Специализация std::less
struct less >: // для boost::shared_ptr
bool operator()(const boost::shared_ptr & a,
const boost::shared_ptr & b) const <
return less ()(a.get(), b.get()); // shared_ptr::get возвращает
>; // из объекта shared_ptr
В данном примере специализация выглядит вполне разумно, поскольку специализация less всего лишь гарантирует, что порядок сортировки умных указателей будет совпадать с порядком сортировки их встроенных аналогов. К сожалению, наша специализация less для класса Widget преподносит неприятный сюрприз.
bool operator()(const Widget& lhs, const Widget& rhs) const <
Функторы (глава книги «Теория категорий для программистов»)
Это седьмая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре:
Функторы
За понятием функтора стоит очень простая, но мощная идея (как бы заезжено это ни прозвучало). Просто теория категорий полна простых и мощных идей. Функтор есть отображение между категориями. Пусть даны две категории C и D, а функтор F отображает объекты из C в объекты из D — это функция над объектами. Если a — это объект из C, то будем обозначать его образ из D как F a (без скобок). Но ведь категория — это не только объекты, но еще и соединяющие их морфизмы. Функтор также отображает и морфизмы — это функция над морфизмами. Но морфизмы отображаются не как попало, а так, чтобы сохранять связи. А именно, если морфизм f из C связывает объект a с объектом b,
то образ f в D, F f, связывает образ a с образом b:
(Надеемся, что такая смесь математических обозначений и синтаксиса Haskell понятна читателю. Мы не будем писать скобки, применяя функторы к объектам или морфизмам.)
Как видите, функтор сохраняет структуру: что было связано во входной категории, будет связано и в выходной. Но этим структура не исчерпывается: необходимо также поддержать композицию морфизмов. Если h — композиция f и g :
то потребуем, чтобы его образ под действием F был композицией образов f и g:
Наконец, потребуем, чтобы все единичные(тождественные) морфизмы из C отображались в единичные морфизмы из D:
Здесь ida — это единичный морфизм объекта a, а idF a — единичный морфизм объекта F a.
Заметим, что все эти условия существенно ограничивают круг функций, подходящих в качестве морфизмов. Функторы должны сохранять структуру категории. Если представить себе категорию как набор объектов, переплетенных морфизмами, то функтор не имеет права оборвать ни одной нити этого кружева. Он может объединить несколько объектов, он может склеить морфизмы в один, но никогда не разрывает связей. Это ограничение аналогично понятию непрерывности из математического анализа. В этом смысле функторы «непрерывны» (хотя существует еще более ограничивающее определение непрерывности функторов). Как и любая функция, функтор может быть и склеивающими, и вкладывающими. Аспект вложения наиболее ярко проявляется, когда исходная категория намного меньше целевой. В предельном случае исходная категория представляет собой категорию 1, состоящую из одного объекта и одного (единичного) морфизма. Функтор из категории 1 в любую другую категорию просто выбирает определенный объект из этой категории. Имеет место полная аналогия с морфизмами из синглтона, выбирающими элементы из целевых множеств. Аспект склеивания, доведенный до абсурда, наблюдается в константном функторе Δc. Он отображает каждый объект исходной категории в определенный объект c целевой категории, а всякий морфизм — в единичный морфизм idc. Это как черная дыра, засасывающая все в точку сингулярности. Мы вернемся к рассмотрению этого функтора при обсуждении пределов и копределов.
Функторы в программировании
Вернёмся на землю, в мир программирования. Итак, у нас есть категория типов и функций. Рассмотрим функторы, отображающие эту категорию в себя — так называемые эндофункторы. Что представляет собой эндофунктор в категории типов? В первую очередь, он сопоставляет одним типам другие. Подобные отображения на самом деле нам знакомы, это типы, параметризованные другими типами. Рассмотрим несколько примеров.
Функтор Maybe
Определение Maybe есть отображение типа a в тип Maybe a:
Следуя сказанному выше, дадим определение fmap для Maybe :
Чтобы показать, что конструктор типов Maybe вместе с функцией fmap составляют функтор, осталось доказать, что fmap сохраняет единичные морфизмы и композицию. Эти утверждения называются «функториальными законами», но они просто удостоверяют сохранение структуры категории.
Метод эквивалентных преобразований
Докажем функториальные законы методом эквивалентных преобразований, который является типичной техникой доказательств в Haskell. Метод опирается на то, что функции в Haskell определены набором равенств: левая часть равна правой, обе они могут быть подставлены друг вместо друга (возможно, при подстановке потребуется переименовать переменные во избежание конфликтов). Можно как подставить тело функции вместо ее вызова (инлайнинг), так и вызов функции вместо ее тела (рефакторинг). Рассмотрим в качестве примера тождественную функцию:
Теперь покажем, что fmap сохраняет композицию:
Начнём со случая Nothing :
Теперь пришло время Just :
Стоит подчеркнуть, что для функций с побочными эффектами в стиле С++, метод эквивалентных преобразований не работает. Рассмотрим пример:
Метод эквивалентных преобразований позволил бы развернуть square и получить
Определенно, такая трансформация некорректна и меняет результат выражения. Несмотря на это, если определить square как макрос, препроцессор C++ воспользуется методом эквивалентных преобразований с катастрофическим результатом.
Снова Maybe
Это функция высшего порядка, принимающая функцию как аргумент и возвращающая функцию. А вот другой вариант, без каррирования:
Классы типов
Как же абстракция функтора реализована в Haskell? Используется механизм классов типов. Класс типов задаёт семейство типов, поддерживающих единый интерфейс. К примеру, класс объектов, сравнимых на равенство определяется так:
можно определить равенство точек:
Функторы в C++
Но как нам специализировать этот шаблон для разных функторов? К сожалению, частичная специализация шаблонных функций C++ запрещена. Нельзя написать:
Вместо этого приходится вернуться к перегрузке функций, в результате мы возвращаемся к первоначальному определению fmap (без каррирования):
Это определение работает, но для правильной перегрузки требуется второй аргумент. Более общее определение fmap просто игнорируется.
Функтор List
Для лучшего понимания значимости функторов в программировании стоит рассмотреть больше примеров. Любой тип, параметризуемый другим типом — кандидат на роль функтора. К примеру, обобщённые контейнеры параметризуются типом своих элементов, рассмотрим список, очень простой контейнер:
С её помощью мы можем, к примеру, возвести в квадрат ряд чисел:
Функтор Reader
Как и обычные функции, типовые функции нескольких аргументов можно применять частично. И когда мы даём стрелке один аргумент, она всё ещё ждёт другой. То есть,
Сработало! Минималист может ещё сократить запись, воспользовавшись префиксной формой:
теперь аргументы можно опустить, получая отождествление двух функций:
Комбинацию конструктора типов (->) r и такой реализации fmap называют «reader».
Функторы как контейнеры
Мы познакомились с примерами использования функторов в программировании для определения контейнеров общего назначения, или хотя бы объектов, содержащих какие-то значения того типа, которым функтор параметризован. Функтор reader кажется исключением, поскольку мы не думаем о функциях как о данных. Но как мы видели, к функциям применима мемоизация, когда вычисление сводится к поиску в таблице. Таблица это уже данные. С другой стороны, поскольку Haskell ленив, традиционный контейнер вроде списка может на деле реализовываться как функция. Посмотрите, например, на бесконечный список натуральных чисел, который можно описать так:
Поскольку наш функтор игнорирует свой типовый аргумент, будет естественным в реализации fmap игнорировать функциональный аргумент, — функцию не к чему применять:
В C++ это выглядит немного нагляднее (вот уж не думал, что скажу такое!), за счёт более чёткого различия между типовыми аргументами, которые работают на этапе компиляции, и значениями, работающими во время выполнения.
Несмотря на странный вид, функтор Const играет важную роль во многих построениях. В теории категорий это частный случай функтора Δc, упомянутого ранее — эндофункторной разновидности чёрной дыры. В будущем мы познакомимся с ним поближе.
Композиция функторов
Несложно убедиться, что для функторов между категориями композиция работает точно также, как для функций между множествами. Композиция двух функторов, при действии на объекты, есть просто композиция соответствующих отображений объектов, аналогичная ситуация с действием на морфизмы. После прыжка вдоль двух функторов, единичные морфизмы остаются единичными, также как и композиция морфизмов остаётся таковой для образов. Ничего особенного. В частности, легко сочетаются эндофункторы. Помните функцию maybeTail (ПП: из предыдущей главы)? Давайте её перепишем, применительно к стандартным спискам Haskell:
Но вспомните, что о fmap можно думать как о функции единственного аргумента:
и возвращает функцию типа
Затем первый fmap берёт получившуюся функцию и в свою очередь возвращает
Упражнения
Благодарности
Гершом Базерман любезно продолжает рецензирование текста. Автор благодарен ему за терпение и высказанные идеи.
leshabirukov: приблизительно первая половина главы переведена совместно мною и Bodigrim, который также участвовал в редактировании окончательной версии. Несогласованность нашего труда лежит на моей совести.