Haskell Language
Functor
Recherche…
Introduction
Functor
est la classe de types f :: * -> *
qui peuvent être mis en correspondance sur covariante. Le mappage d'une fonction sur une structure de données applique la fonction à tous les éléments de la structure sans modifier la structure elle-même.
Remarques
Un foncteur peut être considéré comme un conteneur pour une valeur ou un contexte de calcul. Les exemples sont Maybe a
- Maybe a
ou [a]
. L'article de Typeclassopedia présente un bon résumé des concepts de Functors.
Pour être considéré comme un vrai foncteur, une instance doit respecter les 2 lois suivantes:
Identité
fmap id == id
Composition
fmap (f . g) = (fmap f) . (fmap g)
Instances courantes de Functor
Peut être
Maybe
- Maybe
un Functor
contenant une valeur éventuellement absente:
instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)
Maybe
l'instance de Functor
applique une fonction à une valeur enveloppée dans un Just
. Si le calcul a déjà échoué (donc la valeur Maybe
est un Nothing
), alors il n'y a pas de valeur à appliquer la fonction, donc fmap
est un no-op.
> fmap (+ 3) (Just 3)
Just 6
> fmap length (Just "mousetrap")
Just 9
> fmap sqrt Nothing
Nothing
Nous pouvons vérifier les lois du foncteur pour cette instance en utilisant le raisonnement équationnel. Pour la loi d'identité,
fmap id Nothing
Nothing -- definition of fmap
id Nothing -- definition of id
fmap id (Just x)
Just (id x) -- definition of fmap
Just x -- definition of id
id (Just x) -- definition of id
Pour la loi de composition,
(fmap f . fmap g) Nothing
fmap f (fmap g Nothing) -- definition of (.)
fmap f Nothing -- definition of fmap
Nothing -- definition of fmap
fmap (f . g) Nothing -- because Nothing = fmap f Nothing, for all f
(fmap f . fmap g) (Just x)
fmap f (fmap g (Just x)) -- definition of (.)
fmap f (Just (g x)) -- definition of fmap
Just (f (g x)) -- definition of fmap
Just ((f . g) x) -- definition of (.)
fmap (f . g) (Just x) -- definition of fmap
Des listes
L'instance de Functor
de Functor
de Functor
applique la fonction à toutes les valeurs de la liste en place.
instance Functor [] where
fmap f [] = []
fmap f (x:xs) = f x : fmap f xs
Cela pourrait aussi être écrit comme une compréhension de la liste: fmap f xs = [fx | x <- xs]
.
Cet exemple montre que fmap
généralise la map
. map
opère uniquement sur les listes, alors que fmap
fonctionne sur un Functor
arbitraire.
La loi d'identité peut être démontrée par induction:
-- base case
fmap id []
[] -- definition of fmap
id [] -- definition of id
-- inductive step
fmap id (x:xs)
id x : fmap id xs -- definition of fmap
x : fmap id xs -- definition of id
x : id xs -- by the inductive hypothesis
x : xs -- definition of id
id (x : xs) -- definition of id
et de même, la loi de composition:
-- base case
(fmap f . fmap g) []
fmap f (fmap g []) -- definition of (.)
fmap f [] -- definition of fmap
[] -- definition of fmap
fmap (f . g) [] -- because [] = fmap f [], for all f
-- inductive step
(fmap f . fmap g) (x:xs)
fmap f (fmap g (x:xs)) -- definition of (.)
fmap f (g x : fmap g xs) -- definition of fmap
f (g x) : fmap f (fmap g xs) -- definition of fmap
(f . g) x : fmap f (fmap g xs) -- definition of (.)
(f . g) x : fmap (f . g) xs -- by the inductive hypothesis
fmap (f . g) xs -- definition of fmap
Les fonctions
Tous les Functor
ressemblent pas à un conteneur. Les instances de Functor
des Functor
appliquent une fonction à la valeur de retour d'une autre fonction.
instance Functor ((->) r) where
fmap f g = \x -> f (g x)
Notez que cette définition est équivalente à fmap = (.)
. Donc fmap
généralise la composition des fonctions.
Vérification de la loi d'identité:
fmap id g
\x -> id (g x) -- definition of fmap
\x -> g x -- definition of id
g -- eta-reduction
id g -- definition of id
et la loi de composition:
(fmap f . fmap g) h
fmap f (fmap g h) -- definition of (.)
fmap f (\x -> g (h x)) -- definition of fmap
\y -> f ((\x -> g (h x)) y) -- definition of fmap
\y -> f (g (h y)) -- beta-reduction
\y -> (f . g) (h y) -- definition of (.)
fmap (f . g) h -- definition of fmap
Définition de classe du foncteur et des lois
class Functor f where
fmap :: (a -> b) -> f a -> f b
Une façon de le voir est que fmap
soulève une fonction de valeurs dans une fonction de valeurs dans un contexte f
.
Une instance correcte de Functor
devrait satisfaire aux lois du foncteur , bien que celles-ci ne soient pas appliquées par le compilateur:
fmap id = id -- identity
fmap f . fmap g = fmap (f . g) -- composition
Il existe un alias infix couramment utilisé pour fmap
appelé <$>
.
infixl 4 <$>
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap
Remplacement de tous les éléments d'un foncteur par une valeur unique
Le module Data.Functor
contient deux combinateurs, <$
et $>
, qui ignorent toutes les valeurs contenues dans un foncteur, les remplaçant toutes par une seule valeur constante.
infixl 4 <$, $>
<$ :: Functor f => a -> f b -> f a
(<$) = fmap . const
$> :: Functor f => f a -> b -> f b
($>) = flip (<$)
void
ignore la valeur de retour d'un calcul.
void :: Functor f => f a -> f ()
void = (() <$)
Foncteurs polynomiaux
Il existe un ensemble utile de combinateurs de types pour la construction de gros Functor
parmi les plus petits. Ce sont des exemples instructifs d'exemples de Functor
, et ils sont également utiles en tant que technique de programmation générique, car ils peuvent être utilisés pour représenter une grande classe de foncteurs communs.
Le foncteur d'identité
Le foncteur d'identité encapsule simplement son argument. C'est une implémentation au niveau du combinateur I
du calcul SKI.
newtype I a = I a
instance Functor I where
fmap f (I x) = I (f x)
I
peux être trouvé, sous le nom d' Identity
, dans le module Data.Functor.Identity
.
Le foncteur constant
Le foncteur constant ignore son second argument, ne contenant qu'une valeur constante. C'est un analogue au niveau du type de const
, le combinateur K
du calcul SKI.
newtype K c a = K c
Notez que K ca
ne contient aucune valeur a
; K ()
est isomorphe au Proxy
. Cela signifie que K
mise en œuvre de l » de fmap
ne fait aucun mappage du tout!
instance Functor (K c) where
fmap _ (K c) = K c
K
est également appelé Const
, à partir de Data.Functor.Const
.
Les autres foncteurs dans cet exemple combinent des foncteurs plus petits en plus gros.
Produits Functor
Le foncteur prend une paire de foncteurs et les emballe. C'est analogue à un tuple, sauf que while (,) :: * -> * -> *
opère sur les types
*
, (:*:) :: (* -> *) -> (* -> *) -> (* -> *)
opère sur les functors
* -> *
.
infixl 7 :*:
data (f :*: g) a = f a :*: g a
instance (Functor f, Functor g) => Functor (f :*: g) where
fmap f (fx :*: gy) = fmap f fx :*: fmap f gy
Ce type peut être trouvé, sous le nom de Product
, dans le module Data.Functor.Product
.
Coproduits Functor
Tout comme :*:
est analogue à (,)
:+:
est l'analogue de niveau fonctionnel de Either
.
infixl 6 :+:
data (f :+: g) a = InL (f a) | InR (g a)
instance (Functor f, Functor g) => Functor (f :+: g) where
fmap f (InL fx) = InL (fmap f fx)
fmap f (InR gy) = InR (fmap f gy)
:+:
peut être trouvé sous le nom Sum
, dans le module Data.Functor.Sum
.
Composition de foncteur
Enfin, :.:
Fonctionne comme un type de niveau (.)
, En prenant la sortie d'un foncteur et la plomberie dans l'entrée d'un autre.
infixr 9 :.:
newtype (f :.: g) a = Cmp (f (g a))
instance (Functor f, Functor g) => Functor (f :.: g) where
fmap f (Cmp fgx) = Cmp (fmap (fmap f) fgx)
Le type de Compose
se trouve dans Data.Functor.Compose
Functeurs polynomiaux pour la programmation générique
I
, K
:*:
, :+:
et :.:
Peut être considéré comme un kit de blocs de construction pour une certaine classe de types de données simples. Le kit devient particulièrement puissant lorsque vous le combinez avec des points fixes, car les types de données Functor
avec ces combinateurs sont automatiquement des instances de Functor
. Vous utilisez le kit pour créer un type de modèle, en marquant des points récursifs à l'aide de I
, puis en le Fix
dans Fix
pour obtenir un type pouvant être utilisé avec le zoo standard des schémas de récurrence.
prénom | En tant que type de données | Utiliser le kit de foncteur |
---|---|---|
Paires de valeurs | data Pair a = Pair aa | type Pair = I :*: I |
Deux par deux grilles | type Grid a = Pair (Pair a) | type Grid = Pair :.: Pair |
Nombres naturels | data Nat = Zero | Succ Nat | type Nat = Fix (K () :+: I) |
Des listes | data List a = Nil | Cons a (List a) | type List a = Fix (K () :+: K a :*: I) |
Arbres binaires | data Tree a = Leaf | Node (Tree a) a (Tree a) | type Tree a = Fix (K () :+: I :*: K a :*: I) |
Rosiers | data Rose a = Rose a (List (Rose a)) | type Rose a = Fix (K a :*: List :.: I) |
Cette approche "kit" de la conception des types de données est l'idée derrière les bibliothèques de programmation génériques telles que les generics-sop
. L'idée est d'écrire des opérations génériques en utilisant un kit comme celui présenté ci-dessus, puis d'utiliser une classe de type pour convertir des types de données arbitraires vers et à partir de leur représentation générique:
class Generic a where
type Rep a -- a generic representation built using a kit
to :: a -> Rep a
from :: Rep a -> a
Les foncteurs dans la théorie des catégories
Un foncteur est défini dans la théorie des catégories comme une carte de préservation de la structure (un «homomorphisme») entre les catégories. Plus précisément, tous les objets sont mappés à des objets et toutes les flèches sont associées à des flèches, de sorte que les lois de la catégorie sont préservées.
La catégorie dans laquelle les objets sont des types Haskell et les morphismes sont des fonctions Haskell appelée Hask . Ainsi, un foncteur de Hask à Hask consisterait en un mappage des types en types et en un mappage des fonctions vers les fonctions.
La relation que cette notion théorique de catégorie a avec la construction de programmation de Haskell Functor
est plutôt directe. Le mappage des types aux types prend la forme d'un type f :: * -> *
, et le mappage des fonctions vers les fonctions prend la forme d'une fonction fmap :: (a -> b) -> (fa -> fb)
. Assembler ces éléments dans une classe,
class Functor (f :: * -> *) where
fmap :: (a -> b) -> f a -> f b
fmap
est une opération qui prend une fonction (un type de morphisme), :: a -> b
, et la mappe à une autre fonction, :: fa -> fb
. On suppose (mais c'est au programmeur de s'assurer) que les instances de Functor
sont bien des foncteurs mathématiques, préservant la structure catégorielle de Hask :
fmap (id {- :: a -> a -}) == id {- :: f a -> f a -}
fmap (h . g) == fmap h . fmap g
fmap
lève une fonction :: a -> b
dans une sous-catégorie de Hask d'une manière qui préserve à la fois l'existence de flèches d'identité et l'associativité de la composition.
La classe Functor
ne code que les endo functors sur Hask . Mais en mathématiques, les foncteurs peuvent mapper entre des catégories arbitraires. Un encodage plus fidèle de ce concept ressemblerait à ceci:
class Category c where
id :: c i i
(.) :: c j k -> c i j -> c i k
class (Category c1, Category c2) => CFunctor c1 c2 f where
cfmap :: c1 a b -> c2 (f a) (f b)
La classe standard Functor est un cas particulier de cette classe dans lequel les catégories source et cible sont toutes deux Hask . Par exemple,
instance Category (->) where -- Hask
id = \x -> x
f . g = \x -> f (g x)
instance CFunctor (->) (->) [] where
cfmap = fmap
Functor dérivant
L'extension de langage DeriveFunctor
permet à GHC de générer automatiquement des instances de Functor
.
{-# LANGUAGE DeriveFunctor #-}
data List a = Nil | Cons a (List a) deriving Functor
-- instance Functor List where -- automatically defined
-- fmap f Nil = Nil
-- fmap f (Cons x xs) = Cons (f x) (fmap f xs)
map :: (a -> b) -> List a -> List b
map = fmap