Haskell Language
functor

Invoering

Opmerkingen

fmap id == id

fmap (f . g) = (fmap f) . (fmap g)

Veel voorkomende voorbeelden van Functor

Kan zijn

Maybe is een Functor die een mogelijk afwezige waarde bevat:

instance Functor Maybe where
    fmap f Nothing = Nothing
    fmap f (Just x) = Just (f x)

Maybe past het exemplaar van Functor een functie toe op een waarde gewikkeld in een Just . Als de berekening eerder is mislukt (dus de waarde Maybe is Nothing ), dan is er geen waarde waarop de functie kan worden toegepast, dus fmap is een no-op.

> fmap (+ 3) (Just 3)
Just 6
> fmap length (Just "mousetrap")
Just 9
> fmap sqrt Nothing
Nothing

We kunnen de functorwetten voor dit geval controleren met behulp van equationeel redeneren. Voor de identiteitswet,

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

Voor de compositiewet,

(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

lijsten

Lists instantie van Functor past de functie toe op elke waarde in de lijst.

instance Functor [] where
    fmap f [] = []
    fmap f (x:xs) = f x : fmap f xs

Dit kan ook worden geschreven als een fmap f xs = [fx | x <- xs] : fmap f xs = [fx | x <- xs] .

Dit voorbeeld laat zien dat fmap map generaliseert. map werkt alleen op lijsten, terwijl fmap op een willekeurige Functor .

De identiteitswet kan worden aangetoond door inductie:

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

en op dezelfde manier: de compositiewet:

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

functies

Niet elke Functor ziet eruit als een container. Functies 'instantie van Functor past een functie toe op de retourwaarde van een andere functie.

instance Functor ((->) r) where
    fmap f g = \x -> f (g x)

Merk op dat deze definitie equivalent is aan fmap = (.) . Dus fmap generaliseert functiesamenstelling.

Nogmaals het controleren van de identiteitswet:

fmap id g
\x -> id (g x)  -- definition of fmap
\x -> g x  -- definition of id
g  -- eta-reduction
id g  -- definition of id

en de compositiewet:

(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

Klasse Definitie van Functor en Wetten

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Een manier om ernaar te kijken is dat fmap een functie van waarden opheft in een functie van waarden in een context f .

Een correct exemplaar van Functor moet voldoen aan de functorwetten , hoewel deze niet worden afgedwongen door de compiler:

fmap id = id                    -- identity
fmap f . fmap g = fmap (f . g)  -- composition

Er is een algemeen gebruikte infix-alias voor fmap naam <$> .

infixl 4 <$>
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap

Alle elementen van een Functor vervangen door een enkele waarde

De Data.Functor module bevat twee combinators, <$ en $> , die alle waarden in een functor negeren en ze allemaal vervangen door een enkele constante waarde.

infixl 4 <$, $>

<$ :: Functor f => a -> f b -> f a
(<$) = fmap . const

$> :: Functor f => f a -> b -> f b
($>) = flip (<$)

void negeert de retourwaarde van een berekening.

void :: Functor f => f a -> f ()
void = (() <$)

Polynomiale functoren

Er is een handige set Functor voor het bouwen van grote Functor uit kleinere. Deze zijn leerzaam als voorbeeldinstanties van Functor en ze zijn ook nuttig als een techniek voor generieke programmering, omdat ze kunnen worden gebruikt om een grote klasse gemeenschappelijke functors te vertegenwoordigen.

De identiteitsfunctor

De identiteitsfunctor sluit eenvoudigweg zijn argumentatie af. Het is een type-niveau implementatie van de I combinator van SKI calculus.

newtype I a = I a

instance Functor I where
    fmap f (I x) = I (f x)

I te vinden onder de naam Identity in de module Data.Functor.Identity .

De constante functor

De constante functor negeert zijn tweede argument, dat alleen een constante waarde bevat. Het is een type-niveau-analoog van const , de K combinator uit SKI calculus.

newtype K c a = K c

Merk op dat K ca geen bevat a -waarden; K () is isomorf voor Proxy . Dit betekent dat K 's implementatie van fmap helemaal geen mapping fmap !

instance Functor (K c) where
    fmap _ (K c) = K c

K is ook bekend als Const , van Data.Functor.Const .

De overige functoren in dit voorbeeld combineren kleinere functoren in grotere.

Functor-producten

Het functorproduct neemt een paar functors en pakt ze in. Het is analoog aan een tuple, behalve dat terwijl (,) :: * -> * -> * werkt op types * , (:*:) :: (* -> *) -> (* -> *) -> (* -> *) werkt op 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

Dit type is te vinden onder de naam Product in de module Data.Functor.Product .

Functor coproducts

Net als :*: is analoog aan (,) ,: :+: is het functieniveau-analoog van 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)

:+: is te vinden onder de naam Sum , in de module Data.Functor.Sum .

Functor samenstelling

Ten slotte :.: Werkt als een type-niveau (.) , Waarbij de uitvoer van de ene functor wordt overgenomen en naar de invoer van een andere wordt geleid.

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)

Het Compose type is te vinden in Data.Functor.Compose

Polynomiale functoren voor generieke programmering

I , K :*: , :+: en :.: Kan worden gezien als een pakket bouwstenen voor een bepaalde klasse eenvoudige gegevenstypen. De kit wordt vooral krachtig wanneer u deze combineert met vaste punten, omdat gegevenstypen die met deze combinators zijn gebouwd, automatisch exemplaren van Functor . U gebruikt de kit om een sjabloontype te bouwen, recursieve punten te markeren met I en vervolgens in Fix te Fix om een type te krijgen dat kan worden gebruikt met de standaard dierentuin van recursieschema's.

Deze "kit" -benadering voor het ontwerpen van gegevenstypen is het idee achter generieke programmeerbibliotheken zoals generics-sop . Het idee is om generieke bewerkingen te schrijven met behulp van een kit zoals hierboven gepresenteerd, en vervolgens een typeklasse te gebruiken om willekeurige gegevenstypen om te zetten naar en van hun generieke weergave:

class Generic a where
    type Rep a  -- a generic representation built using a kit
    to :: a -> Rep a
    from :: Rep a -> a

Functors in Category Theory

Een Functor wordt in de categorietheorie gedefinieerd als een structuurbehoudende kaart (een 'homomorfisme') tussen categorieën. In het bijzonder worden (alle) objecten toegewezen aan objecten, en (alle) pijlen worden toegewezen aan pijlen, zodat de categoriewetten behouden blijven.

De categorie waarin objecten Haskell-typen zijn en morfismen Haskell-functies zijn, wordt Hask genoemd . Een functor van Hask naar Hask zou dus bestaan uit een toewijzing van typen aan typen en een toewijzing van functies aan functies.

De relatie die dit categorietheoretische concept heeft met het Haskell-programmeerconstruct Functor is vrij direct. De toewijzing van typen naar typen neemt de vorm aan van een type f :: * -> * , en de toewijzing van functies aan functies neemt de vorm aan van een functie fmap :: (a -> b) -> (fa -> fb) . Die samenbrengen in een klas,

class Functor (f :: * -> *) where
    fmap :: (a -> b) -> f a -> f b

fmap is een bewerking die een functie (een soort morfisme) gebruikt, :: a -> b , en deze toewijst aan een andere functie, :: fa -> fb . Er wordt aangenomen (maar aan de programmeur overgelaten om ervoor te zorgen) dat instanties van Functor inderdaad wiskundige functors zijn, met behoud van de categorische structuur van Hask :

fmap (id {- :: a -> a -})  ==  id {- :: f a -> f a -}
fmap (h . g)               ==  fmap h . fmap g

fmap tilt een functie :: a -> b in een subcategorie van Hask op een manier die zowel het bestaan van identiteitspijlen als de associativiteit van de compositie behoudt.

De Functor klasse alleen codeert Endo functors op Hask. Maar in de wiskunde kunnen functoren in kaart brengen tussen willekeurige categorieën. Een meer getrouwe codering van dit concept zou er zo uitzien:

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)

De standaard Functor-klasse is een speciaal geval van deze klasse waarin de bron- en doelcategorie Hask zijn . Bijvoorbeeld,

instance Category (->) where        -- Hask
    id    = \x -> x
    f . g = \x -> f (g x)

instance CFunctor (->) (->) [] where
    cfmap = fmap

Afgeleide functor

Met de DeriveFunctor kan GHC automatisch instanties van Functor genereren.

{-# 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