Haskell Language
funktor

Introduktion

Anmärkningar

fmap id == id

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

Vanliga instanser av Functor

Kanske

Maybe är en Functor innehåller ett eventuellt frånvarande värde:

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

Maybe fallet av Functor tillämpar en funktion på ett värde som är inslaget i en Just . Om beräkningen tidigare har misslyckats (så Maybe värdet är Nothing ), finns det inget värde att använda funktionen på, så fmap är ett no-op.

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

Vi kan kontrollera funktorns lagar för det här fallet med hjälp av ekvationella resonemang. För identitetslagen,

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

För kompositionslagen,

(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

listor

Listas instans av Functor tillämpar funktionen för varje värde i listan på plats.

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

Detta kan alternativt skrivas som en fmap f xs = [fx | x <- xs] : fmap f xs = [fx | x <- xs] .

Detta exempel visar att fmap generaliserar map . map fungerar endast på listor, medan fmap fungerar på en godtycklig Functor .

Identitetslagstiftningen kan visas att hålla genom induktion:

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

och på liknande sätt kompositionslagen:

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

funktioner

Inte varje Functor ser ut som en container. Funktioners instans av Functor tillämpar en funktion på returvärdet för en annan funktion.

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

Observera att denna definition motsvarar fmap = (.) . Så fmap generaliserar funktionskomposition.

Kontrollera igen identitetslagen:

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

och kompositionslagen:

(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

Klassdefinition av funktor och lagar

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

Ett sätt att titta på det är att fmap lyfter en funktion av värden till en funktion av värden i ett sammanhang f .

En korrekt instans av Functor bör tillfredsställa funktorlagarna , även om dessa inte verkställs av kompilatorn:

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

Det finns ett vanligt använt infixalias för fmap heter <$> .

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

Ersätt alla element i en Functor med ett enda värde

Data.Functor modulen innehåller två kombinationer, <$ och $> , som ignorerar alla värden i en funktor och ersätter dem alla med ett enda konstant värde.

infixl 4 <$, $>

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

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

void ignorerar en beräknings returvärde.

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

Polynomiska funktorer

Det finns en användbar uppsättning Functor för att bygga stora Functor av mindre. Dessa är lärorika som exempel på Functor , och de är också användbara som en teknik för generisk programmering, eftersom de kan användas för att representera en stor klass av vanliga funktorer.

Identitetsfunktorn

Identitetsfunktorn släpper helt enkelt upp sitt argument. Det är en typnivåimplementering av I kombinatorn från SKI-kalkylen.

newtype I a = I a

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

I kan hittas under namnet Identity i Data.Functor.Identity modulen .

Den ständiga funktorn

Den ständiga funktorn ignorerar sitt andra argument och innehåller endast ett konstant värde. Det är en typnivåanalog av const , K kombinatorn från SKI-kalkylen.

newtype K c a = K c

Notera att K ca inte innehåller några a -värden; K () är isomorf för Proxy . Detta innebär att K : s implementering av fmap inte gör någon kartläggning alls!

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

K är annars känd som Const , från Data.Functor.Const .

De återstående funktorerna i detta exempel kombinerar mindre funktorer till större.

Functor produkter

Funktorprodukten tar ett par funktorer och förpackar dem. Det är analogt med en tupel, förutom att medan (,) :: * -> * -> * fungerar på types * , (:*:) :: (* -> *) -> (* -> *) -> (* -> *) arbetar med 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

Denna typ finns under namnet Product i Data.Functor.Product modulen .

Funktorkoprodukter

Precis som :*: är analog med (,) :+: är funktornivån analog till 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)

:+: kan hittas under namnet Sum i Data.Functor.Sum modulen .

Funktorsammansättning

Slutligen :.: Fungerar som en typnivå (.) , Tar utgången från en funktor och rör den i ingången till en annan.

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)

Compose finns i Data.Functor.Compose

Polynomiska funktorer för generisk programmering

I , K :*: , :+: och :.: Kan betraktas som ett byggsätt för en viss klass enkla datatyper. Satsen blir särskilt kraftfull när du kombinerar den med fasta punkter eftersom datatyper byggda med dessa kombinatorer automatiskt är instanser av Functor . Du använder satsen för att bygga en malltyp, markera rekursiva punkter med hjälp av I och sedan ansluta den till Fix att få en typ som kan användas med standardzoo för rekursionsscheman.

Denna "kit" -metod för att designa datatyper är idén bakom generiska programmeringsbibliotek som generics-sop . Tanken är att skriva generiska operationer med hjälp av ett kit som det som presenterats ovan och sedan använda en typklass för att konvertera godtyckliga datatyper till och från deras generiska representation:

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

Funktorer i kategoriteori

En funktor definieras i kategoriteori som en strukturbevarande karta (en 'homomorfism') mellan kategorierna. Specifikt mappas (alla) objekt till objekt och (alla) pilar mappas till pilar, så att kategorilagarna bevaras.

Den kategori där objekt är Haskell-typer och morfismer är Haskell-funktioner kallas Hask . Så en funktor från Hask till Hask skulle bestå av en kartläggning av typer till typer och en kartläggning från funktioner till funktioner.

Förhållandet som det här kategoriteoretiska konceptet har till Haskell-programmeringskonstruktionen Functor är ganska direkt. Kartläggningen från typer till typer har formen av en typ f :: * -> * , och kartläggningen från funktioner till funktioner har formen av en funktion fmap :: (a -> b) -> (fa -> fb) . Sätta samman dem i en klass,

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

fmap är en operation som tar en funktion (en typ av morfism), :: a -> b , och kartlägger den till en annan funktion, :: fa -> fb . Det antas (men lämnas till programmeraren för att säkerställa) att instanser av Functor verkligen är matematiska funktorer, vilket bevarar Hasks kategoriska struktur:

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

fmap lyfter en funktion :: a -> b in i en underkategori av Hask på ett sätt som bevarar både existensen av alla identitetspilar och kompositionens associativitet.

Functor klassen kodar endast för endo- funktorer på Hask . Men i matematik kan funktorer kartlägga mellan godtyckliga kategorier. En mer trogen kodning av detta koncept skulle se ut så här:

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)

Functor-klassen är ett speciellt fall i denna klass där källkategorin och målkategorierna båda är Hask . Till exempel,

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

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

Härleda Functor

DeriveFunctor språkförlängningen tillåter GHC att generera instanser av Functor automatiskt.

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