Haskell Language
Functor
Suche…
Einführung
Functor ist die Klasse der Typen f :: * -> * die kovariant übergeordnet werden können. Durch das Mappen einer Funktion über eine Datenstruktur wird die Funktion auf alle Elemente der Struktur angewendet, ohne die Struktur selbst zu ändern.
Bemerkungen
Ein Functor kann als Container für einen bestimmten Wert oder als Berechnungskontext betrachtet werden. Beispiele sind Maybe a oder [a] . Der Artikel über Typeclassopedia enthält eine gute Beschreibung der Konzepte von Functors.
Um ein echter Functor zu sein, muss eine Instanz die zwei folgenden Gesetze beachten:
Identität
fmap id == id
Zusammensetzung
fmap (f . g) = (fmap f) . (fmap g)
Häufige Instanzen von Functor
Könnte sein
Maybe ein Functor einen möglicherweise fehlenden Wert:
instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)
Die Instanz von Functor wendet Maybe eine Funktion auf einen Wert an, der in einem Just Wert enthalten ist. Wenn die Berechnung zuvor fehlgeschlagen ist (also der Maybe Wert ein Nothing ), gibt es keinen Wert, auf den die Funktion fmap kann. fmap ist fmap ein No-Op.
> fmap (+ 3) (Just 3)
Just 6
> fmap length (Just "mousetrap")
Just 9
> fmap sqrt Nothing
Nothing
Wir können die functor-Gesetze für diese Instanz anhand von Gleichungsgrundsätzen überprüfen. Für das Identitätsgesetz
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 das Kompositionsgesetz
(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
Listen
Die Functor -Instanz von Lists wendet die Funktion auf jeden Wert in der vorhandenen Liste an.
instance Functor [] where
fmap f [] = []
fmap f (x:xs) = f x : fmap f xs
Dies könnte alternativ als Listenverständnis geschrieben werden: fmap f xs = [fx | x <- xs] .
Dieses Beispiel zeigt, dass fmap die map verallgemeinert. map nur mit Listen, während fmap mit einem beliebigen Functor funktioniert.
Das Identitätsgesetz kann durch Einführung nachgewiesen werden:
-- 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
und in ähnlicher Weise das Kompositionsgesetz:
-- 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
Funktionen
Nicht jeder Functor sieht aus wie ein Container. Die Funktionsinstanz von Functor wendet eine Funktion auf den Rückgabewert einer anderen Funktion an.
instance Functor ((->) r) where
fmap f g = \x -> f (g x)
Beachten Sie, dass diese Definition fmap = (.) . So verallgemeinert fmap die Funktionszusammenstellung.
Nochmals Überprüfung des Identitätsgesetzes:
fmap id g
\x -> id (g x) -- definition of fmap
\x -> g x -- definition of id
g -- eta-reduction
id g -- definition of id
und das Kompositionsgesetz:
(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
Klassendefinition von Functor und Gesetzen
class Functor f where
fmap :: (a -> b) -> f a -> f b
Eine Sichtweise besteht darin, dass fmap eine Funktion von Werten in eine Funktion von Werten in einem Kontext f hebt .
Eine korrekte Instanz von Functor sollte die Functor-Gesetze erfüllen, obwohl diese vom Compiler nicht erzwungen werden:
fmap id = id -- identity
fmap f . fmap g = fmap (f . g) -- composition
Für fmap gibt es einen häufig verwendeten Infix-Alias namens <$> .
infixl 4 <$>
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap
Ersetzen aller Elemente eines Functors durch einen einzelnen Wert
Das Data.Functor Modul enthält zwei Kombinatoren, <$ und $> , die alle in einem Funktionsbereich enthaltenen Werte ignorieren und alle durch einen einzigen konstanten Wert ersetzen.
infixl 4 <$, $>
<$ :: Functor f => a -> f b -> f a
(<$) = fmap . const
$> :: Functor f => f a -> b -> f b
($>) = flip (<$)
void ignoriert den Rückgabewert einer Berechnung.
void :: Functor f => f a -> f ()
void = (() <$)
Polynomfunktionalitäten
Es gibt eine Reihe nützlicher Kombinatoren, um große Functor aus kleineren zu bauen. Diese Beispiele dienen als Beispielinstanzen für Functor und sind auch als Technik für die generische Programmierung nützlich, da sie dazu verwendet werden können, eine große Klasse von allgemeinen Funktoren darzustellen.
Der Identitätsfunktor
Der Identitätsfunktor fasst sein Argument einfach zusammen. Es ist eine Implementierung auf Typebene des I Kombinators von SKI.
newtype I a = I a
instance Functor I where
fmap f (I x) = I (f x)
I unter dem Namen Identity im Modul Data.Functor.Identity .
Der Konstante functor
Der Konstanten-Funktor ignoriert sein zweites Argument und enthält nur einen konstanten Wert. Es ist ein Typ-Analogon von const , der K Kombinator von SKI.
newtype K c a = K c
Beachten Sie, dass K ca keine a Werte enthält. K () ist zu Proxy isomorph. Dies bedeutet, dass die Implementierung von fmap K überhaupt keine Zuordnung fmap !
instance Functor (K c) where
fmap _ (K c) = K c
K ist ansonsten als Const , von Data.Functor.Const .
Die verbleibenden Funktoren in diesem Beispiel kombinieren kleinere zu größeren.
Functor Produkte
Das functor-Produkt nimmt ein Paar Funkeln und packt sie zusammen. Es ist analog zu einem Tupel, außer dass while (,) :: * -> * -> * auf types * , (:*:) :: (* -> *) -> (* -> *) -> (* -> *) arbeitet mit 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
Dieser Typ befindet sich unter dem Namen Product im Modul Data.Functor.Product .
Functor-Koprodukte
Genau wie :*: ist analog zu (,) ,: :+: ist das Analog der Funktionsebene von 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)
:+: ist unter dem Namen Sum im Modul Data.Functor.Sum .
Functor Zusammensetzung
Schließlich :.: wie eine Typebene (.) , Wobei die Ausgabe eines Funktionsbausteins in die Eingabe einer anderen Funktion eingefügt wird.
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)
Der Compose Typ befindet sich in Data.Functor.Compose
Polynomfunktionen für die generische Programmierung
I , K :*: , :+: und :.: Kann als Satz von Bausteinen für eine bestimmte Klasse einfacher Datentypen betrachtet werden. Das Kit wird besonders leistungsfähig, wenn Sie es mit festen Punkten kombinieren, da mit diesen Kombinatoren erstellte Datentypen automatisch Instanzen von Functor . Sie verwenden das Kit, um einen Vorlagentyp zu erstellen, rekursive Punkte mit I markieren, und dann in Fix , um einen Typ zu erhalten, der mit dem Standardzoo von Rekursionsschemata verwendet werden kann.
| Name | Als Datentyp | Verwendung des Functor-Kits |
|---|---|---|
| Paare von Werten | data Pair a = Pair aa | type Pair = I :*: I |
| Zwei mal zwei Gitter | type Grid a = Pair (Pair a) | type Grid = Pair :.: Pair |
| Natürliche Zahlen | data Nat = Zero | Succ Nat | type Nat = Fix (K () :+: I) |
| Listen | data List a = Nil | Cons a (List a) | type List a = Fix (K () :+: K a :*: I) |
| Binäre Bäume | data Tree a = Leaf | Node (Tree a) a (Tree a) | type Tree a = Fix (K () :+: I :*: K a :*: I) |
| Rosenbäume | data Rose a = Rose a (List (Rose a)) | type Rose a = Fix (K a :*: List :.: I) |
Dieser "Kit" -Ansatz zum Entwerfen von Datentypen ist die Idee hinter generischen Programmierbibliotheken wie generics-sop . Die Idee ist, generische Operationen mit einem Kit wie dem oben dargestellten zu schreiben und dann eine Typklasse zu verwenden, um beliebige Datentypen in und aus ihrer generischen Darstellung zu konvertieren:
class Generic a where
type Rep a -- a generic representation built using a kit
to :: a -> Rep a
from :: Rep a -> a
Functors in der Kategorie Theorie
Ein Functor wird in der Kategorientheorie als eine strukturerhaltende Karte (ein "Homomorphismus") zwischen Kategorien definiert. Insbesondere werden (alle) Objekte Objekten zugeordnet, und (alle) Pfeile werden Pfeilen zugeordnet, so dass die Kategoriengesetze erhalten bleiben.
Die Kategorie, in der Objekte Haskell-Typen sind und Morphismen sind Haskell-Funktionen, wird Hask genannt . Ein Funktor von Hask nach Hask würde also aus einer Zuordnung von Typen zu Typen und einer Zuordnung von Funktionen zu Funktionen bestehen.
Die Beziehung, die dieses kategorientheoretische Konzept mit dem Haskell-Programmierkonstrukt Functor ist eher direkt. Das Mapping von Typen zu Typen hat die Form eines Typs f :: * -> * , und das Mapping von Funktionen zu Funktionen hat die Form einer Funktion fmap :: (a -> b) -> (fa -> fb) . Diese zusammen in eine Klasse setzen,
class Functor (f :: * -> *) where
fmap :: (a -> b) -> f a -> f b
fmap ist eine Operation, die eine Funktion (eine Art Morphismus), :: a -> b , übernimmt und diese einer anderen Funktion, :: fa -> fb . Es wird davon ausgegangen (aber dem Programmierer überlassen), dass die Instanzen von Functor in der Tat mathematische Funktoren sind, die die kategoriale Struktur von Hask bewahren:
fmap (id {- :: a -> a -}) == id {- :: f a -> f a -}
fmap (h . g) == fmap h . fmap g
fmap hebt eine Funktion :: a -> b in eine Unterkategorie von Hask , dass sowohl die Existenz von Identitätspfeilen als auch die Assoziativität der Komposition erhalten bleibt.
Die Functor Klasse codiert nur Endo-Funktionen auf Hask . In der Mathematik können Funktoren jedoch zwischen beliebigen Kategorien kartieren. Eine getreuere Kodierung dieses Konzepts würde folgendermaßen aussehen:
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)
Die Standard-Functor-Klasse ist ein Spezialfall dieser Klasse, in dem die Quell- und Zielkategorien beide Hask sind . Zum Beispiel,
instance Category (->) where -- Hask
id = \x -> x
f . g = \x -> f (g x)
instance CFunctor (->) (->) [] where
cfmap = fmap
Functor ableiten
Mit der DeriveFunctor kann GHC Instanzen von Functor automatisch generieren.
{-# 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