Haskell Language
funtore

introduzione

Osservazioni

fmap id == id

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

Istanze comuni di Functor

Può essere

Maybe è un Functor contiene un valore possibilmente assente:

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

Maybe l'istanza di Functor applica una funzione a un valore racchiuso in un Just . Se il calcolo è già fallito (quindi il valore Maybe è un Nothing ), non c'è alcun valore per applicare la funzione, quindi fmap è un no-op.

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

Possiamo controllare le leggi del functor per questa istanza usando il ragionamento equazionale. Per la legge sull'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

Per la legge sulla composizione,

(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

elenchi

L'istanza di Functor di Functor applica la funzione a ogni valore nell'elenco in posizione.

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

Questo potrebbe in alternativa essere scritto come una comprensione di lista: fmap f xs = [fx | x <- xs] .

Questo esempio mostra che fmap generalizza la map . map funziona solo sugli elenchi, mentre fmap funziona su un Functor arbitrario.

La legge sull'identità può essere mostrata per induzione:

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

e allo stesso modo, la legge sulla composizione:

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

funzioni

Non tutti i Functor aspetto di un contenitore. L'istanza di Functor di Functor applica una funzione al valore di ritorno di un'altra funzione.

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

Si noti che questa definizione è equivalente a fmap = (.) . Quindi fmap generalizza la composizione delle funzioni.

Ancora una volta controllando la legge sull'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

e la legge sulla composizione:

(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

Definizione di classe di Functional and Laws

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

Un modo di vedere le cose è che fmap solleva una funzione di valori in funzione di valori in un contesto f .

Un'istanza corretta di Functor dovrebbe soddisfare le leggi del functor , sebbene queste non siano applicate dal compilatore:

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

C'è un alias infisso comunemente usato per fmap chiamato <$> .

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

Sostituzione di tutti gli elementi di un Functor con un singolo valore

Il modulo Data.Functor contiene due combinatori, <$ e $> , che ignorano tutti i valori contenuti in un functor, sostituendoli tutti con un singolo valore costante.

infixl 4 <$, $>

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

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

void ignora il valore di ritorno di un calcolo.

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

Funtori polinomiali

Esiste un insieme utile di combinatori di tipi per la creazione di grandi Functor da quelli più piccoli. Queste sono istruttive come esempi di Functor , e sono anche utili come tecnica per la programmazione generica, perché possono essere usate per rappresentare una grande classe di funtori comuni.

Il funtore dell'identità

Il functor di identità racchiude semplicemente la sua argomentazione. Si tratta di un'implementazione a livello di codice del combinatore I dal calcolo dello SKI.

newtype I a = I a

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

I Data.Functor.Identity , sotto il nome di Identity , nel modulo Data.Functor.Identity .

Il costante functor

Il functor costante ignora il suo secondo argomento, contenente solo un valore costante. È un analogo di livello tipo di const , il combinatore K del calcolo dello SKI.

newtype K c a = K c

Si noti che K ca non contiene a -Valori; K () è isomorfo a Proxy . Ciò significa che K implementazione s' di fmap non fa alcuna mappatura a tutti!

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

K è altrimenti noto come Const , da Data.Functor.Const .

I rimanenti funtori in questo esempio combinano funtori più piccoli in quelli più grandi.

Prodotti Functor

Il prodotto del functor prende una coppia di funtori e li impacchetta. È analogo a una tupla, tranne che mentre (,) :: * -> * -> * funziona sui types * , (:*:) :: (* -> *) -> (* -> *) -> (* -> *) funziona sui 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

Questo tipo può essere trovato, sotto il nome Product , nel modulo Data.Functor.Product .

Coprodotti di Functor

Proprio come :*: è analogo a (,) ,: :+: è l'analogo a livello di funzione di 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)

:+: può essere trovato sotto il nome Sum , nel modulo Data.Functor.Sum .

Composizione del Functor

Infine, :.: Funziona come un tipo di livello (.) , Prendendo l'output di un funtore e scandendolo nell'input di un altro.

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)

Il tipo di Compose può essere trovato in Data.Functor.Compose

Funtori polinomiali per programmazione generica

I , K :*: , :+: e :.: Può essere pensato come un kit di elementi costitutivi per una determinata classe di tipi di dati semplici. Il kit diventa particolarmente potente quando lo si combina con punti fissi perché i tipi di dati creati con questi combinatori sono automaticamente istanze di Functor . Si utilizza il kit per creare un tipo di modello, contrassegnando i punti ricorsivi usando I , quindi collegandolo a Fix per ottenere un tipo che può essere utilizzato con lo zoo standard degli schemi di ricorsione.

Questo approccio "kit" alla progettazione di tipi di dati è l'idea alla base di generiche librerie di programmazione come generics-sop . L'idea è di scrivere operazioni generiche usando un kit come quello presentato sopra, e quindi usare una classe di tipo per convertire i tipi di dati arbitrari da e verso la loro rappresentazione generica:

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

Funzionari nella teoria delle categorie

Un Functor è definito nella teoria delle categorie come una mappa che preserva la struttura (un "omomorfismo") tra le categorie. Nello specifico, tutti gli oggetti sono mappati agli oggetti e le frecce (tutte) sono mappate alle frecce, in modo tale da preservare le leggi delle categorie.

La categoria in cui gli oggetti sono tipi e morfismi di Haskell sono le funzioni di Haskell è chiamata Hask . Quindi un functor da Hask a Hask consisterebbe in una mappatura di tipi di tipi e una mappatura da funzioni a funzioni.

La relazione che questo concetto teorico di categoria porta al costrutto di programmazione Haskell Functor è piuttosto diretta. La mappatura da tipi a tipi assume la forma di un tipo f :: * -> * e la mappatura da funzioni a funzioni assume la forma di una funzione fmap :: (a -> b) -> (fa -> fb) . Mettendo quelli insieme in una classe,

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

fmap è un'operazione che accetta una funzione (un tipo di morfismo), :: a -> b , e la mappa in un'altra funzione, :: fa -> fb . Si presume (ma è lasciato al programmatore di garantire) che le istanze di Functor siano effettivamente dei funtori matematici, preservando la struttura categorica di Hask :

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

fmap una funzione :: a -> b in una sottocategoria di Hask in un modo che preserva sia l'esistenza di qualsiasi freccia di identità, sia l'associatività della composizione.

La classe Functor codifica solo endo functor su Hask . Ma in matematica, i funtori possono mappare tra categorie arbitrarie. Una codifica più fedele di questo concetto sarebbe simile a questa:

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 di Functor è un caso speciale di questa classe in cui le categorie di origine e di destinazione sono entrambe Hask . Per esempio,

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

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

Funzionante Derivante

L'estensione del linguaggio DeriveFunctor consente a GHC di generare automaticamente istanze di 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