Я встречал термин «Functor» несколько раз, читая различные статьи о функциональном программировании, но авторы обычно предполагают, что читатель уже понимает этот термин. Просмотр в Интернете предоставил либо чрезмерно технические описания (см. Статью в Википедии ), либо невероятно расплывчатые описания (см. Раздел «Функторы» на этом веб-сайте ocaml-учебника ).
Может кто-нибудь любезно дать определение термину, объяснить его использование и, возможно, привести пример того, как создаются и используются функторы?
Изменить : Хотя меня интересует теория, стоящая за этим термином, меня интересует не столько теория, сколько реализация и практическое использование концепции.
Редактировать 2 : Похоже, что происходит некоторая кросс-терминология: я специально имею в виду Функторы функционального программирования, а не функциональные объекты C ++.
источник
fmap
сопоставляет функции. Существует два вида сопоставлений. Такой взгляд на вещи поможет понять теорию категорий (которая носит более общий характер). Я имею в виду, что интересно понять основную теорию категорий, чтобы помочь нам со всеми вещами теории категорий в Haskell (функтор, монады, ...).Ответы:
Слово «функтор» происходит от теории категорий, которая является очень общей, очень абстрактной областью математики. Он был заимствован дизайнерами функциональных языков как минимум двумя различными способами.
В семействе языков ML функтор - это модуль, который принимает один или несколько других модулей в качестве параметра. Это считается расширенной функцией, и большинство начинающих программистов испытывают трудности с этим.
В качестве примера реализации и практического использования вы можете раз и навсегда определить вашу любимую форму сбалансированного бинарного дерева поиска как функтор, и в качестве параметра он будет принимать модуль, который обеспечивает:
Тип ключа, который будет использоваться в двоичном дереве
Функция полного заказа на клавиши
Как только вы это сделаете, вы можете использовать одну и ту же сбалансированную двоичную реализацию дерева навсегда. (Тип значения, хранящегося в дереве, обычно остается полиморфным - дереву не нужно смотреть на значения, кроме как копировать их, тогда как дерево определенно должно иметь возможность сравнивать ключи, и оно получает функцию сравнения из параметр функтора.)
Другое применение функторов ML - это многоуровневые сетевые протоколы . Ссылка на действительно потрясающую статью группы CMU Fox; в нем показано, как использовать функторы для построения более сложных протокольных уровней (таких как TCP) на типах более простых уровней (таких как IP или даже напрямую через Ethernet). Каждый слой реализован как функтор, который принимает в качестве параметра слой под ним. Структура программного обеспечения фактически отражает то, как люди думают о проблеме, в отличие от уровней, существующих только в сознании программиста. В 1994 году, когда эта работа была опубликована, это было большое дело.
Для дикого примера функторов ML в действии вы можете увидеть статью ML Module Mania , в которой содержится публикуемый (то есть, страшный) пример функторов в действии . Чтобы получить блестящее, ясное и ясное объяснение системы модулей ML (со сравнениями с другими типами модулей), прочитайте первые несколько страниц блестящей 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
классе типов. Оператор действительно перегружен, так что если у вас есть функцияeven
с типомInt -> Bool
, топерегруженная функция, которая может делать много замечательных вещей:
Преобразовать список целых чисел в список логических значений
Преобразовать дерево целых чисел в дерево булевых
Преобразовать
Nothing
вNothing
иJust 7
вJust False
В Haskell это свойство выражается путем указания типа
fmap
:где у нас теперь есть маленький
t
, что означает «любой тип вFunctor
классе».Короче говоря, в Haskell функтор - это своего рода коллекция, для которой, если вам дана функция для элементов,
fmap
вам будет возвращена функция для коллекций . Как вы можете себе представить, это идея, которую можно широко использовать, поэтому она является частью стандартной библиотеки Haskell.Как обычно, люди продолжают изобретать новые, полезные абстракции, и вы можете захотеть взглянуть на аппликативные функторы, для которых лучшим справочным материалом может стать статья « Аппликативное программирование с эффектами » Конора МакБрайда и Росса Патерсона.
источник
then you have to be able to take that function and product a related function on collections
Вы имели в видуproduce
вместоproduct
?Другие ответы здесь полны, но я попробую другое объяснение использования функтора в FP . Возьмем это как аналогию:
В отличие от использования указателя на абстрагированную функцию в C ++, здесь функтор не является функцией; скорее это то, что ведет себя последовательно, когда подвергается функции .
источник
Есть три разных значения, мало связанных между собой!
В Ocaml это параметризованный модуль. Смотрите руководство . Я думаю, что лучший способ получить их - это пример: (написано быстро, может быть глючит)
Теперь вы можете быстро добавлять множество возможных заказов, способы формирования новых заказов, легко выполнять бинарный или линейный поиск по ним. Универсальное программирование FTW.
В функциональных языках программирования, таких как Haskell, это означает некоторые конструкторы типов (параметризованные типы, такие как списки, множества), которые могут быть отображены. Чтобы быть точным, функтор
f
оснащен(a -> b) -> (f a -> f b)
. Это имеет начало в теории категорий. Статья в Википедии, на которую вы ссылаетесь, является этим использованием.Итак, это особый тип конструкторов типов, и он не имеет ничего общего с функторами в Ocaml!
источник
В OCaml это параметризованный модуль.
Если вы знаете C ++, подумайте о функторе OCaml как о шаблоне. В C ++ есть только шаблоны классов, а функторы работают в масштабе модуля.
Примером функтора является Map.Make;
module StringMap = Map.Make (String);;
создает модуль карты, который работает с картами со строковыми ключами.Вы не могли бы достичь чего-то вроде StringMap только с полиморфизмом; вам нужно сделать некоторые предположения о ключах. Модуль String содержит операции (сравнение и т. Д.) Для полностью упорядоченного строкового типа, а функтор будет связывать операции, содержащиеся в модуле String. Вы можете сделать что-то подобное с объектно-ориентированным программированием, но у вас будут накладные расходы на метод.
источник
Вы получили довольно много хороших ответов. Я передам:
Функтор в математическом смысле - это особый вид функции в алгебре. Это минимальная функция, которая отображает алгебру в другую алгебру. «Минимальность» выражается законами функтора.
Есть два способа посмотреть на это. Например, списки являются функторами некоторого типа. То есть, учитывая алгебру над типом «а», вы можете сгенерировать совместимую алгебру списков, содержащих вещи типа «а». (Например: карта, которая переводит элемент в одноэлементный список, содержащий его: f (a) = [a]) Опять же, понятие совместимости выражается законами функторов.
С другой стороны, учитывая, что функтор f "над" типом a (то есть fa является результатом применения функтора f к алгебре типа a) и функцию из g: a -> b, мы можем вычислить новый функтор F = (fmap g), который отображает fa на f b. Короче говоря, fmap является частью F, которая отображает «части функтора» на «части функтора», а g является частью функции, которая отображает «части алгебры» в «части алгебры». Он принимает функцию, функтор, и когда он завершен, он тоже является функтором.
Может показаться, что разные языки используют разные понятия функторов, но это не так. Они просто используют функторы над различными алгебрами. У OCamls есть алгебра модулей, а функторы над этой алгеброй позволяют вам присоединять новые объявления к модулю «совместимым» способом.
Функтор Haskell НЕ является классом типа. Это тип данных со свободной переменной, который удовлетворяет классу типа. Если вы хотите разобраться в сущности типа данных (без свободных переменных), вы можете переосмыслить тип данных как функтор над базовой алгеброй. Например:
данные F = F Int
изоморфен классу инт. Таким образом, F, как конструктор значений, является функцией, которая отображает Int в F Int, эквивалентную алгебру. Это функтор. С другой стороны, вы не получаете fmap бесплатно здесь. Вот для чего нужно сопоставление с образцом.
Функторы хороши для «прикрепления» вещей к элементам алгебры алгебраически совместимым способом.
источник
Лучший ответ на этот вопрос найден в "Typeclassopedia" Brent Yorgey.
В этом выпуске Monad Reader содержится точное определение того, что такое функтор, а также множество определений других понятий и диаграммы. (Monoid, Applicative, Monad и другие концепции объясняются и рассматриваются по отношению к функтору).
http://haskell.org/sitewiki/images/8/85/TMR-Issue13.pdf
отрывок из Typeclassopedia для Functor: «Простая интуиция заключается в том, что Functor представляет некоторый« контейнер »вместе со способностью равномерно применять функцию к каждому элементу в контейнере»
Но на самом деле вся тип-классопедия очень рекомендуется для чтения, что удивительно легко. В некотором смысле вы можете видеть представленный там класс типов как параллель к шаблону проектирования в объекте в том смысле, что они дают вам словарный запас для данного поведения или возможностей.
ура
источник
Есть довольно хороший пример в книге O'Reilly OCaml, которая находится на веб-сайте Инрии (которая на момент написания статьи, к сожалению, не работает). В этой книге я нашел очень похожий пример, используемый caltech: Введение в OCaml (pdf link) . Соответствующим разделом является глава о функторах (стр. 139 в книге, стр. 149 в PDF).
В книге у них есть функтор MakeSet, который создает структуру данных, состоящую из списка, и функции для добавления элемента, определения наличия элемента в списке и поиска элемента. Функция сравнения, которая используется для определения того, находится ли она в / не в наборе, была параметризована (что делает MakeSet функтором вместо модуля).
У них также есть модуль, который реализует функцию сравнения, так что он выполняет сравнение строк без учета регистра.
Используя функтор и модуль, который реализует сравнение, они могут создать новый модуль в одну строку:
это создает модуль для заданной структуры данных, которая использует сравнения без учета регистра. Если вы хотите создать набор, в котором используются сравнения с учетом регистра, вам просто нужно реализовать новый модуль сравнения вместо нового модуля структуры данных.
Тобу сравнил функторы с шаблонами в C ++, которые я считаю вполне подходящими.
источник
Учитывая другие ответы и то, что я собираюсь опубликовать сейчас, я бы сказал, что это довольно сильно перегруженное слово, но в любом случае ...
Чтобы получить подсказку о значении слова «функтор» в Haskell, спросите GHCi:
Так что, по сути, функтор в Haskell - это то, что можно отобразить. Другой способ сказать, что функтор - это нечто, что можно рассматривать как контейнер, который можно попросить использовать данную функцию для преобразования значения, которое он содержит; Таким образом, для списков,
fmap
совпадает сmap
, дляMaybe
,fmap f (Just x) = Just (f x)
, иfmap f Nothing = Nothing
т.д.В подразделе класса типов Functor и разделе « Функторы, аппликативные функторы и моноиды « вы учите хакел »за великое благо» приводятся примеры того, как эта конкретная концепция полезна. (Резюме: много мест! :-))
Обратите внимание, что любую монаду можно рассматривать как функтор, и на самом деле, как указывает Крейг Штунц, наиболее часто используемые функторы, как правило, являются монадами ... ОТО, иногда удобно сделать тип экземпляром класса типов Functor не вдаваясь в проблемы сделать его монадой. (Например, в случае
ZipList
сControl.Applicative
, упомянутым на одной из вышеупомянутых страниц .)источник
Вот статья о функторах из POV программирования , а затем более конкретно, как они появляются в языках программирования .
Практическое использование функтора в монаде, и вы можете найти много уроков по монадам, если посмотрите на это.
источник
В комментарии к ответу , получившему наибольшее количество голосов , пользователь Wei Hu спрашивает:
Примечание : я не знаю ML, поэтому, пожалуйста, простите и исправьте все ошибки, связанные с ними.
Давайте сначала предположим, что мы все знакомы с определениями «категория» и «функтор».
Компактным ответом будет то, что «функторы Хаскеля» являются (эндо-) функторами,
F : Hask -> Hask
а «функторы ML» - функторамиG : ML -> ML'
.Здесь
Hask
есть категория формируется типов Haskell и функций между ними, а так жеML
иML'
такие категории , определяемые ML структурами.Примечание : есть некоторые технические проблемы с созданием
Hask
категории, но есть способы их обойти.С теоретической точки зрения категории это означает, что
Hask
-functor - это картаF
типов Haskell:вместе с картой
fmap
функций Haskell:ML почти такой же, хотя
fmap
я не знаю никакой канонической абстракции, поэтому давайте определим одну:То есть
f
картыML
-типы иfmap
картыML
-функции, такфунктор
F: StructA -> StructB
.источник
«Функтор - это отображение объектов и морфизмов, которое сохраняет композицию и идентичность категории».
Давайте определим, что такое категория?
Что держит категория?
Итак, мы должны отобразить объекты и сохранить композицию после применения нашего Functor.
Давайте представим, что «A» - это наша категория, в которой есть объекты ['a', 'b'] и существует морфизм a -> b
Теперь нам нужно определить функтор, который может отображать эти объекты и морфизмы в другую категорию «B».
Допустим, функтор называется «Может быть»
Итак, категория «В» выглядит следующим образом.
Пожалуйста, нарисуйте еще один круг, но на этот раз с «Возможно a» и «Возможно b» вместо «a» и «b».
Все выглядит хорошо, и все объекты сопоставлены
«а» стало «может быть», а «б» стало «возможно, б».
Но проблема в том, что мы должны сопоставить морфизм от «а» до «б».
Это означает, что морфизм a -> b в «A» должен соответствовать морфизму «Maybe a» -> «Maybe b».
морфизм из a -> b называется f, затем морфизм из 'Maybe a' -> 'Maybe b' называется 'fmap f'
Теперь давайте посмотрим, что функция «f» делала в «A», и посмотрим, сможем ли мы повторить ее в «B».
Определение функции 'f' в 'A':
е берет а возвращает б
определение функции 'f' в 'B':
f берет Может а и возвращает Может б
давайте посмотрим, как использовать fmap для отображения функции 'f' из 'A' в функцию 'fmap f' в 'B'
определение fmap
Итак, что мы здесь делаем?
Мы применяем функцию «f» к «x», которая имеет тип «a». Специальное сопоставление с образцом 'Nothing' происходит из определения
Functor Maybe
.Итак, мы отобразили наши объекты [a, b] и морфизмы [f] из категории «A» в категорию «B».
Это Функтор!
источник
Грубый Обзор
В функциональном программировании функтор - это, по сути, конструкция, поднимающая обычные унарные функции (т. Е. С одним аргументом) в функции между переменными новых типов. Гораздо проще писать и поддерживать простые функции между простыми объектами и использовать функторы для их подъема, а затем вручную писать функции между сложными объектами-контейнерами. Еще одним преимуществом является написание простых функций только один раз, а затем их повторное использование через различные функторы.
Примеры функторов включают массивы, функторы «возможно» и «либо», фьючерсы (см., Например, https://github.com/Avaq/Fluture ) и многие другие.
иллюстрация
Рассмотрим функцию построения полного имени человека из имени и фамилии. Мы можем определить его
fullName(firstName, lastName)
как функцию двух аргументов, что, однако, не подходит для функторов, которые имеют дело только с функциями одного аргумента. Чтобы исправить это, мы собираем все аргументы в один объектname
, который теперь становится единственным аргументом функции:А что если у нас много людей в массиве? Вместо того, чтобы вручную просматривать список, мы можем просто повторно использовать нашу функцию с
fullName
помощьюmap
метода, предусмотренного для массивов с короткой строкой кода:и использовать его как
Это будет работать, когда каждая запись в нашей
nameList
является объект , предоставляющий какfirstName
иlastName
свойства. Но что, если некоторые объекты этого не делают (или вообще не являются объектами)? Чтобы избежать ошибок и сделать код более безопасным, мы можем заключить наши объекты вMaybe
тип (например, https://sanctuary.js.org/#maybe-type ):где
Just(name)
- контейнер, содержащий только допустимые имена иNothing()
специальное значение, используемое для всего остального. Теперь вместо того, чтобы прерывать (или забывать) проверку правильности наших аргументов, мы можем просто повторно использовать (поднять) нашу исходнуюfullName
функцию с другой строкой кода, опять же на основеmap
метода, на этот раз предоставленного для типа Maybe:и использовать его как
Теория категорий
Functor в теории категорий является отображение между двумя категориями уважающих состав их морфизмов. В компьютерном языке основной интересующей категорией является та, чьи объекты являются типами (определенными наборами значений), а морфизмы являются функциями
f:a->b
от одного типаa
к другому типуb
.Например, возьмем
a
в качествеString
типа типb
Number иf
функцию, отображающую строку в ее длину:Здесь
a = String
представлен набор всех строк иb = Number
набор всех чисел. В этом смыслеa
иb
представляют, и представляют объекты в категории множеств (которая тесно связана с категорией типов, причем здесь разница не существенна). В категории множеств морфизмы между двумя наборами - это точно все функции из первого множества во второе. Таким образом, наша функция длиныf
- это морфизм из набора строк в набор чисел.Поскольку мы рассматриваем только заданную категорию, соответствующие Функторы из нее в себя являются картами, отправляющими объекты объектам, и морфизмы в морфизмы, которые удовлетворяют определенным алгебраическим законам.
Пример:
Array
Array
может означать много вещей, но только одна вещь - это Functor - конструкция типа, отображающая типa
в тип[a]
всех массивов типаa
. Например,Array
функтор отображает типString
в тип[String]
(набор всех массивов строк произвольной длины) и устанавливает типNumber
в соответствующий тип[Number]
(набор всех массивов чисел).Важно не путать карту Функтора
с морфизмом
a -> [a]
. Функтор просто отображает (связывает) типa
в тип[a]
как одно в другое. То, что каждый тип на самом деле представляет собой набор элементов, здесь не имеет значения. Напротив, морфизм является действительной функцией между этими наборами. Например, существует естественный морфизм (функция)который отправляет значение в массив из 1 элемента с этим значением в виде одной записи. Эта функция не является частью
Array
Functor! С точки зрения этого функтора,pure
это просто функция, как и любая другая, ничего особенного.С другой стороны, у
Array
Функтора есть вторая часть - часть морфизма. Который отображает морфизмf :: a -> b
в морфизм[f] :: [a] -> [b]
:Здесь
arr
любой массив произвольной длины со значениями типаa
, иarr.map(f)
это массив той же длины со значениями типаb
, записи которого являются результатами примененияf
к записямarr
. Чтобы сделать его функтором, должны выполняться математические законы отображения идентичности на идентичность и композиций на композиции, что легко проверить в этомArray
примере.источник
Не противоречит предыдущим теоретическим или математическим ответам, но Функтор также является Объектом (на объектно-ориентированном языке программирования), который имеет только один метод и эффективно используется в качестве функции.
Примером является интерфейс Runnable в Java, который имеет только один метод: run.
Рассмотрим этот пример, сначала в Javascript, который имеет функции первого класса:
Выход: [1, 4, 25, 100]
Метод map принимает функцию и возвращает новый массив, каждый элемент которого является результатом применения этой функции к значению в той же позиции в исходном массиве.
Чтобы сделать то же самое с Java, используя Functor, вам сначала нужно определить интерфейс, скажем:
Затем, если вы добавите класс коллекции, у которого есть функция map, вы можете сделать:
При этом используется встроенный подкласс IntMapFunction для создания Functor, который является ОО-эквивалентом функции из более раннего примера JavaScript.
Использование Функторов позволяет применять функциональные методы на языке ОО. Конечно, некоторые языки OO также поддерживают функции напрямую, поэтому это не требуется.
Ссылка: http://en.wikipedia.org/wiki/Function_object
источник
Array
функтор, ноArray(value)
дает только 1-элементные массивы.KISS: функтор - это объект, у которого есть метод карты.
Массивы в JavaScript реализуют карту и поэтому являются функторами. Обещания, потоки и деревья часто реализуют карту на функциональных языках, и когда они это делают, они считаются функторами. Метод map функтора берет свое собственное содержимое и преобразует каждое из них, используя обратный вызов преобразования, переданный в map, и возвращает новый функтор, который содержит структуру в качестве первого функтора, но с преобразованными значениями.
источник: https://www.youtube.com/watch?v=DisD9ftUyCk&feature=youtu.be&t=76
источник
Array
Конструкция типа определяет один функтор. Его экземпляры также называют «массивами», но они не являются функторами. Описание здесь должно быть более точным.На практике под функтором понимается объект, который реализует оператор вызова в C ++. В ocaml я думаю, что functor относится к чему-то, что принимает модуль в качестве входного и выходного другого модуля.
источник
Проще говоря, функтор или объект функции - это объект класса, который можно вызывать так же, как функцию.
В C ++:
Вот как вы пишете функцию
Вот как ты пишешь функтор
Теперь вы можете сделать это:
Что делает их такими замечательными, так это то, что вы можете сохранять состояние в классе - представьте, хотите ли вы спросить функцию, сколько раз она вызывается. Там нет никакого способа сделать это аккуратным, инкапсулированным способом. С функциональным объектом это так же, как и с любым другим классом: у вас есть некоторая переменная экземпляра, которую вы увеличиваете,
operator ()
и какой-то метод для проверки этой переменной, и все аккуратно, как вам угодно.источник
FunctorClass
соответствует первому Закону Функтора, но не могли бы вы набросать доказательство для второго Закона? Я не совсем это вижу.Функтор конкретно не связан с функциональным программированием. Это просто «указатель» на функцию или какой-то объект, который может быть вызван как функция.
источник