Haskell Language
Functor

Introduction

Remarques

fmap id == id

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.

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