В Функциональном программировании, что такое функтор?

Я столкнулся с термином 'Функтор' несколько раз при чтении различных статей о функциональном программировании, но авторы обычно предполагают, что читатель уже понимает термин. Оглядывание в сети обеспечило любой чрезмерно технические описания (см. статью Wikipedia), или невероятно неопределенные описания (см. раздел по Функторам в этом ocaml-учебном веб-сайте).

Кто-то может любезно определить термин, объяснить его использование и возможно обеспечить пример того, как Функторы создаются и используются?

Править: В то время как я интересуюсь теорией позади термина, я меньше интересуюсь теорией, чем я нахожусь в реализации и практическом применении понятия.

Редактирование 2: Похож существует некоторое перекрестное-terminoligy продолжение: я конкретно обращаюсь к Функторам функционального программирования, не функциональным объектам C++.

218
задан Erik Forbes 26 November 2013 в 02:28
поделиться

11 ответов

Слово «функтор» происходит от теории категорий, которая является очень общим, очень абстрактным разделом математики. Разработчики функциональных языков заимствовали его как минимум двумя способами.

  • В семействе языков ML функтор - это модуль, который принимает один или несколько других модулей в качестве параметра. Это считается продвинутой функцией, и у большинства начинающих программистов с ней возникают трудности.

    В качестве примера реализации и практического использования вы можете раз и навсегда определить вашу любимую форму сбалансированного двоичного дерева поиска как функтор, и он будет принимать в качестве параметра модуль, который предоставляет:

    • Тип ключа для использования в двоичном дереве

    • Функция полного упорядочения по клавишам

    Как только вы это сделаете, вы можете навсегда использовать одну и ту же реализацию сбалансированного двоичного дерева. (Тип значения, хранящегося в дереве, обычно остается полиморфным - дереву не нужно смотреть на значения, кроме как копировать их, тогда как дерево определенно должно иметь возможность сравнивать ключи, и оно получает функцию сравнения из параметр функтора.)

    Другое применение функторов ML - это многоуровневые сетевые протоколы . Ссылка ведет на действительно потрясающую статью группы CMU Fox; в нем показано, как использовать функторы для построения более сложных уровней протокола (например, TCP) на типах более простых слоев (например, IP или даже непосредственно через Ethernet). Каждый уровень реализован как функтор, который принимает в качестве параметра уровень ниже него. Структура программного обеспечения фактически отражает то, как люди думают о проблеме, в отличие от слоев, существующих только в сознании программиста. В 1994 году, когда эта работа была опубликована, это было большим событием.

    Яркий пример использования функторов ML в действии можно найти в статье ML Module Mania , в которой содержится готовый к публикации (то есть пугающий) пример работы функторов. Для блестящего, ясного и ясного объяснения системы модулей машинного обучения (в сравнении с другими видами модулей) прочтите первые несколько страниц блестящей статьи Ксавье Лероя по POPL 1994 г. Типы манифестов, модули и отдельная компиляция .

  • В Haskell и в некоторых связанных чисто функциональных языках Functor является классом типов . Тип принадлежит к классу типа (или, точнее говоря, тип «является экземпляром» класса типа), когда тип обеспечивает определенные операции с определенным ожидаемым поведением. Тип T может принадлежать классу Functor , если он имеет определенное поведение, подобное коллекции:

    • Тип T параметризован по сравнению с другим типом, который вам следует воспринимайте как тип элемента коллекции. Тип полной коллекции будет примерно таким, как T Int , T String , T Bool , если вы содержите целые числа, строки или логические значения соответственно. Если тип элемента неизвестен, он записывается как параметр типа a , как в T a .

      Примеры включают списки (ноль или более элементов типа a ), тип Maybe (ноль или один элемент типа a ), наборы элементов типа a , массивы элементов типа a , всевозможные деревья поиска, содержащие значения типа a , и многие другие, о которых вы можете подумать.

    • Другое свойство, которому T должен удовлетворять, заключается в том, что если у вас есть функция типа a -> b (функция для элементов), то вы должны иметь возможность возьмите эту функцию и создайте связанную функцию в коллекциях. Вы делаете это с помощью оператора fmap , который является общим для всех типов в классе типов Functor . Оператор фактически перегружен, поэтому, если у вас есть функция даже с типом Int -> Bool , то

       fmap даже
       

      - это перегруженная функция, которая может делать много замечательных вещей:

      • Преобразовать список целых чисел в список логиров

      • Преобразовать дерево целых чисел на дерево логических островов

      • Ничего - Ничего и просто 7 Просто ложный

      в Haskell, это свойство выражается путем предоставления типа FMAP :

       FMAP :: (функтор T) => (A -> B  ) -> TA -> TB
       

      Если у нас сейчас есть маленький T , что означает «любой тип в класс ».

    , чтобы сделать длинную историю короткой, в Haskell Функтор - это своего рода коллекция, для которой если вам дают функцию на элементах, FMAP вернет функцию на коллекциях . Как вы можете себе представить, это идея, которая может быть широко использована повторно использована, поэтому она благословлена ​​как часть стандартной библиотеки Haskell.

Как обычно, люди продолжают изобрести новые, полезные абстракции, и вы можете захотеть посмотреть в , применяющих функторов, для которых наилучшая ссылка может быть бумага, называемая , применимое программированием с эффектами от Conor McBride и Ross Патерсон.

266
ответ дан 23 November 2019 в 04:11
поделиться
[

] Проще говоря, объект функции или функции, это объект класса, который может быть вызван точно так же, как и функция.[

] [

]В C++:[

] [

]Это то, как вы пишете функцию[

] [
void foo()
{
    cout << "Hello, world! I'm a function!";
}
] [

]Это то, как вы пишете functor[

] [
class FunctorClass
{
    public:
    void operator ()
    {
        cout << "Hello, world! I'm a functor!";
    }
};
] [

]Теперь вы можете сделать это:[

] [
foo(); //result: Hello, World! I'm a function!

FunctorClass bar;
bar(); //result: Hello, World! I'm a functor!
] [

]Что делает это настолько замечательным, так это то, что вы можете сохранить состояние в классе - представьте, если вы хотите спросить функцию, сколько раз она была вызвана. Нет способа сделать это аккуратно, инкапсулированно. В объекте функции, как и в любом другом классе: у вас будет некая переменная экземпляра, которую вы инкрементируете в операторе [] ()[], и некий метод для проверки этой переменной, и все будет аккуратно, как вам угодно.[

].
-6
ответ дан 23 November 2019 в 04:11
поделиться
[

] Функтор специально не связан с функциональным программированием. Это просто "указатель" на функцию или какой-то объект, который может быть вызван так же, как и функция.[

].
-10
ответ дан 23 November 2019 в 04:11
поделиться
[

]В OCaml это параметризованный модуль.[

] [

]Если вы знаете C++, подумайте о OCaml functor как о шаблоне. На C++ есть только шаблоны классов, а в масштабе модуля работают functors.[

] [

]Примером functor является Map.Make; []модуль StringMap = Map.Make (String);[] строит модуль карты, который работает со String-клавишными картами.[

] [

]С помощью простого полиморфизма не получится что-то вроде StringMap; нужно сделать некоторые предположения по клавишам. Модуль String содержит операции (сравнение и т.д.) над полностью упорядоченным строковым типом, и functor будет ссылаться на операции, содержащиеся в модуле String. С объектно-ориентированным программированием можно было бы сделать нечто подобное, но с методом накладных расходов.[

].
15
ответ дан 23 November 2019 в 04:11
поделиться
[

] Вот [] статья о функторах из программируемого POV[], а затем более конкретно [] о том, как они выглядят на языках программирования [].[

] [

] Практическое использование functor находится в монаде, и вы можете найти много учебников по монадам, если вы ищете это.[

].
5
ответ дан 23 November 2019 в 04:11
поделиться
[

] Есть довольно хороший пример в книге O'Reilly OCaml, которая находится на сайте Inria (который, к сожалению, на момент написания этой книги находится внизу). Я нашел очень похожий пример в этой книге, используемый компанией caltech: [] Введение в OCaml (pdf ссылка) []. Соответствующий раздел - это глава о функторах (стр. 139 книги, стр. 149 в PDF).[

] [

]В книге есть functor под названием MakeSet, который создает структуру данных, состоящую из списка, и функции для добавления элемента, определения того, есть ли элемент в списке, и для поиска элемента. Функция сравнения, которая используется для определения, находится ли элемент в/нет в списке, была параметризована (что делает MakeSet functor вместо модуля).[

] [

]У них также есть модуль, который реализует функцию сравнения, так что он делает сравнение строк с нечувствительностью к регистру.[

] [

]Используя functor и модуль, который реализует сравнение, они могут создать новый модуль в одной строке:[

] [
module SSet = MakeSet(StringCaseEqual);;
] [

]который создает модуль для структуры данных множества, использующий нечувствительные к регистру сравнения. Если вы хотите создать набор, использующий регистрозависимые сравнения, то вам нужно просто реализовать новый модуль сравнения вместо нового модуля структуры данных.[

] [

]Tobu сравнивал functors с шаблонами на C++, что, на мой взгляд, вполне уместно[

].
7
ответ дан 23 November 2019 в 04:11
поделиться
[

] Есть три различных значения, не очень близких![

] [
    ] [
  • ][

    ]В Ocaml это параметризованный модуль. Смотрите [] manual[]. Я думаю, что лучший способ провести их поиск - на примере: (написано быстро, может быть багги)[

    ] [
    ][]тип модуля Order = sig
     тип t
     val compare: t -> t -> bool
    конец;..;
    
    
    модуль Интеграторы = структура
     тип t = int
     давайте сравним x y = x > y
    конец;..;
    
    модуль ReverseOrder = functor (X: Порядок) -> структура
     тип t = X.t
     давайте сравним x y = X.сравним y x
    конец;..;
    
    (* Мы можем заказать наоборот *)
    модуль K = ReverseOrder (Целочисленные);;
    Целочисленные сравнить 3 4;; (* это ложь *)
    К.сравнить 3 4; (* это правда *)
    
    модуль LexicographicOrder = functor (X: Заказ) -> 
     functor (Y: Order) -> struct
     тип t = X.t * Y.t
     давайте сравним (a,b) (c,d) = если X.сравнить c, то истинно
     иначе, если X.сравнивать c a, то ложь
     иначе Y. сравнить b d
    конец;..;
    
    (* сравнить лексикографию *)
    модуль X = LexicographicOrder (Целочисленные) (Целочисленные);;
    X.сравнивать (2,3) (4,5);;
    
    модуль LinearSearch = functor (X: Порядок) -> структура
     тип t = массив X.t
     давайте найдем x k = 0 (* какой-нибудь скучный код *)
    конец;..;
    
    модуль BinarySearch = functor (X: Порядок) -> структура
     тип t = массив X.t
     давайте найдем x k = 0 (* какой-нибудь скучный код *)
    конец;..;
    
    (* линейный поиск по массивам целых чисел *)
    модуль LS = LinearSearch (Целочисленные);;
    LS.find [|1;2;3] 2;;
    (* двоичный поиск по массивам пар целых чисел, 
     отсортировано лексикографически *)
    модуль BS = BinarySearch (LexicographicOrder (Целочисленные) (Целочисленные));;
    BS.find [|(2,3);(4,5)|] (2,3);;
    [][
    ][
  • ] [
] [

]Теперь вы можете быстро добавить множество возможных заказов, способы формирования новых заказов, легко выполнить двоичный или линейный поиск по ним. Общее программирование FTW.[

] [
    ] [
  • ][

    ]В функциональных языках программирования, таких как Haskell, это означает некоторые конструкторы типов (параметризованные типы, такие как списки, наборы), которые могут быть "картированы". Точнее говоря, functor []f[] оснащен [](a -> b) -> (f a -> f b)[]. Это происходит из теории категорий. Статья в Википедии, на которую вы ссылаетесь, это использование.[

    ] [
    ][]класс Functor f где
     fmap :: (a -> b) -> (f a -> f b)
    
    Например, Фанктор [] где -- списки - это фанктор.
     отображение = карта
    
    Например, Фанктор Может быть, где... Может быть, это вариант в Хаскелле.
     fmap f (Просто x) = Просто f x)
     fmap f Ничто = Ничто
    
    fmap (+1) [2,3,4] -- это [3,4,5]
    fmap (+1) (Всего 5) -- это всего лишь 6.
    fmap (+1) Nothing -- this is Nothing
    [][
    ][
  • ] [
] [

] Итак, это особый вид конструкторов типа, и имеет мало общего с фанкторами в Ocaml![

] [
    ] [
  • ]В императивных языках это указатель на функцию.[
  • ] [
]
37
ответ дан 23 November 2019 в 04:11
поделиться
[

]Учитывая другие ответы и то, что я собираюсь написать сейчас, я бы сказал, что это довольно перегруженное слово, но в любом случае. ...[

] [

]Для подсказки относительно значения слова "functor" в Хаскелле, спросите GHCi:[

] [
Prelude> :info Functor
class Functor f where
  fmap :: forall a b. (a -> b) -> f a -> f b
  (GHC.Base.<$) :: forall a b. a -> f b -> f a
        -- Defined in GHC.Base
instance Functor Maybe -- Defined in Data.Maybe
instance Functor [] -- Defined in GHC.Base
instance Functor IO -- Defined in GHC.Base
] [

]Так что, в принципе, functor в Хаскелле - это то, что может быть отображено на карте. Другой способ сказать, что functor - это нечто, что можно рассматривать как контейнер, который можно попросить использовать данную функцию для преобразования содержащегося в ней значения; таким образом, для списков []fmap[] совпадает с []map[], для []Maybe[], []fmap f (Just x) = Just (f x)[], []fmap f Nothing = Nothing[] и т.д. и т.п. [

] [

][]В подразделе Functor typeclass[] и разделе []Functors, Applicative Functors and Monoids[] из []Learn You a Haskell for Great Good[] приведены некоторые примеры того, где эта конкретная концепция полезна. (Резюме: много мест! :-))[

] [

]Обратите внимание, что к любой монаде можно относиться как к фанктору, и на самом деле, как отмечает Крейг Стунц, наиболее часто используемые фанкторы, как правило, являются монадами.... OTOH, иногда удобно сделать тип экземпляром типового стекла Functor, не задумываясь о том, чтобы превратить его в монаду. (Например, в случае с []ZipList[] из []Control.Applicative[], упомянутым на []одной из вышеупомянутых страниц [])[

].
5
ответ дан 23 November 2019 в 04:11
поделиться

Лучший ответ на этот вопрос можно найти в "Typeclassopedia" Брента Йорги.

В этом выпуске Monad Reader содержится точное определение того, что такое functor, а также множество определений других понятий, а также диаграмма. (Моноидное, Аппликативное, Монад и другие понятия объясняются и рассматриваются по отношению к functor).

http://haskell.org/sitewiki/images/8/85/TMR-Issue13.pdf

отрывок из Типеклассопдии для Функтора: "Простая интуиция заключается в том, что Фанктор представляет собой "контейнер" некоторых сортировка, наряду со способностью единообразно применять функцию к каждому элементу в контейнер"

Но на самом деле вся типографская клавиатура - это очень рекомендуемое чтение, которое удивительно просто. В некотором смысле, вы можете видеть, что типографское стекло представлено там как параллель с шаблоном дизайна в объекте в том смысле, что они дают вам словарь для заданного поведения или способности.

Ура

7
ответ дан 23 November 2019 в 04:11
поделиться

Другие ответы здесь завершены, но попробую еще одно объяснение использования ФП функтора . Возьмите это как аналогию:

Функтор представляет собой контейнер типа A , который, когда он подвергается функции, которая отображается из A b , дает Контейнер типа B .

В отличие от абстрагированного использования функционального указателя в C ++, здесь функция не функция; Скорее, это то, что ведет себя последовательно, когда подвергается функции .

61
ответ дан 23 November 2019 в 04:11
поделиться

У вас довольно много хороших ответов. Я расскажу:

Функтор в математическом смысле - это особый вид функции на алгебре. Это минимальная функция, которая отображает одну алгебру в другую. «Минимальность» выражается законами функторов.

Есть два взгляда на это. Например, списки являются функторами некоторого типа. То есть, имея алгебру над типом «а», вы можете сгенерировать совместимую алгебру списков, содержащих элементы типа «а». (Например: карта, которая переносит элемент в содержащий его одноэлементный список: f (a) = [a]). Опять же, понятие совместимости выражается законами функторов.

С другой стороны, для функтора f "над" типом a (то есть, fa является результатом применения функтора f к алгебре типа a) и функции из g: a -> b, мы можем вычислить новый функтор F = (fmap g), который отображает fa в f b.Короче говоря, fmap - это часть F, которая отображает «части функтора» на «части функтора», а g - это часть функции, которая отображает «части алгебры» в «части алгебры». Он принимает функцию, функтор, и после завершения он также ЯВЛЯЕТСЯ функтором.

Может показаться, что в разных языках используются разные понятия функторов, но это не так. Они просто используют функторы над разными алгебрами. В OCamls есть алгебра модулей, и функторы над этой алгеброй позволяют присоединять новые объявления к модулю «совместимым» способом.

Функтор Haskell НЕ является классом типа. Это тип данных со свободной переменной, который удовлетворяет классу типа. Если вы готовы покопаться в нутро типа данных (без свободных переменных), вы можете переосмыслить тип данных как функтор над лежащей в основе алгеброй. Например:

data F = F Int

изоморфен классу Ints. Итак, F как конструктор значений - это функция, которая отображает Int в F Int, эквивалентную алгебру. Это функтор. С другой стороны, вы не получите здесь fmap бесплатно. Вот для чего нужно сопоставление с образцом.

Функторы хороши для «прикрепления» вещей к элементам алгебр алгебраически совместимым способом.

13
ответ дан 23 November 2019 в 04:11
поделиться
Другие вопросы по тегам:

Похожие вопросы: