En programmation fonctionnelle, qu'est-ce qu'un foncteur?

224

J'ai rencontré le terme «Functor» à quelques reprises en lisant divers articles sur la programmation fonctionnelle, mais les auteurs supposent généralement que le lecteur comprend déjà le terme. La recherche sur le Web a fourni des descriptions excessivement techniques (voir l'article Wikipedia ) ou des descriptions incroyablement vagues (voir la section sur les foncteurs sur ce site Web de tutoriel ocaml ).

Quelqu'un peut-il gentiment définir le terme, expliquer son utilisation et peut-être fournir un exemple de la façon dont les foncteurs sont créés et utilisés?

Edit : Bien que je sois intéressé par la théorie derrière le terme, je suis moins intéressé par la théorie que par la mise en œuvre et l'utilisation pratique du concept.

Edit 2 : Il semble qu'il y ait une terminologie croisée en cours: je me réfère spécifiquement aux Functors de la programmation fonctionnelle, pas aux objets fonctionnels de C ++.

Erik Forbes
la source
4
Voir aussi: adit.io/posts/…
Vlad l'Impala
Très bonne réponse aussi: stackoverflow.com/a/45149475/1498178
toraritte
Si vous êtes plus intéressé par la mise en œuvre et l'utilisation pratiques que par la terminologie et la théorie stratosphériques derrière le concept, vous avez juste besoin d'un liner: un foncteur expose une fonction de "carte".
Richard Gomes
@RichardGomes IMHO Je pense que cela réduit le rôle d'un foncteur à une simple interface de type Java, ce qui n'est pas le cas. Un foncteur transforme les choses, il construit de nouveaux types à partir de ceux existants (dans Haskell) ce qui signifie que les types sont également mappés. fmapmappe les fonctions. Il existe deux types de mappages impliqués. Cette façon de voir les choses aidera à comprendre la théorie des catégories (qui est plus générale). Je veux dire qu'il est intéressant de comprendre la théorie des catégories de base pour nous aider avec toutes les choses sur la théorie des catégories dans Haskell (foncteur, monades, ...).
Ludovic Kuty
@VladtheImpala Le billet de blog est fantastique mais, même s'il aide beaucoup, j'aime garder à l'esprit qu'un foncteur construit (mappe) vers un autre type. J'aime particulièrement la phrase «Un foncteur F prend chaque type T et le mappe sur un nouveau type FT» dans Monads are like burritos . À mon humble avis, ce n'est pas seulement un contexte (une boîte) autour d'une valeur même si cela s'avère pratique pour voir des choses comme ça (Haskell PoV vs catégorie théorie PoV?)
Ludovic Kuty

Réponses:

273

Le mot «foncteur» vient de la théorie des catégories, qui est une branche très générale et très abstraite des mathématiques. Il a été emprunté par les concepteurs de langages fonctionnels d'au moins deux manières différentes.

  • Dans la famille de langages ML, un foncteur est un module qui prend un ou plusieurs autres modules en paramètre. Il est considéré comme une fonctionnalité avancée et la plupart des programmeurs débutants ont des difficultés avec cela.

    À titre d'exemple d'implémentation et d'utilisation pratique, vous pourriez définir une fois pour toutes votre forme préférée d'arbre de recherche binaire équilibré comme foncteur, et il prendrait comme paramètre un module qui fournit:

    • Le type de clé à utiliser dans l'arbre binaire

    • Une fonction de commande totale sur les touches

    Une fois que vous avez fait cela, vous pouvez toujours utiliser la même implémentation d'arbre binaire équilibré. (Le type de valeur stockée dans l'arborescence est généralement laissé polymorphe - l'arborescence n'a pas besoin de regarder des valeurs autres que de les copier, alors que l'arborescence doit absolument pouvoir comparer les clés, et elle obtient la fonction de comparaison de le paramètre du foncteur.)

    Une autre application des foncteurs ML est les protocoles réseau en couches . Le lien est vers un article vraiment formidable du groupe CMU Fox; il montre comment utiliser les foncteurs pour construire des couches de protocole plus complexes (comme TCP) sur des types de couches plus simples (comme IP ou même directement sur Ethernet). Chaque couche est implémentée comme un foncteur qui prend en paramètre la couche en dessous. La structure du logiciel reflète en fait la façon dont les gens pensent du problème, par opposition aux couches existant uniquement dans l'esprit du programmeur. En 1994, lorsque cet ouvrage a été publié, c'était une grosse affaire.

    Pour un exemple sauvage de foncteurs ML en action, vous pouvez voir le document ML Module Mania , qui contient un exemple publiable (c'est-à-dire effrayant) de foncteurs au travail. Pour une explication brillante, claire et limpide du système de modules ML (avec des comparaisons avec d'autres types de modules), lisez les premières pages du brillant article POPL 1994 de Xavier Leroy Types de manifestes, modules et compilation séparée .

  • Dans Haskell, et dans un langage fonctionnel pur apparenté, Functorest une classe de type . Un type appartient à une classe de type (ou plus techniquement, le type "est une instance de" la classe de type) lorsque le type fournit certaines opérations avec un certain comportement attendu. Un type Tpeut appartenir à une classe Functors'il a un certain comportement de type collection:

    • Le type Test paramétré sur un autre type, que vous devez considérer comme le type d'élément de la collection. Le type de la collection complète est alors quelque chose comme T Int, T String, T Bool, si vous contenons entiers, des chaînes ou des booléens respectivement. Si le type d'élément est inconnu, il est écrit en tant que paramètre de type a , comme dans T a.

      Les exemples incluent des listes (zéro ou plusieurs éléments de type a), le Maybetype (zéro ou un élément de type a), des ensembles d'éléments de type a, des tableaux d'éléments de type a, toutes sortes d'arbres de recherche contenant des valeurs de type a, et beaucoup d'autres vous peut penser.

    • L'autre propriété qui Tdoit satisfaire est que si vous avez une fonction de type a -> b(une fonction sur les éléments), alors vous devez être en mesure de prendre cette fonction et de produire une fonction associée sur les collections. Vous faites cela avec l'opérateur fmap, qui est partagé par chaque type de la Functorclasse de type. L'opérateur est en fait surchargé, donc si vous avez une fonction evende type Int -> Bool, alors

      fmap even

      est une fonction surchargée qui peut faire beaucoup de choses merveilleuses:

      • Convertir une liste d'entiers en une liste de booléens

      • Convertir un arbre d'entiers en arbre de booléens

      • Convertir Nothingvers Nothinget Just 7versJust False

      A Haskell, cette propriété s'exprime en donnant le type de fmap:

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

      où nous avons maintenant un petit t, ce qui signifie "tout type dans la Functorclasse."

    Pour faire court, dans Haskell, un foncteur est une sorte de collection pour laquelle si on vous donne une fonction sur les éléments, fmapvous rendrez une fonction sur les collections . Comme vous pouvez l'imaginer, c'est une idée qui peut être largement réutilisée, c'est pourquoi elle est bénie dans le cadre de la bibliothèque standard de Haskell.

Comme d'habitude, les gens continuent d'inventer de nouvelles abstractions utiles, et vous voudrez peut-être examiner les foncteurs applicatifs , pour lesquels la meilleure référence peut être un article intitulé Programmation Applicative avec Effets par Conor McBride et Ross Paterson.

Norman Ramsey
la source
7
Je comprends à la fois les foncteurs ML et les foncteurs Haskell, mais je n'ai pas la perspicacité de les relier ensemble. Quelle est la relation entre ces deux, dans un sens théorique de catégorie?
Wei Hu
6
@Wei Hu: La théorie des catégories n'a jamais eu de sens pour moi. Le mieux que je puisse dire, c'est que les trois notions impliquent la cartographie.
Norman Ramsey
16
Selon ce wiki Haskell: en.wikibooks.org/wiki/Haskell/Category_theory , c'est comme ceci: Une catégorie est une collection d'objets et de morphismes (fonctions), où les morphismes vont des objets d'une catégorie à d'autres objets de cette catégorie . Un foncteur est une fonction qui mappe des objets et des morphismes d'une catégorie à des objets et des morphismes dans une autre. C'est du moins ainsi que je le comprends. Ce que cela signifie exactement pour la programmation, je n'ai pas encore compris.
Paul
5
@ norman-ramsey, avez-vous regardé les mathématiques conceptuelles de Lawvere et Schanuel? Je suis un novice total dans la région, mais le livre est éminemment lisible et - j'ose dire - agréable. (J'ai adoré votre explication.)
Ram Rajamony
2
then you have to be able to take that function and product a related function on collectionsVoulez-vous dire produceau lieu de product?
problemofficer
64

Les autres réponses ici sont complètes, mais je vais essayer une autre explication de l'utilisation FP du foncteur . Prenez cela comme analogie:

Un foncteur est un conteneur de type a qui, lorsqu'il est soumis à une fonction qui mappe à partir de ab , donne un conteneur de type b .

Contrairement à l'utilisation du pointeur de fonction abstraite en C ++, ici le foncteur n'est pas la fonction; c'est plutôt quelque chose qui se comporte de manière cohérente lorsqu'il est soumis à une fonction .

seh
la source
3
Un conteneur de type b signifie "le même type de conteneur que le conteneur d'entrée, mais maintenant rempli de b". Donc, si nous avons une liste de bananes et que nous mappons une fonction qui prend une banane et produit une salade de fruits, nous avons maintenant une liste de salades de fruits. De même, si nous avions un arbre de bananes et que nous mappions la même fonction, nous aurions maintenant un arbre de pommes. L' arbre et la liste etc. sont deux foncteurs ici.
Qqwy
3
"Un foncteur est un conteneur de type A qui, lorsqu'il est soumis à une fonction" - c'est en fait l'inverse - la fonction (le morphisme) est soumise à un foncteur, à mapper dans un autre morphisme
Dmitri Zaitsev
38

Il y a trois significations différentes, peu liées!

  • Dans Ocaml, c'est un module paramétré. Voir manuel . Je pense que la meilleure façon de les grogner est par exemple: (écrit rapidement, peut être buggé)

    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);;

Vous pouvez maintenant ajouter rapidement de nombreuses commandes possibles, des façons de former de nouvelles commandes, effectuer une recherche binaire ou linéaire facilement par-dessus. Programmation générique FTW.

  • Dans les langages de programmation fonctionnels comme Haskell, cela signifie certains constructeurs de types (types paramétrés comme des listes, des ensembles) qui peuvent être "mappés". Pour être précis, un foncteur fest équipé de (a -> b) -> (f a -> f b). Cela a ses origines dans la théorie des catégories. L'article Wikipédia auquel vous avez lié est cet usage.

    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

Il s'agit donc d'un type particulier de constructeurs de type, et n'a pas grand-chose à voir avec les foncteurs dans Ocaml!

  • Dans les langages impératifs, c'est un pointeur pour fonctionner.
sdcvvc
la source
La <q> carte </q> dans les 3 dernières lignes de ce commentaire ne devrait-elle pas être <q> fmap </q>?
imz - Ivan Zakharyaschev
1
J'ai toujours lu que les foncteurs sont des conteneurs - mais ce n'est qu'une mauvaise simplification. Votre réponse a finalement fourni le lien manquant: les foncteurs sont une classe de type (contrainte de type) pour les types paramétrés (constructeurs de type). C'est si simple!
16

Dans OCaml, c'est un module paramétré.

Si vous connaissez le C ++, pensez à un foncteur OCaml comme modèle. C ++ n'a que des modèles de classe et les foncteurs fonctionnent à l'échelle du module.

Un exemple de foncteur est Map.Make; module StringMap = Map.Make (String);;construit un module de carte qui fonctionne avec des cartes à chaîne.

Vous ne pouviez pas réaliser quelque chose comme StringMap avec juste du polymorphisme; vous devez faire quelques hypothèses sur les clés. Le module String contient les opérations (comparaison, etc.) sur un type de chaîne totalement ordonné, et le foncteur établira un lien avec les opérations contenues dans le module String. Vous pourriez faire quelque chose de similaire avec la programmation orientée objet, mais vous auriez une surcharge d'indirection de méthode.

Tobu
la source
Je l'ai obtenu sur le site Web ocaml - mais je ne comprends pas ce que serait l'utilisation d'un module paramétré.
Erik Forbes
4
@Kornel Oui, ce que j'ai décrit est un concept OCaml. L'autre concept n'est que «valeur fonctionnelle», ce qui n'a rien de particulier en PF. @Erik J'ai légèrement développé, mais les documents de référence sont lents à charger.
Tobu
13

Vous avez obtenu pas mal de bonnes réponses. Je vais lancer:

Un foncteur, au sens mathématique, est un type particulier de fonction sur une algèbre. C'est une fonction minimale qui mappe une algèbre à une autre algèbre. La "minimalité" est exprimée par les lois des foncteurs.

il y a deux façons de regarder ceci. Par exemple, les listes sont des foncteurs sur certains types. Autrement dit, étant donné une algèbre sur un type 'a', vous pouvez générer une algèbre compatible de listes contenant des choses de type 'a'. (Par exemple: la carte qui prend un élément dans une liste singleton le contenant: f (a) = [a]) Encore une fois, la notion de compatibilité est exprimée par les lois du foncteur.

D'un autre côté, étant donné un foncteur f "sur" un type a, (c'est-à-dire que fa est le résultat de l'application du foncteur f à l'algèbre de type a), et la fonction de g: a -> b, nous pouvons calculer un nouveau foncteur F = (fmap g) qui associe fa à f b. En bref, fmap est la partie de F qui mappe les "parties de foncteur" aux "parties de foncteur", et g est la partie de la fonction qui mappe les "parties d'algèbre" aux "parties d'algèbre". Cela prend une fonction, un foncteur, et une fois terminé, c'est aussi un foncteur.

Il peut sembler que différents langages utilisent différentes notions de foncteurs, mais ce n'est pas le cas. Ils utilisent simplement des foncteurs sur différentes algèbres. OCamls a une algèbre de modules, et les foncteurs sur cette algèbre vous permettent d'attacher de nouvelles déclarations à un module de manière "compatible".

Un foncteur Haskell n'est PAS une classe de type. Il s'agit d'un type de données avec une variable libre qui satisfait la classe de type. Si vous êtes prêt à creuser dans les tripes d'un type de données (sans variables libres), vous pouvez réinterpréter un type de données en tant que foncteur sur une algèbre sous-jacente. Par exemple:

données F = F Int

est isomorphe à la classe des Ints. Ainsi, F, en tant que constructeur de valeurs, est une fonction qui mappe Int à F Int, une algèbre équivalente. C'est un foncteur. D'un autre côté, vous n'obtenez pas fmap gratuitement ici. C'est à cela que sert la correspondance de motifs.

Les foncteurs sont bons pour «attacher» des éléments aux algèbres, d'une manière algébriquement compatible.

user276631
la source
8

La meilleure réponse à cette question se trouve dans "Typeclassopedia" de Brent Yorgey.

Ce numéro de Monad Reader contient une définition précise de ce qu'est un fonctor ainsi que de nombreuses définitions d'autres concepts ainsi qu'un diagramme. (Monoïde, Applicatif, Monade et autre concept sont expliqués et vus en relation avec un foncteur).

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

extrait de Typeclassopedia for Functor: "Une simple intuition est qu'un Functor représente un" conteneur "quelconque, ainsi que la possibilité d'appliquer une fonction uniformément à chaque élément du conteneur"

Mais en réalité, l'ensemble de la classe de typographie est une lecture fortement recommandée qui est étonnamment facile. D'une certaine manière, vous pouvez voir la classe de types qui y est présentée comme un modèle de conception parallèle à l'objet dans le sens où elle vous donne un vocabulaire pour un comportement ou une capacité donnée.

À votre santé

JFT
la source
7

Il y a un assez bon exemple dans le livre O'Reilly OCaml qui se trouve sur le site Web d'Inria (qui, au moment de la rédaction, est malheureusement en baisse). J'ai trouvé un exemple très similaire dans ce livre utilisé par caltech: Introduction à OCaml (lien pdf) . La section pertinente est le chapitre sur les foncteurs (page 139 du livre, page 149 du PDF).

Dans le livre, ils ont un foncteur appelé MakeSet qui crée une structure de données qui se compose d'une liste et fonctionne pour ajouter un élément, déterminer si un élément est dans la liste et trouver l'élément. La fonction de comparaison utilisée pour déterminer s'il est dans / pas dans l'ensemble a été paramétrée (ce qui fait de MakeSet un foncteur au lieu d'un module).

Ils ont également un module qui implémente la fonction de comparaison afin qu'il effectue une comparaison de chaîne insensible à la casse.

En utilisant le foncteur et le module qui implémente la comparaison, ils peuvent créer un nouveau module sur une seule ligne:

module SSet = MakeSet(StringCaseEqual);;

qui crée un module pour une structure de données définie qui utilise des comparaisons insensibles à la casse. Si vous souhaitez créer un ensemble qui utilise des comparaisons sensibles à la casse, il vous suffit d'implémenter un nouveau module de comparaison au lieu d'un nouveau module de structure de données.

Tobu a comparé les foncteurs aux modèles en C ++, ce qui me semble tout à fait approprié.

Niki Yoshiuchi
la source
6

Compte tenu des autres réponses et de ce que je vais publier maintenant, je dirais que c'est un mot plutôt lourdement surchargé, mais de toute façon ...

Pour obtenir un indice sur la signification du mot «foncteur» dans Haskell, demandez à 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

Donc, fondamentalement, un foncteur dans Haskell est quelque chose qui peut être cartographié. Une autre façon de le dire est qu'un foncteur est quelque chose qui peut être considéré comme un conteneur auquel on peut demander d'utiliser une fonction donnée pour transformer la valeur qu'il contient; ainsi, pour les listes, fmapcoïncide avec map, pour Maybe, fmap f (Just x) = Just (f x), fmap f Nothing = Nothingetc.

La sous-catégorie Functor et la section Functors, Applicative Functors and Monoids of Learn You a Haskell for Great Good donnent quelques exemples de l'utilisation de ce concept particulier. (Un résumé: beaucoup d'endroits! :-))

Notez que toute monade peut être traitée comme un foncteur, et en fait, comme le souligne Craig Stuntz, les foncteurs les plus souvent utilisés ont tendance à être des monades ... OTOH, il est parfois pratique de faire d'un type une instance de la classe de types Functor sans se donner la peine d'en faire une Monade. (Par exemple , dans le cas de ZipListde Control.Applicative, mentionnée sur l' une des pages mentionnées ci - dessus .)

Michał Marczyk
la source
5

Voici un article sur les foncteurs d'un POV de programmation , suivi plus spécifiquement de la façon dont ils apparaissent dans les langages de programmation .

L'utilisation pratique d'un foncteur est dans une monade, et vous pouvez trouver de nombreux tutoriels sur les monades si vous recherchez cela.

Craig Stuntz
la source
1
"L'utilisation pratique d'un foncteur est dans une monade" - pas seulement. Toutes les monades sont des foncteurs, mais il existe de nombreuses utilisations pour les foncteurs non monades.
amindfv
1
Je dirais qu'étudier des monades pour utiliser des foncteurs, c'est comme économiser pour un Rolls pour aller acheter de l'épicerie.
Marco Faustinelli
5

Dans un commentaire à la réponse la mieux notée , l'utilisateur Wei Hu demande:

Je comprends à la fois les foncteurs ML et les foncteurs Haskell, mais je n'ai pas la perspicacité de les relier ensemble. Quelle est la relation entre ces deux, dans un sens théorique de catégorie?

Remarque : je ne connais pas ML, veuillez donc pardonner et corriger toute erreur connexe.

Supposons d'abord que nous connaissons tous les définitions de «catégorie» et de «foncteur».

Une réponse compacte serait que les "foncteurs Haskell" sont des (endo-) foncteurs F : Hask -> Hasktandis que les "foncteurs ML" sont des foncteurs G : ML -> ML'.

Ici, Haskest la catégorie formée par les types et fonctions Haskell entre eux, et de la même manière MLet ML'sont des catégories définies par des structures ML.

Remarque : La création d' une catégorie pose certains problèmes techniquesHask , mais il existe des moyens de les contourner.

D'un point de vue théorique de catégorie, cela signifie qu'un Hask-foncteur est une carte Fde types Haskell:

data F a = ...

avec une carte fmapdes fonctions Haskell:

instance Functor F where
    fmap f = ...

ML est à peu près le même, bien qu'il n'y ait aucune fmapabstraction canonique à ma connaissance, alors définissons-en une:

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

Ce sont des fcartes ML-types et des fmapcartes ML-fonctions, donc

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

est un foncteur F: StructA -> StructB.

Ncat
la source
5

"Functor est la cartographie des objets et des morphismes qui préserve la composition et l'identité d'une catégorie."

Permet de définir ce qu'est une catégorie?

C'est un tas d'objets!

Dessinez quelques points (pour l'instant 2 points, l'un est «a», l'autre est «b») à l'intérieur d'un cercle et nommez ce cercle A (Catégorie) pour l'instant.

Que contient la catégorie?

Composition entre les objets et fonction d'identité pour chaque objet.

Nous devons donc cartographier les objets et conserver la composition après avoir appliqué notre Functor.

Imaginons 'A' est notre catégorie qui a des objets ['a', 'b'] et il existe un morphisme a -> b

Maintenant, nous devons définir un foncteur qui peut mapper ces objets et morphismes dans une autre catégorie «B».

Disons que le foncteur s'appelle 'Peut-être'

data Maybe a = Nothing | Just a

Ainsi, la catégorie «B» ressemble à ceci.

Veuillez dessiner un autre cercle mais cette fois avec "Peut-être a" et "Peut-être b" au lieu de "a" et "b".

Tout semble bien et tous les objets sont cartographiés

«a» est devenu «peut-être a» et «b» est devenu «peut-être b».

Mais le problème est que nous devons également cartographier le morphisme de «a» à «b».

Cela signifie que le morphisme a -> b dans 'A' devrait correspondre au morphisme 'Peut-être a' -> 'Peut-être b'

le morphisme de a -> b est appelé f, puis le morphisme de 'Peut-être a' -> 'Peut-être b' est appelé 'fmap f'

Voyons maintenant quelle fonction «f» faisait dans «A» et voyons si nous pouvons la reproduire dans «B»

définition de la fonction de 'f' dans 'A':

f :: a -> b

f prend a et retourne b

définition de la fonction de 'f' dans 'B':

f :: Maybe a -> Maybe b

f prend peut-être a et retourne peut-être b

permet de voir comment utiliser fmap pour mapper la fonction 'f' de 'A' à la fonction 'fmap f' dans 'B'

définition de fmap

fmap :: (a -> b) -> (Maybe a -> Maybe b)
fmap f Nothing = Nothing
fmap f (Just x) = Just(f x)

Alors, qu'est-ce qu'on fait ici?

Nous appliquons la fonction 'f' à 'x' qui est de type 'a'. La correspondance de motifs spéciaux de «Rien» vient de la définition de Functor Maybe.

Nous avons donc cartographié nos objets [a, b] et morphismes [f] de la catégorie 'A' à la catégorie 'B'.

C'est Functor!

entrez la description de l'image ici

Sumanth Kumar Mora
la source
Réponse intéressante. Je souhaite le compléter avec des Monades comme des burritos (réponse amusante à l' Abstraction, à l'intuition et au "sophisme du tutoriel de la monade" ) et sa phrase "Un foncteur F prend chaque type T et le mappe à un nouveau type FT" alias un constructeur de type . Programmation fonctionnelle et théorie des catégories - Catégories et foncteurs étaient également utiles.
Ludovic Kuty
3

Présentation approximative

Dans la programmation fonctionnelle, un foncteur est essentiellement une construction de levage de fonctions unaires ordinaires (c'est-à-dire celles avec un argument) en fonctions entre des variables de nouveaux types. Il est beaucoup plus facile d'écrire et de maintenir des fonctions simples entre des objets simples et d'utiliser des foncteurs pour les soulever, puis d'écrire manuellement des fonctions entre des objets conteneurs complexes. Un autre avantage est d'écrire des fonctions simples une seule fois, puis de les réutiliser via différents foncteurs.

Des exemples de foncteurs incluent les tableaux, les foncteurs "peut-être" et "soit", les futurs (voir par exemple https://github.com/Avaq/Fluture ), et bien d'autres.

Illustration

Considérez la fonction qui construit le nom complet de la personne à partir du prénom et du nom. Nous pourrions le définir comme fullName(firstName, lastName)fonction de deux arguments, ce qui ne conviendrait cependant pas aux foncteurs qui ne traitent que les fonctions d'un seul argument. Pour y remédier, nous collectons tous les arguments dans un seul objet name, qui devient désormais le seul argument de la fonction:

// In JavaScript notation
fullName = name => name.firstName + ' ' + name.lastName

Et maintenant, si nous avons beaucoup de personnes dans un tableau? Au lieu de parcourir manuellement la liste, nous pouvons simplement réutiliser notre fonction fullNamevia la mapméthode fournie pour les tableaux avec une seule ligne de code courte:

fullNameList = nameList => nameList.map(fullName)

et l'utiliser comme

nameList = [
    {firstName: 'Steve', lastName: 'Jobs'},
    {firstName: 'Bill', lastName: 'Gates'}
]

fullNames = fullNameList(nameList) 
// => ['Steve Jobs', 'Bill Gates']

Cela fonctionnera, chaque fois que chaque entrée dans notre nameListest un objet fournissant à la fois firstNameet des lastNamepropriétés. Mais que se passe-t-il si certains objets ne le font pas (ou ne le sont même pas)? Pour éviter les erreurs et rendre le code plus sûr, nous pouvons encapsuler nos objets dans le Maybetype (voir par exemple https://sanctuary.js.org/#maybe-type ):

// function to test name for validity
isValidName = name => 
    (typeof name === 'object') 
    && (typeof name.firstName === 'string')
    && (typeof name.lastName === 'string')

// wrap into the Maybe type
maybeName = name => 
    isValidName(name) ? Just(name) : Nothing()

Just(name)est un conteneur portant uniquement des noms valides et Nothing()est la valeur spéciale utilisée pour tout le reste. Maintenant, au lieu d'interrompre (ou d'oublier) pour vérifier la validité de nos arguments, nous pouvons simplement réutiliser (lever) notre fullNamefonction d' origine avec une autre ligne de code, basée à nouveau sur la mapméthode, cette fois fournie pour le type Maybe:

// Maybe Object -> Maybe String
maybeFullName = maybeName => maybeName.map(fullName)

et l'utiliser comme

justSteve = maybeName(
    {firstName: 'Steve', lastName: 'Jobs'}
) // => Just({firstName: 'Steve', lastName: 'Jobs'})

notSteve = maybeName(
    {lastName: 'SomeJobs'}
) // => Nothing()

steveFN = maybeFullName(justSteve)
// => Just('Steve Jobs')

notSteveFN = maybeFullName(notSteve)
// => Nothing()

Catégorie Théorie

Un foncteur en théorie des catégories est une carte entre deux catégories respectant la composition de leurs morphismes. Dans un langage informatique , la principale catégorie d'intérêt est celle dont les objets sont des types (certains ensembles de valeurs) et dont les morphismes sont des fonctions f:a->bd'un type aà un autre b.

Par exemple, prenez apour être le Stringtype, ble type Number et fla fonction mappant une chaîne dans sa longueur:

// f :: String -> Number
f = str => str.length

Ici a = Stringreprésente l'ensemble de toutes les chaînes et b = Numberl'ensemble de tous les nombres. En ce sens, les deux aet breprésentent des objets dans la catégorie d'ensemble (qui est étroitement liée à la catégorie de types, la différence étant ici inessentielle). Dans la catégorie d'ensemble, les morphismes entre deux ensembles sont précisément toutes les fonctions du premier ensemble au second. Donc, notre fonction de longueur fici est un morphisme de l'ensemble de chaînes dans l'ensemble de nombres.

Comme nous ne considérons que la catégorie d'ensemble, les foncteurs pertinents de celle-ci en elle-même sont des cartes envoyant des objets aux objets et des morphismes aux morphismes, qui satisfont certaines lois algébriques.

Exemple: Array

Arraypeut signifier beaucoup de choses, mais une seule chose est un Functor - la construction de type, mappant un type adans le type [a]de tous les tableaux de type a. Par exemple, le Arrayfoncteur mappe le type String dans le type [String](l'ensemble de tous les tableaux de chaînes de longueur arbitraire) et définit le type Numberdans le type correspondant [Number](l'ensemble de tous les tableaux de nombres).

Il est important de ne pas confondre la carte Functor

Array :: a => [a]

avec un morphisme a -> [a]. Le foncteur mappe simplement (associe) le type aau type [a]comme une chose à une autre. Le fait que chaque type soit en fait un ensemble d'éléments n'a aucune importance ici. En revanche, un morphisme est une fonction réelle entre ces ensembles. Par exemple, il y a un morphisme naturel (fonction)

pure :: a -> [a]
pure = x => [x]

qui envoie une valeur dans le tableau à 1 élément avec cette valeur comme entrée unique. Cette fonction ne fait pas partie du ArrayFunctor! Du point de vue de ce foncteur, purec'est juste une fonction comme les autres, rien de spécial.

D'un autre côté, le ArrayFunctor a sa deuxième partie - la partie morphisme. Qui mappe un morphisme f :: a -> bdans un morphisme [f] :: [a] -> [b]:

// a -> [a]
Array.map(f) = arr => arr.map(f)

Voici arrtout tableau de longueur arbitraire avec des valeurs de type a, et arr.map(f)est le tableau de même longueur avec des valeurs de type b, dont les entrées sont le résultat de l'application faux entrées de arr. Pour en faire un foncteur, les lois mathématiques de mise en correspondance de l'identité à l'identité et des compositions aux compositions doivent tenir, ce qui est facile à vérifier dans cet Arrayexemple.

Dmitri Zaitsev
la source
2

Pour ne pas contredire les réponses théoriques ou mathématiques précédentes, mais un Functor est aussi un objet (dans un langage de programmation orienté objet) qui n'a qu'une seule méthode et est effectivement utilisé comme fonction.

Un exemple est l'interface Runnable en Java, qui n'a qu'une seule méthode: exécuter.

Considérez cet exemple, d'abord en Javascript, qui a des fonctions de première classe:

[1, 2, 5, 10].map(function(x) { return x*x; });

Sortie: [1, 4, 25, 100]

La méthode map prend une fonction et renvoie un nouveau tableau, chaque élément étant le résultat de l'application de cette fonction à la valeur à la même position dans le tableau d'origine.

Pour faire la même chose est Java, en utilisant un Functor, vous devez d'abord définir une interface, dites:

public interface IntMapFunction {
  public int f(int x);
}

Ensuite, si vous ajoutez une classe de collection qui avait une fonction de carte, vous pouvez faire:

myCollection.map(new IntMapFunction() { public int f(int x) { return x * x; } });

Cela utilise une sous-classe en ligne d'IntMapFunction pour créer un Functor, qui est l'équivalent OO de la fonction de l'exemple JavaScript précédent.

L'utilisation de Functors vous permet d'appliquer des techniques fonctionnelles dans un langage OO. Bien sûr, certains langages OO prennent également directement en charge les fonctions, ce n'est donc pas obligatoire.

Référence: http://en.wikipedia.org/wiki/Function_object

Kevin Greer
la source
En fait, "objet de fonction" n'est pas une description correcte d'un foncteur. Par exemple, Arrayest un foncteur, mais Array(value)ne donne que des tableaux à 1 élément.
Dmitri Zaitsev
0

KISS: Un foncteur est un objet qui a une méthode de carte.

Les tableaux en JavaScript implémentent la carte et sont donc des foncteurs. Les promesses, les flux et les arbres implémentent souvent la carte dans des langages fonctionnels, et lorsqu'ils le font, ils sont considérés comme des foncteurs. La méthode map du fonctor prend son propre contenu et transforme chacun d'eux en utilisant le rappel de transformation passé à map, et renvoie un nouveau fonctor, qui contient la structure comme premier foncteur, mais avec les valeurs transformées.

src: https://www.youtube.com/watch?v=DisD9ftUyCk&feature=youtu.be&t=76

soundyogi
la source
1
Avec la note latérale, «objet» doit être pris très largement et signifie simplement «quelque chose». Pour les langages OOP, par exemple, substituez l' objet à la classe . On pourrait dire `` un functor est une classe qui implémente l'interface Functor '' (Bien sûr, cette interface peut ne pas être physiquement là, mais vous pouvez déplacer la logique de la `` carte '' vers cette interface et la partager avec toutes vos classes mappables) - tant que votre système de saisie permet de taper des choses aussi générales, c'est-à-dire).
Qqwy
1
Pour être honnête, je trouve que les classes sont très déroutantes, d'un côté, elles ne sont qu'un modèle pour quelque chose de concret / mais elles peuvent aussi avoir des méthodes (des choses statiques) et peuvent se comporter comme des objets. La classe implémente-t-elle l'interface ou l'instance qu'elle crée?
soundyogi
1
Oui, ils peuvent prêter à confusion. Mais: Les classes implémentent des interfaces (elles «remplissent» les blancs qui ont été données dans les méthodes d'interfaces. En d'autres termes: elles transforment les directives abstraites de l'interface en une directive concrète qui peut être instantanément (pardonnez le jeu de mots) instanciée). En ce qui concerne les «classes se comportent comme des objets»: dans des langages véritablement OOP comme Ruby, les classes sont des instances de la classe «Class». C'est des tortues tout le long.
Qqwy
ArrayLa construction de type définit un seul foncteur. Ses instances sont également appelées «tableaux» mais elles ne sont pas des foncteurs. La description ici devrait être plus précise.
Dmitri Zaitsev
@DmitriZaitsev Pourriez-vous élaborer? Donc, ce que vous dites, c'est que les instances ne sont pas des foncteurs? Je ne vois pas le sens dans la mesure où vous obtenez un nouveau foncteur en mappant sur un.
soundyogi
-4

En pratique, functor signifie un objet qui implémente l'opérateur d'appel en C ++. Dans ocaml, je pense que functor fait référence à quelque chose qui prend un module en entrée et qui en sort un autre.

feng
la source
-6

En termes simples, un foncteur, ou objet de fonction, est un objet de classe qui peut être appelé comme une fonction.

En C ++:

Voici comment vous écrivez une fonction

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

Voici comment vous écrivez un foncteur

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

Vous pouvez maintenant le faire:

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

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

Ce qui les rend si géniaux, c'est que vous pouvez garder l'état dans la classe - imaginez si vous vouliez demander à une fonction combien de fois elle a été appelée. Il n'y a aucun moyen de le faire de manière nette et encapsulée. Avec un objet fonction, c'est comme n'importe quelle autre classe: vous auriez une variable d'instance dans laquelle vous incrémentez operator ()et une méthode pour inspecter cette variable, et tout est propre à votre guise.

Mat
la source
12
Non, ces foncteurs ne sont pas la notion de théorie des types utilisée par les langages FP.
Tobu
1
Je peux en quelque sorte voir comment on pourrait prouver que FunctorClassremplit la première loi de Functor, mais pourriez-vous esquisser une preuve pour la deuxième loi? Je ne le vois pas tout à fait.
Jörg W Mittag
3
Bah, vous avez raison. J'ai essayé de résoudre le "Web a fourni des descriptions extrêmement techniques" et j'ai dépassé, essayant d'éviter, "Dans la famille de langues ML, un foncteur est un module qui prend un ou plusieurs autres modules comme paramètre." Mais cette réponse est, eh bien, mauvaise. Trop simplifié et sous-spécifié. Je suis tenté de le supprimer, mais je laisse le soin aux générations futures de secouer la tête :)
Matt
Je suis content que vous ayez laissé la réponse et les commentaires, car cela aide à cadrer le problème. Je vous remercie! J'ai du mal à ce que la plupart des réponses soient écrites en termes de Haskell ou OCaml, et pour moi, c'est un peu comme expliquer les alligators en termes de crocodiles.
Rob
-10

Functor n'est pas spécifiquement lié à la programmation fonctionnelle. C'est juste un "pointeur" vers une fonction ou une sorte d'objet, qui peut être appelé comme ce serait une fonction.

alemjerus
la source
8
Il existe un concept FP spécifique d'un foncteur (de la théorie des catégories), mais vous avez raison de dire que le même mot est également utilisé pour d'autres choses dans des langages non FP.
Craig Stuntz
Êtes-vous sûr que les pointeurs de fonction sont des foncteurs? Je ne vois pas comment les pointeurs de fonction remplissent les deux lois de foncteur, en particulier la deuxième loi de foncteur (préservation de la composition du morphisme). En avez-vous une preuve? (Juste un croquis.)
Jörg W Mittag