Функторы в языках программирования

http://www.catonmat.net/blog/on-functors/
  • Перевод
Интересно, что термин "функтор" означает совершенно разные вещи в разных языках программирования. Возьмем, например, C++. Каждый, кто освоил мастерство C++, знает, что класс, который реализует 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(: 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 :: (-> 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]

В этом простом примере, функцией Functorfmap является просто 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 в статье ошибочна.
Поделиться публикацией
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 38
    –28
    ОМГ как можно «functor» прочитать как функтор?
      +3
      фанктер?)
          –18
          Вы издеваетесь?

          Прослушайте в гугле, если не верите
          Пруф
            +6
            И? А слово «функция» вы по-русски тоже говорите «фанкшион»?
              –22
              А вы функшион?

              Ненадо путать слово «функция», которое нормально переводится с английского, с термином, у которого нет однозначного перевода в одно слово, следовательно используем термин с точным английским произношением фанктор (и произносить, конечно, желательно на английский манер)
                +16
                Вобщем-то есть вполне сложивщийся, устоявшийся как в математике, так и в программировании русский термин — функтор. Я не америку открываю и не сам это придумал. Как связано произношение в английском языке и русский перевод? Почему слово произносится слово фУнкция, но однокоренное с ним слов фАнкчер?
                  +4
                  лучше чтоб по корню слова смысл был понятен, здесь оно важнее. Без смысла слово мертвое)
                    +6
                    Нет. Если бы вы прочитали статьи в википедии, то уже знали бы, что термин пришёл из философии и имеет немецкое, а не английское происхождение.
                      +3
                      Вы один из тех, кто считает, что все языки произошли от английского и должны пользоваться правилами английского языка? Что-нибудь про латинский слышали? Древнее римляне тоже произносили слово functio с английским акцентом?
                      Вы еще скажите что слово sputnik надо читать как спатник.
                        –7
                        Прослушайте, я снова окажусь прав в произношении, ориентируясь на гугл
                        Пруф
                          +7
                          Попробуйте ориентироваться на здравый смысл. Иногда это полезней тыканья в гугл.
                    –21
                    По-моему Вы, кто вступил со мной в дискуссию, из тех людей, которые джаву называют явой.

                    Пожалуйста, называйте как хотите, не мне же за Вас краснеть
                      +8
                      1. Букур И., Деляну А. Введение в теорию категорий и функторов. М.: Мир, 1972
                      2. Двойственность Экмана–Хилтона и теория функторов в категории топологических пространств
                        Д. Б. Фукс
                        УМН, 21:2(128) (1966)

                      И т.д.

                      Кроме Qt есть ещё много прекрасного, разного. ;)
                        –11
                        Я в курсе :)
                        Когда с STL работал, говорил именно так, как правильно произносится, а минусовать мне за чью-то давнишнюю ошибку перевода нехорошо!

                        Честно, не знал, что в большом количестве литературы перевели как функтор, моя оплошность, однако это не делает предложенный мной вариант произношения неверным!
                          +6
                          Вы совершенно правы, «functor» читается как «фанктор», но «функтор» читается как «функтор», таков уж принятый термин.

                          Кроме того, «функтор» гораздо благозвучнее.
                            +3
                            Почему это «функтор» — ошибка перевода? Вам уже указали на то, что слова «функтор» и «функция» — однокоренные, соответственно никаких ваших фанктеров быть не может. Вы, конечно, молодец, что интересуетесь другими языками, но и свой забывать не стоит. Из-за «фанктеров» в языке появляются уродливые слова-кальки без языковой истории.
                          +8
                          Подтяните свои знания математики чтоб нам за вас не краснеть.
                            –19
                            А Вы, пардон, кто такой, чтобы быть за меня в ответе, да и говорить за всех?
                            –11
                            < Любое мое сообщение >

                            Минусуйте на здоровье!
                              +4
                              В кои-то веки соглашусь со мнением здешней общественности. Утверждать отсутствие однозначного перевода в одно слово для термина, используемого в русскоязычной литературе с середины XX века, как минимум, странно.
                        +12
                        плиз донт эпплай ë инкомплит нолидж ов инглиш ту рашн сайнтифик вокэбъюлари. итс джат рон.
                        +7
                        Мне как математику очень огорчительно видеть такую картину. Использование устоявшихся понятий в отличном от общепринятого смысле — зло, а люди, которые подменяют наименования, совершают акт вредительства.
                          +3
                          В ML и Хаскеле функторы не далеки от математического собрата. Жаль только что именно определение С++ наиболее популярно.
                            +1
                            Мне как математику крайне непонятно до сих пор, как правильно говорить:
                            «ко'мплексные» или «компле'ксные» (слово встречается не только для чисел),
                            «ре'шать» или «реша'ть».

                            Я о том, что среди математиков столько диалектов есть и многие даже гордятся своим произношением, также как и написанием греческого алфавита.

                            В общем, главное, чтобы человек был хороший :)
                            +2
                            Стоит заметить, что в Functor в Haskell — это эндофунктор.
                              0
                              Любопытная мысль. Я так понимаю, что вы подразумеваете все типы как объекты и функции как морфизмы. Тогда действительно получается эндофунктор. Но разве нельзя выделить пару полных подкатегорий и определить функтор между ними?
                                0
                                Так ведь
                                fmap : (a -> b) -> f a -> f b
                                обязан работать на любых типах и морфизмах.

                                В Control.Category есть класс Category, так что должно было быть так:
                                fmap : g a b -> h (f a) (f b)

                                  +2
                                  Ну я не про fmap конкретно говорил, я имел ввиду что в хаскеле наверно можно и не только функтор с такой сигнатурой объявить. Можно например попробовать рассмотреть подкатегорию списков и еще какую-нибудь, скажем Maybe и объявить функтор между ними.
                                  Получится функтор который объекты одной подкатегории (maybe) отображает в объекты другой (списки) и морфизмы одной (Maybe a -> Maybe b) в морфизмы другой ([a] -> [b]). Что-то вроде
                                  class MaybeListFunctor where
                                  f :: Maybe a -> [a]
                                  g :: (Maybe a -> Maybe b) -> [a] -> [b]
                                  чем не функтор?
                                  Простите если где ошибки, я в хаскеле не силен. А за Control.Category отдельное спасибо :) Покопаюсь на досуге
                                    +1
                                    Таким образом, конечно, можно.
                                    Кстати, если data-accessor сделать инстансом Control.Category, то можно будет писать
                                    (tail.head.second ^= 12) [('x', 125), ('a', 11)]
                                    :)
                                  +1
                                  В Haskell все функторы суть эндофункторы категории Hask, за пределы которой выйти нельзя. В частности именно поэтому в Prelude должно быть отношение Functor => Monad.

                                  Что касается выделения подкатегорий… в принципе можно сделать что-то подобное с помощью Control.Category, но это будет уже совсем не обычных хаскельный функтор.
                                    0
                                    Я выше написал что имел ввиду :) Понятно что выйти за пределы типов хаскеля нельзя и понятно почему Functor объявлен именно так. Меня просто заинтересовала мысль про эндофунктор, я об этом как-то не задумывался никогда (да собственно у меня опыта с хаскелем почти 0, поэтому я о нем мало думаю). Просто подумал, что можно ведь не только функтор с такой сигнатурой объявить. Да и не любой эндофунктор в хаскеле можно под эту сигнатуру подогнать. Это я просто так мыслю вслух, не обращайте внимания :)
                                +3
                                Хорошая статья. Впрочем, про функторы в Haskell можно рассказать ещё много чего :) самое удобное лично для меня представление — это функтор как механизм спуска по правой ветке дерева типов
                                  +1
                                  Это, к слову, является следствием того, что композиция (аппликативных) функторов — тоже (аппликативный) функтор. Для монад это уже, увы, неверно.
                                    0
                                    зато у монад по определению есть join
                                      +2
                                      И? Композиция у них от этого не появляется.
                                  +1
                                  Фига себе функторы в Прологе! Вот так пишешь-пишешь статьи , а толку (

                                  Мне кажется это надо срочно подправить.
                                  Функтор в Прологе это синоним терм, никаких больше значений он не имеет!
                                  Стандартный предикат functor/2 (из пункта 2), это предикат с названием 'functor'/2.

                                  Пример likes некорректен, потому что это предикат. В Прологе существует возможность функтор, вызывать как предикат типа:
                                  likes(X) :- X.
                                  Принимается терм, а вызывается уже предикат. Но это большая разница, так как в исходном Прологе это запрещено (как рефлексия в C++, хочется — нету, но кое-где появляется), так как такое использование термов ведет логикам второго порядка, а изначально Пролог — это хорновские дизъюнкты логики 1-го порядка.

                                  Напишу в послесловие, откуда появились функторы в Прологе и что они означают. На самом деле понятие функторов в Прологе наверное самое правильное, чем во всех остальных языках, так как оно сложилось еще в 30-е годы в математической логике.

                                  В математике часто встречаются определения: «для любого X существует Y», по сути дела это и есть функциональная зависимость. Так у этих функциональных зависимостей есть имя или его можно придумать, то договорились о краткой записи: plus(X, Y) — «для любого X, Y существует Z» и далее каким условиям удовлетворяет или в каких отношениях состоит. Благодаря, этому сокращению можно убрать все кванторы, кванторы существования заменяются функторами (отличия от функции теоритически нету, так как любому функтору можно поставить в соотвествию функцию, функцией чаще называют то, что эффективно вычислимо), а кванторы общности просто опускаются и остаются одни переменные.
                                    0
                                    Спасибо за информацию. Статья не моя, это перевод, поэтому исправлять я, вроде как, не имею морального права, но я дам добавлю ссылку на ваш комментарий в конец топика.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое