Интересно, что термин "функтор" означает совершенно разные вещи в разных языках программирования. Возьмем, например, C++. Каждый, кто освоил мастерство C++, знает, что класс, который реализует
Функторы в C++ являются сокращением от "функциональные объекты". Функциональный объект является экземпляром класса С++, в котором определён
Обратите внимание, что мы можем вызывать
Чаще всего функторы в С++ используются в качестве предикатов, псевдозамыканий или функций сравнения в алгоритмах STL. Вот вам ещё один пример. Предположим, у вас есть список целых чисел и вы хотите найти сумму всех четных и сумму всех нечетных. Идеальная задача для функтора и
Здесь экземпляр
Сложно сформулировать в терминах ООП: функторы в ML являются общими реализациями интерфейсов. В терминах ML функторы являются частью системы модулей ML и они позволяют компоновать структуры.
Например, предположим, что вы хотите написать систему плагинов, и вы хотите, чтобы все плагины реализовывали необходимый интерфейс, который, для простоты, включает в себя только функцию
Теперь, когда мы определили интерфейс (сигнатуру) для плагинов, мы можем реализовать два плагина, скажем,
И SilentPlugin,
Теперь мы приблизились к функторам. Функторы в ML принимают структуры в качестве аргументов, поэтому мы можем написать, что в качестве аргумента требуется
Этот функтор принимает
Теперь давайте попробуем использовать функтор
Будет выведено,
Это, скорее всего, самый простейший пример функторов Standard ML.
Функторы в Haskell является тем, чем и должны быть настоящие функторы. Функторы Haskell очень напоминают математические функторы из теории категорий. В теории категорий функтор F — это отображение между категориями, такое, что структура категории сохраняется или, другими словами, это гомоморфизм между двумя категориями.
В Haskell это определение реализовано в виде простого класса типа,
Оглядываясь, например, на ML, класс типа в Haskell подобен сигнатуре, за исключением того, что он определен для типа. Он определяет, какие операции должен реализовать тип, чтобы быть экземпляром данного класса. В данном случае, однако,
Чтобы понять, что он делает, думайте о
Простейший пример функторов — это обычные списки и функция
В этом простом примере, функцией
Давайте посмотрим, что это действительно верно, используя
Но заметьте, что определение Functor ничего не говорит о сохранении структуры! Поэтому любой нормальный функтор должен неявно удовлетворять законам функторов, которые являются частью определения математических функторов. Есть два правила
Первое правило гласит, что отображение тождественной функции на каждый элемент в контейнере не имеет никакого эффекта. Второе правило гласит, что композиция двух функций над каждым элементом в контейнере то же самое, что отображение первой функции, а затем отображение второй.
Другой пример функторов, который иллюстрирует их наиболее ярко, — это операции над деревьями. Подумайте о дереве, как контейнере, а затем примените функцию
Давайте, для начала, определим дерево,
В этом определении сказано, что тип
Теперь мы можем определить
В этом определении сказано, что
Теперь давайте проиллюстрируем, как
Здесь у нас построено следующее дерево,
И отображение
Еще один способ сказать, что
На самом деле функтором является фундаментальным классом типа в Haskell так как Монады, аппликативные функторы и стрелки — это всё функторы. Я бы сказал, что Haskell начинается там, где начинаются функторы.
Если вы хотите узнать больше о классах типа в Haskell, начните с превосходной статьи Typeclassopedia (начинается со стр. 17).
И, наконец, функторы в Prolog. Функторы в Prolog самые простые из всех. Можно рассмотреть два примера. Первый — это атом в начале структуры. Например, возьмём выражение,
функтором является первый атом —
Второй — это встроенный предикат под названием
Вот вам и функторы в Prolog.
В данной статье показано, как такой простой термин, как «функтор» может относиться к совершенно к разным вещам в разных языках программирования. Поэтому, когда вы слышите термин «функтор», важно знать контекст, в котором оно используется.
Оригинал статьи: www.catonmat.net/blog/on-functors
И, тут такое дело… мне тут сказали, что, оказывается, человек, чью статью я перевёл, есть на хабре =)
А ещё говорят, что по часть по Prolog в статье ошибочна.
operator()
, называется функтором. Теперь возьмём Standard ML. В ML функторы отображают структуры на структуры. Теперь Haskell. В Haskell функторы — это просто гомоморфизм над категориями. А в Prolog функтор означает атом в начале структуры. Все они различаются. Давайте подробнее рассмотрим каждый из них.Функторы в C++
Функторы в C++ являются сокращением от "функциональные объекты". Функциональный объект является экземпляром класса С++, в котором определён
operator()
. Если вы определите operator()
для C++ класса, то вы получите объект, который действует как функция, но может также хранить состояние. Например,#include <iostream> #include <string> class SimpleFunctor { std::string name_; public: SimpleFunctor(const char *name) : name_(name) {} void operator()() { std::cout << "Oh, hello, " << name_ << endl; } }; int main() { SimpleFunctor sf("catonmat"); sf(); // выводит "Oh, hello, catonmat" }
Обратите внимание, что мы можем вызывать
sf()
в функции main
, хотя sf
является объектом. Это потому, что в классе SimpleFunctor
для него определён operator()
.Чаще всего функторы в С++ используются в качестве предикатов, псевдозамыканий или функций сравнения в алгоритмах STL. Вот вам ещё один пример. Предположим, у вас есть список целых чисел и вы хотите найти сумму всех четных и сумму всех нечетных. Идеальная задача для функтора и
for_each
.#include <algorithm> #include <iostream> #include <list> class EvenOddFunctor { int even_; int odd_; public: EvenOddFunctor() : even_(0), odd_(0) {} void operator()(int x) { if (x%2 == 0) even_ += x; else odd_ += x; } int even_sum() const { return even_; } int odd_sum() const { return odd_; } }; int main() { EvenOddFunctor evenodd; int my_list[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; evenodd = std::for_each(my_list, my_list+sizeof(my_list)/sizeof(my_list[0]), evenodd); std::cout << "Сумма чётных: " << evenodd.even_sum() << "\n"; std::cout << "Сумма нечётных: " << evenodd.odd_sum() << std::endl; // вывод: // Сумма чётных: 30 // Сумма нечётных: 25 }
Здесь экземпляр
EvenOddFunctor
передается в for_each
. for_each итерируется по каждому элементу в my_list и вызывает функтор. После этого он возвращает копию функтора evenodd
, который содержит сумму чётных и нечётных элементов.Функторы в Standart ML
Сложно сформулировать в терминах ООП: функторы в ML являются общими реализациями интерфейсов. В терминах ML функторы являются частью системы модулей ML и они позволяют компоновать структуры.
Например, предположим, что вы хотите написать систему плагинов, и вы хотите, чтобы все плагины реализовывали необходимый интерфейс, который, для простоты, включает в себя только функцию
perform
. В ML необходимо сначала задать сигнатуру для плагинов,signature Plugin =
sig
val perform : unit -> unit
end;
Теперь, когда мы определили интерфейс (сигнатуру) для плагинов, мы можем реализовать два плагина, скажем,
LoudPlugin
и SilentPlugin
. Реализация осуществляется через структуры,structure LoudPlugin :> Plugin =
struct
fun perform () = print "ВЫПОЛНЯЕМ ЗАДАНИЕ ГРОМКО!\n"
end;
И SilentPlugin,
structure SilentPlugin :> Plugin =
struct
fun perform () = print "выполняем задание тихо\n"
end;
Теперь мы приблизились к функторам. Функторы в ML принимают структуры в качестве аргументов, поэтому мы можем написать, что в качестве аргумента требуется
Plugin
,functor Performer(P : Plugin) =
struct
fun job () = P.perform ()
end;
Этот функтор принимает
Plugin
в качестве аргумента P
и использует его для функции job
, которая вызывает функцию perform
у плагина P
.Теперь давайте попробуем использовать функтор
Performer
. Помните, что функтор возвращает структуру,structure LoudPerformer = Performer(LoudPlugin);
structure SilentPerformer = Performer(SilentPlugin);
LoudPerformer.job ();
SilentPerformer.job ();
Будет выведено,
ВЫПОЛНЯЕМ ЗАДАНИЕ ГРОМКО! выполняем задание тихо
Это, скорее всего, самый простейший пример функторов Standard ML.
Функторы в Haskell
Функторы в Haskell является тем, чем и должны быть настоящие функторы. Функторы Haskell очень напоминают математические функторы из теории категорий. В теории категорий функтор F — это отображение между категориями, такое, что структура категории сохраняется или, другими словами, это гомоморфизм между двумя категориями.
В Haskell это определение реализовано в виде простого класса типа,
class Functor f where
fmap :: (a -> b) -> f a -> f b
Оглядываясь, например, на ML, класс типа в Haskell подобен сигнатуре, за исключением того, что он определен для типа. Он определяет, какие операции должен реализовать тип, чтобы быть экземпляром данного класса. В данном случае, однако,
Functor
определен не над типами, а над конструктором типа f
. Это значит, Functor
— это то, что реализует функцию fmap
, которая принимает функцию (принимающую тип a
и возращающую тип b
) и значение типа f a
(тип построеный из конструктора типа f
, применяемый к типу a
) и возвращает значение типа f b
.Чтобы понять, что он делает, думайте о
fmap
как о функции, которая применяет операцию к каждому элементу в каком-то контейнере.Простейший пример функторов — это обычные списки и функция
map
, которая применяет функцию к каждому элементу в списке.Prelude> map (+1) [1,2,3,4,5]
[2,3,4,5,6]
В этом простом примере, функцией
Functor
'а fmap
является просто map
и конструктором типа f
является []
— конструктор типа списка. Поэтому Functor
, например, для списков определяется какinstance Functor [] where
fmap = map
Давайте посмотрим, что это действительно верно, используя
fmap
вместо map
,Prelude> fmap (+1) [1,2,3,4,5]
[2,3,4,5,6]
Но заметьте, что определение Functor ничего не говорит о сохранении структуры! Поэтому любой нормальный функтор должен неявно удовлетворять законам функторов, которые являются частью определения математических функторов. Есть два правила
fmap
:fmap id = id
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.Теперь мы можем определить
Functor
над деревьями Tree
,instance Functor Tree where
fmap g (Leaf v) = Leaf (g v)
fmap g (Node l r) = Node (fmap g l) (fmap g r)
В этом определении сказано, что
fmap
от функции g
над Leaf
со значением v
— это просто Leaf
из g
, применяемого к v
. А fmap
от g
над Node
с левой ветвью l
и правой r
— это просто Node
из fmap
, применяемого к значениям левой и правой ветви.Теперь давайте проиллюстрируем, как
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)
Здесь у нас построено следующее дерево,
* / \ / \ * "baar" / \ / \ / \ / \ "hello" "foo"
И отображение
length
над ним даёт нам, * / \ / \ * 4 / \ / \ / \ / \ 5 3
Еще один способ сказать, что
fmap
делает — отображает (в оригинале — поднимает) функцию из «нормального мира» в "f
мир".На самом деле функтором является фундаментальным классом типа в Haskell так как Монады, аппликативные функторы и стрелки — это всё функторы. Я бы сказал, что Haskell начинается там, где начинаются функторы.
Если вы хотите узнать больше о классах типа в Haskell, начните с превосходной статьи Typeclassopedia (начинается со стр. 17).
Функторы в Prolog
И, наконец, функторы в Prolog. Функторы в Prolog самые простые из всех. Можно рассмотреть два примера. Первый — это атом в начале структуры. Например, возьмём выражение,
?- likes(mary, pizza)
функтором является первый атом —
likes
.Второй — это встроенный предикат под названием
functor
. Он возвращает арность и функтор структуры. Например,?- functor(likes(mary, pizza), Functor, Arity).
Functor = likes
Arity = 2
Вот вам и функторы в Prolog.
Заключение
В данной статье показано, как такой простой термин, как «функтор» может относиться к совершенно к разным вещам в разных языках программирования. Поэтому, когда вы слышите термин «функтор», важно знать контекст, в котором оно используется.
Оригинал статьи: www.catonmat.net/blog/on-functors
И, тут такое дело… мне тут сказали, что, оказывается, человек, чью статью я перевёл, есть на хабре =)
А ещё говорят, что по часть по Prolog в статье ошибочна.