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

Question

Je suis venu à travers le terme de "Foncteur" à quelques reprises lors de la lecture de différents articles sur la programmation fonctionnelle, mais les auteurs supposent généralement que le lecteur comprenne le terme. En regardant autour sur le web a fourni, soit trop de descriptions techniques (voir l' article de Wikipedia) ou incroyablement descriptions vagues (voir la section sur les Foncteurs à ce ocaml tutoriel sur le site web).

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

Edit: Pendant que je m'intéresse à la théorie derrière le terme, je suis moins intéressé par la théorie que je suis dans la mise en œuvre et l'utilisation pratique de ce concept.

Edit 2: Ressemble à il ya quelques croix-terminoligy passe: je suis en se référant expressément aux Foncteurs de la programmation fonctionnelle, et non pas la fonction des objets de C++.

Answer 1

Le mot "foncteur" vient de la catégorie de la théorie, ce qui est très général, très abstrait, branche des mathématiques. Il a été emprunté par les concepteurs de langages fonctionnels dans au moins deux façons différentes.

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

  Comme un exemple de mise en œuvre et de l'utilisation pratique, vous pouvez définir votre préféré forme d'équilibre binaires de recherche arbres une fois pour toutes comme un foncteur, et il prendrait en paramètre un module qui permet de:

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

  • Un total-fonction de commande sur les touches

  Une fois que vous avez fait cela, vous pouvez utiliser le même arbre binaire équilibré mise en œuvre à jamais. (Le type de la valeur stockée dans l'arbre est généralement de gauche polymorphe—l'arbre n'a pas besoin de regarder des valeurs autres que la copie, alors que l'arbre doit absolument être en mesure de comparer les clés, et il obtient la fonction de comparaison à partir du foncteur de paramètre.)

  Une autre application de ML foncteurs est couches de protocoles réseau. Le lien est vraiment un formidable papier par la CMU groupe Fox; il montre comment utiliser les foncteurs de construire plus complexe couches de protocole (comme TCP) sur le type de plus simple, les couches de la propriété intellectuelle, ou même directement sur Ethernet). Chaque couche est mise en œuvre comme un foncteur qui prend comme paramètre le calque de dessous. La structure du logiciel reflète la manière de penser des gens au sujet du problème, par opposition aux couches existant que dans l'esprit du programmeur. En 1994, lors de ce travail a été publié, c'était une grosse affaire.

  Pour un sauvage exemple de ML foncteurs en action, vous pouvez voir l'étude ML Module Mania, qui contient un publiables (c'est à dire, effrayant) exemple de foncteurs au travail. Pour un brillant, clair, pellucide explication de la ML modules du système (avec des comparaisons à d'autres types de modules), lire les premières pages de Xavier Leroy est génial 1994 POPL papier Manifeste Types de Modules et Compilation Séparée.

• En Haskell, et dans certains liées langage purement fonctionnel, Functor est un type de classe. Un type appartient à un type de classe (ou, plus techniquement, le type "est une instance de" le type de la classe) lorsque le type fournit certaines opérations avec certains comportement attendu. Un type T peut appartenir à la classe Functor si il a une certaine collection de comportement de type:

  • Le type T est paramétrée sur un autre type, qui vous devrait penser que le type de l'é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 êtes contenant des entiers, des chaînes, ou des Booléens, respectivement. Si le type d'élément est inconnu, il est écrit comme un paramètre de type a, comme en T a.

    Les exemples incluent des listes (zéro ou plusieurs éléments de type a), l' Maybe type (zéro ou un des éléments de type a), des ensembles d'éléments de type a, les tableaux d'éléments de type a, toutes sortes d'arbres de recherche contenant des valeurs de type a, et beaucoup d'autres personnes que vous pouvez penser.

  • L'autre bien qu' T a à respecter est que si vous avez une fonction de type a -> b (une fonction sur les éléments de), vous devez être en mesure de prendre cette fonction et produit une fonction sur les collections. Vous faites cela avec l'opérateur fmap, ce qui est partagée par chaque type dans l' Functor type de classe. L'opérateur est effectivement surchargé, donc si vous avez une fonction even type Int -> Bool, alors

    fmap even
    

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

    • La conversion d'une liste d'entiers à une liste de Booléens

    • Convertir un arbre d'entiers à un arbre de Booléens

    • Convertir Nothing de Nothing et Just 7 de Just False

    En Haskell, cette propriété est exprimée en donnant le type d' fmap:

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

    nous avons maintenant un petit t, ce qui signifie "n'importe quel type dans l' Functor classe."

  Pour rendre une longue histoire courte, en Haskell un foncteur est une sorte de collection pour laquelle, si vous êtes donné une fonction sur des éléments, fmap va vous redonner une fonction sur les collections. Comme vous pouvez l'imaginer, c'est une idée qui peut être largement réutilisés, ce qui est pourquoi il est béni dans le cadre de Haskell de la bibliothèque standard.

Comme d'habitude, les gens continuent à inventer de nouveaux, utiles abstractions, et vous voudrez peut-être chercher dans applicative de foncteurs, pour qui la meilleure référence peut être un document de Programmation Applicative avec des Effets par Conor McBride et Ross Paterson.

Answer 2

D'autres réponses ici sont complètes, mais je vais essayer une autre explication de l'utilisation de FP du foncteur . Prenons ceci comme analogie: Un foncteur est un conteneur de type a qui, lorsqu'il est soumis à une fonction qui mappe d' un -> b , donne un conteneur de type b .

Contrairement à l'utilisation de abstracted-function-pointer en C ++, ici le foncteur n'est pas la fonction; Au contraire, c'est quelque chose qui se comporte de façon constante lorsqu'il est soumis à une fonction .

Answer 3

Il y a trois significations différentes, pas beaucoup!

• En Ocaml, c'est un paramétrées module. Voir le manuel. Je pense que la meilleure façon de grok, c'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 plusieurs ordres possibles, les moyens de former de nouvelles commandes, faire un binaire ou de la recherche linéaire facilement sur eux. Programmation générique FTW.

• Dans les langages de programmation fonctionnelle comme Haskell, cela signifie que certains types de constructeurs (types paramétrés comme les listes, les ensembles) qui permet de "mapper". Pour être précis, un foncteur f est équipé d' (a -> b) -> (f a -> f b). Cela a des origines dans la catégorie de la théorie. L'article de Wikipédia vous-même liée à cette utilisation.

  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
  

Donc, c'est un genre particulier d'un type de constructeurs, et a peu à voir avec les foncteurs en Ocaml!

• Dans les langages impératifs, il est un pointeur de fonction.

Answer 4

En OCaml, c'est un de paramétrer le module.

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

Un exemple de foncteur est de la Carte.Faire; module StringMap = Map.Make (String);; construit une carte de module qui fonctionne avec de la Ficelle assortie de cartes.

Vous ne pourriez pas obtenir quelque chose comme StringMap avec juste polymorphisme; vous avez besoin de faire quelques hypothèses sur les touches. La Chaîne de module contient les opérations (à titre de comparaison, etc) sur un totalement ordonnée type de chaîne, et le foncteur de lien à l'encontre des opérations de la Chaîne de module contient. Vous pourriez faire quelque chose de similaire avec la programmation orientée objet, mais vous auriez méthode d'indirection de frais généraux.

Answer 5

Vous avez très peu de bonnes réponses. Je vais planter dans:

Un foncteur, dans le sens mathématique, est un type spécial de fonction sur une algèbre. C'est un minimum de la fonction qui associe à une algèbre à l'autre de l'algèbre. "Minimality" est exprimé par le foncteur lois.

Il y a deux façons de regarder cette. Par exemple, les listes sont des foncteurs sur un certain type. C'est, étant donné une algèbre de plus d'un type 'a', vous pouvez générer un compatible algèbre de listes contenant des choses du type "un". (Par exemple: la carte qui prend un élément à une liste singleton contenant: f(a) = [a]) Encore une fois, la notion de compatibilité est exprimé par le foncteur lois.

D'autre part, compte tenu d'un foncteur f "sur" un type a, (qui est, f a est le résultat de l'application du foncteur f de l'algèbre de type a), et la fonction de g: a -> b, on peut calculer une nouvelle foncteur F = (fmap g) qui associe f a et f b. En bref, fmap est la partie de F que les cartes "foncteur parties" à "foncteur pièces", et g est la partie de la fonction que les cartes de "l'algèbre des parties" à "l'algèbre de parties". Elle prend une fonction, un foncteur, et une fois terminé, il EST un foncteur.

Il pourrait sembler que les différentes langues à l'aide de différentes notions de foncteurs, mais ils ne sont pas. Ils sont simplement à l'aide de foncteurs sur différentes algèbres. OCamls a une algèbre de modules et foncteurs de plus que l'algèbre vous permettent d'attacher, de nouvelles déclarations d'un module dans une "compatible".

Un Haskell foncteur n'est PAS un type de classe. C'est un type de données à une variable libre qui satisfait le type de classe. Si vous êtes prêt à creuser dans les entrailles d'un type de données (sans variables libres), vous pouvez réinterpréter un type de données comme un foncteur sur une algèbre sous-jacente. Par exemple:

données F = F Int

est isomorphe a ' la classe d'Entiers. Donc F, en tant que constructeur de valeurs, est une fonction des cartes Int à F Int, un équivalent de l'algèbre. C'est un foncteur. D'autre part, vous n'obtenez pas fmap gratuitement ici. C'est ce que le filtrage est pour.

Les foncteurs sont bonnes pour la "fixation" des choses à des éléments de algèbres, dans un algébriquement compatible.