Что такое функтор в функциональном программировании?

Question

Я встречал термин «Functor» несколько раз, читая различные статьи о функциональном программировании, но авторы обычно предполагают, что читатель уже понимает этот термин. Просмотр в Интернете предоставил либо чрезмерно технические описания (см. статья Википедии ), либо невероятно расплывчатые описания (см. Раздел «Функторы» на этом учебном веб-сайте ).

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

Редактировать : Хотя меня интересует теория, стоящая за этим термином, я интересуюсь не столько теорией, сколько реализацией и практическим использованием концепции.

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

Answer 1

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

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

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

  • Тип ключа, который будет использоваться в двоичном дереве

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

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

  Другое применение функторов 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, то

    fmap even
    

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

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

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

    • Преобразование Nothing в Nothing и Just 7 в Just False

    В Хаскеле это свойство выражается в виде типа fmap:

    fmap :: (Functor t) => (a -> b) -> t a -> t b
    

    где у нас теперь есть маленький t, что означает «любой тип в классе Functor».

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

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

Answer 2

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

Функтор - это контейнер типа a , который при воздействии на функцию, отображающую из a → b , дает контейнер типа б .

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

Answer 3

Есть три разных значения, мало связанных между собой!

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

  module type Order = sig
      type t
      val compare: t -> t -> bool
  end;;
  
  
  module Integers = struct
      type t = int
      let compare x y = x > y
  end;;
  
  module ReverseOrder = functor (X: Order) -> struct
      type t = X.t
      let compare x y = X.compare y x
  end;;
  
  (* We can order reversely *)
  module K = ReverseOrder (Integers);;
  Integers.compare 3 4;;   (* this is false *)
  K.compare 3 4;;          (* this is true *)
  
  module LexicographicOrder = functor (X: Order) -> 
    functor (Y: Order) -> struct
      type t = X.t * Y.t
      let compare (a,b) (c,d) = if X.compare a c then true
                           else if X.compare c a then false
                           else Y.compare b d
  end;;
  
  (* compare lexicographically *)
  module X = LexicographicOrder (Integers) (Integers);;
  X.compare (2,3) (4,5);;
  
  module LinearSearch = functor (X: Order) -> struct
      type t = X.t array
      let find x k = 0 (* some boring code *)
  end;;
  
  module BinarySearch = functor (X: Order) -> struct
      type t = X.t array
      let find x k = 0 (* some boring code *)
  end;;
  
  (* linear search over arrays of integers *)
  module LS = LinearSearch (Integers);;
  LS.find [|1;2;3] 2;;
  (* binary search over arrays of pairs of integers, 
     sorted lexicographically *)
  module BS = BinarySearch (LexicographicOrder (Integers) (Integers));;
  BS.find [|(2,3);(4,5)|] (2,3);;
  

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

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

  class Functor f where
      fmap :: (a -> b) -> (f a -> f b)
  
  instance Functor [] where      -- lists are a functor
      fmap = map
  
  instance Functor Maybe where   -- Maybe is option in Haskell
      fmap f (Just x) = Just (f x)
      fmap f Nothing = Nothing
  
  fmap (+1) [2,3,4]   -- this is [3,4,5]
  fmap (+1) (Just 5)  -- this is Just 6
  fmap (+1) Nothing   -- this is Nothing
  

Итак, это особый тип конструкторов типов, и он мало связан с функторами в Ocaml!

• В императивных языках это указатель на функцию.

Answer 4

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

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

Примером функтора является Map.Make; module StringMap = Map.Make (String);; создает модуль карты, который работает с картами со строковыми ключами.

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

Answer 5

У тебя довольно много хороших ответов. Я введу:

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

Есть два способа взглянуть на это. Например, списки являются функторами некоторого типа. То есть, учитывая алгебру над типом «а», вы можете сгенерировать совместимую алгебру списков, содержащих вещи типа «а». (Например: карта, которая переводит элемент в одноэлементный список, содержащий его: 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

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

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

Answer 6

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

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

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

выдержка из Typeclassopedia for Functor: «Простая интуиция заключается в том, что Functor представляеткакой-то «контейнер», наряду с возможностью равномерно применять функцию к каждому элементу в контейнере »

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

Cheers

Answer 7

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

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

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

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

module SSet = MakeSet(StringCaseEqual);;

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

Тобу сравнил функторы с шаблонами в C ++, которые я считаю вполне подходящими.

Answer 8

В комментарии к ответу , получившему наибольшее количество голосов, пользователь Вей Ху спрашивает:

Я понимаю как функторы ML, так и функторы Haskellно не хватает понимания, чтобы связать их вместе.Какая связь между этими двумя понятиями в теоретическом смысле?

Примечание : я не знаю ML, поэтому, пожалуйста, простите и исправьте все связанные ошибки.

Давайте сначала предположим, что мы все знакомы с определениями «категория» и «функтор».

Компактный ответ будет состоять в том, что «функторы Хаскелла» являются (эндо-) функторами *, тогда как *«ML-функторы» - это функторы G : ML -> ML'.

Здесь Hask - это категория, образованная типами и функциями Haskell между ними, а также ML и ML' - категории, определенные структурами ML.

Примечание : Есть некоторые технические проблемы с созданием Hask категории, но есть способы обойти их.

Из теории теориив перспективе это означает, что Hask -функционер является картой F типов Haskell:

data F a = ...

вместе с картой fmap функций Haskell:

instance Functor F where
    fmap f = ...

ML почти такой же, хотя здесь нет канонического fmap рефератаИон, о котором я знаю, поэтому давайте определим один:

signature FUNCTOR = sig
  type 'a f
  val fmap: 'a -> 'b -> 'a f -> 'b f
end

То есть f карт ML -типов и fmap карт ML -функций, поэтому

functor StructB (StructA : SigA) :> FUNCTOR =
struct
  fmap g = ...
  ...
end

является функтором F: StructA -> StructB.

Answer 9

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

Практическое использование функтора в монаде, и вы можете найти много уроков по монадам, если посмотрите на это.

Answer 10

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

Чтобы получить подсказку о значении слова «функтор» в Haskell, спросите 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

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

Подкласс типов функторов и раздел Функторы, аппликативные функторы и моноиды из Learn You Haskell for Great Good приведите несколько примеров, где этот конкретный Концепция полезна. (Резюме: много мест!: -))

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