Pull to refresh

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

Reading time 6 min
Views 81K
Original author: Peteris Krumins
Интересно, что термин "функтор" означает совершенно разные вещи в разных языках программирования. Возьмем, например, 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 в статье ошибочна.
Tags:
Hubs:
+38
Comments 39
Comments Comments 39

Articles