Haskell Language
Functor

Wprowadzenie

Uwagi

fmap id == id

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

Typowe przypadki Functor

Może

Maybe to Functor zawierający ewentualnie nieobecną wartość:

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

Maybe instancja Functor stosuje funkcję do wartości zawartej w Just . Jeśli obliczenia wcześniej się nie fmap (więc wartość Maybe jest Nothing ), to nie ma wartości, do której można by zastosować funkcję, więc fmap działa.

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

Możemy sprawdzić prawa funktora dla tego wystąpienia, używając wnioskowania równań. W przypadku prawa tożsamości

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

W przypadku prawa składu

(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

Listy

Instancja list Functor stosuje funkcję do każdej wartości na liście na miejscu.

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

Można to alternatywnie zapisać jako zrozumienie listy: fmap f xs = [fx | x <- xs] .

Ten przykład pokazuje, że fmap generalizuje map . map działa tylko na listach, podczas gdy fmap działa na dowolnym Functor .

Można wykazać, że prawo tożsamości ma charakter indukcyjny:

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

i podobnie prawo składu:

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

Funkcje

Nie każdy Functor wygląda jak pojemnik. Instancja funkcji Functor stosuje funkcję do wartości zwracanej innej funkcji.

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

Zauważ, że ta definicja jest równoważna fmap = (.) . Zatem fmap uogólnia skład funkcji.

Jeszcze raz sprawdzając prawo tożsamości:

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

oraz prawo składu:

(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

Definicja klasy funkcjonału i praw

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

Jednym ze sposobów patrzenia na to jest to, że fmap podnosi funkcję wartości do funkcji wartości w kontekście f .

Prawidłowa instancja Functor powinna spełniać prawa funktora , chociaż nie są one egzekwowane przez kompilator:

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

Istnieje powszechnie używany alias fmap dla fmap nazwie <$> .

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

Zamiana wszystkich elementów Functor na jedną wartość

Moduł Data.Functor zawiera dwa kombinatory, <$ i $> , które ignorują wszystkie wartości zawarte w funktorze, zastępując je jedną stałą wartością.

infixl 4 <$, $>

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

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

void ignoruje zwracaną wartość obliczenia.

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

Funktory wielomianowe

Istnieje przydatny zestaw kombinatorów typów do budowania dużych Functor z mniejszych. Są one pouczające jako przykładowe przykłady Functor , a także są przydatne jako technika programowania ogólnego, ponieważ mogą być użyte do reprezentowania dużej klasy wspólnych funktorów.

Funktor tożsamości

Funktor tożsamości po prostu podsumowuje swój argument. Jest to implementacja na poziomie typowym kombinatora I z rachunku SKI.

newtype I a = I a

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

I można znaleźć pod nazwą Identity , w tym Data.Functor.Identity modułu .

Stały funktor

Stały funktor ignoruje swój drugi argument, zawierający tylko stałą wartość. Jest to analog na poziomie typu const , kombinator K z rachunku SKI.

newtype K c a = K c

Zauważ, że K ca nie zawiera żadnych wartości- a ; K () jest izomorficzny do Proxy . Oznacza to, że K realizacja „s fmap nie robi żadnego odwzorowania w ogóle!

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

K jest inaczej znany jako Const , od Data.Functor.Const .

Pozostałe funktory w tym przykładzie łączą mniejsze funktory w większe.

Produkty Functor

Produkt funktorski bierze parę funktorów i pakuje je. Jest to analogiczne do krotki, z tą różnicą, że podczas gdy (,) :: * -> * -> * działa na types * , (:*:) :: (* -> *) -> (* -> *) -> (* -> *) działa na 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

Ten typ można znaleźć pod nazwą Product w module Data.Functor.Product .

Koprodukty Functor

Podobnie jak :*: jest analogiczny do (,) ,: :+: jest analogiem na 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)

:+: można znaleźć pod nazwą Sum , w module Data.Functor.Sum .

Skład funktora

Na koniec :.: Działa jak poziom typu (.) , Biorąc wyjście jednego funktora i podłączając go do wejścia innego.

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)

Typ Compose można znaleźć w Data.Functor.Compose

Funkcje wielomianowe do programowania ogólnego

I , K :*: , :+: i :.: Można traktować jako zestaw bloków konstrukcyjnych dla pewnej klasy prostych typów danych. Zestaw staje się szczególnie wydajny, gdy połączysz go ze stałymi punktami, ponieważ typy danych zbudowane za pomocą tych kombinacji są automatycznie instancjami Functor . Korzystasz z zestawu, aby zbudować typ szablonu, zaznaczając punkty rekurencyjne za pomocą I , a następnie podłącz go do Fix aby uzyskać typ, który może być używany ze standardowym zoo schematów rekurencyjnych.

To „Kit” podejście do projektowania typów danych jest ideą ogólnych bibliotek programowania, takich jak generics-sop . Chodzi o to, aby napisać operacje ogólne przy użyciu zestawu takiego jak ten przedstawiony powyżej, a następnie użyć klasy typu do konwersji dowolnych typów danych na i z ich ogólnej reprezentacji:

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

Funkcje w teorii kategorii

Functor jest zdefiniowany w teorii kategorii jako mapa zachowująca strukturę („homomorfizm”) między kategoriami. W szczególności (wszystkie) obiekty są mapowane na obiekty, a (wszystkie) strzałki są mapowane na strzałki, dzięki czemu prawa kategorii są zachowane.

Kategoria, w której obiektami są typy Haskella, a morfizmy są funkcjami Haskella, nazywa się Hask . Tak więc funktor od Hask do Hask składałby się z mapowania typów na typy i mapowania z funkcji na funkcje.

Zależność koncepcji teoretycznej tej kategorii od konstruktu programistycznego Haskell Functor jest raczej bezpośrednia. Mapowanie typów na typy ma postać typu f :: * -> * , a mapowanie funkcji na funkcje przyjmuje postać funkcji fmap :: (a -> b) -> (fa -> fb) . Łącząc je w jedną klasę,

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

fmap to operacja, która przyjmuje funkcję (rodzaj morfizmu), :: a -> b i odwzorowuje ją na inną funkcję, :: fa -> fb . Zakłada się (ale należy to do programisty zapewnić), że instancje Functor są rzeczywiście matematycznymi funktorami, zachowując kategoryczną strukturę Hask :

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

fmap przenosi funkcję :: a -> b do podkategorii Hask w sposób, który zachowuje zarówno istnienie dowolnych strzałek tożsamości, jak i asocjatywność kompozycji.

Klasa Functor koduje funktory endo tylko w Hask . Ale w matematyce funktory mogą mapować między dowolnymi kategoriami. Bardziej wierne kodowanie tej koncepcji mogłoby wyglądać następująco:

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)

Standardowa klasa Functor jest szczególnym przypadkiem tej klasy, w której kategoriami źródłową i docelową są Hask . Na przykład,

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

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

Wyprowadzanie Functor

DeriveFunctor języka DeriveFunctor umożliwia GHC automatyczne generowanie instancji 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