Functor
A teoria de categories un functor o funtor és una funció d'una categoria a una altra que porta objectes a objectes i morfismes a morfismes de manera que la composició de morfismes i les identitats es preservin.
Els funtors primer es van considerar a topologia algebraica, on s'associen els objectes algebraics amb els espais topològics i s'associen els homomorfismes algebraics amb funcions contínues. Avui dia, els funtors s'utilitzen a través de les matemàtiques modernes per relacionar diverses categories.
Exemples de functors típics són el funtor fidel (un functor injectiu) i el funtor ple (un functor exhaustiu).
En programació possibilita l'equivalència i substitució de la composició de les aplicacions de cadascun dels morfismes, per l'aplicació de la composició dels morfismes, sovint més ràpida perquè converteix la repetició del recorregut de les estructures afectades per cadascun dels morfismes en un sol recorregut, evitant la creació d'estructures intermèdies, optimització coneguda com a Desforestació.
Definició
Siguin C i D categories (les categories descriuen estructures i un Monoide de morfismes composables entre els seus valors). Un functor F de C a D és una correspondència que[1]
- associa a cada objecte de C un objecte de D,
- associa a cada morfisme en C un morfisme en D tal que s'hi donen les següents condicions:
- per cada objecte de C,
- per a tot morfisme i en C.
En llenguatge Haskell
En programació en Haskell un Functor es defineix amb una classe de tipus (estructura algebraica) amb les següents característiques
- la correspondència de valors es concreta en l'estructura algebraica representada per l'índex de la classe
(F:: Tipus -> Tipus)
, on F(x), x∈C, podria instanciar-se en una llista[C]
o bé un context d'efectes laterals amb resultat del tipus C(IO C)
. - la correspondència de morfismes es modela en una funció fmap que associa a una funció
(a -> b)
el resultat(F a -> F b)
que ha de complir els requeriments mencionats més amunt.[2]
{- he posat l'índex F de la classe de tipus en majúscules per coincidir amb l'especificació precedent malgrat que en Haskell ha d'anar en minúscules -} class Functor F where fmap :: (a -> b) -> F a -> F b {- les instàncies de ''functor'' han de complir fmap id == id -- ^ el corresponent de la identitat en la categoria d'origen és la identitat en la categoria destí fmap (f. g) == fmap f. fmap g -- ^ l'aplicació amb `fmap` de la composició dels morfismes -- equival a la composició de les aplicacions individuals -}
Instàncies de Functor són determinats tipus de contenidors, com ara una llista, un vector, però no un conjunt com s'explica més avall, o bé contexts d'efectes com ara IO (efecte global: ent./sortida, vars. globals, excepcions) o també Maybe (efecte semideterminista de les funcions parcials) o bé (Either err) (efecte semideterminista amb indicació de l'error).[2]
Transformació natural entre Functors
Una transformació natural és un homomorfisme entre Functors, que com en tot homomorfisme, manté l'estructura de Functor en transformar el functor origen en el functor destí, preservant l'operació fmap en la imatge de la funció de transformació natural.
Així l'operació fmap en el functor origen seguida de la funció de transf. natural, equival a aplicar fmap en el functor de destí, després d'aplicar la funció de transf. natural, per la definició d'homomorfisme.
Exemple: prenem el functor Maybe com a origen i el functor llista designat '[_]' com a destí i definim maybeToList
i comprovarem si l'operació fmap manté el resultat, abans i després de la funció de transformació.
import Control.Category ((>>>)) -- composició d'esquerre a dreta maybeToList :: Maybe a -> [a] -- funció del Functor Maybe al functor llista [_] maybeToList Nothing = [] maybeToList (Just x) = [x] op1, op2 :: Maybe a -> [b] op1 = fmap f >>> maybeToList -- `fmap` sobre l'origen de la transf. en el Functor Maybe op2 = maybeToList >>> fmap f -- `fmap` sobre la imatge de la transf. en el Functor llista -- `maybeToList` és una transf. natural si `op1 == op2` -- del codi de Data.Maybe instance Functor Maybe where fmap f Nothing = Nothing fmap f (Just x) = Just (f x) -- del codi de Data.List instance Functor [] where fmap f [] = [] fmap f (x : xs) = f x : fmap f xs -- comprovació op1 maybeToList (fmap f Nothing) ≡ maybeToList Nothing ≡ [] maybeToList (fmap f (Just x)) ≡ maybeToList (Just (f x)) ≡ [f x] -- comprovació op2 fmap f (maybeToList Nothing) ≡ fmap f [] ≡ [] fmap f (maybeToList (Just x)) ≡ fmap f [x] ≡ [f x]
Hi ha un gràfic corresponent al wiki de Haskell.org[3]
Això té aplicació en la comprovació de lleis en les instàncies de les classes de tipus del Haskell.
Els conjunts no són Functor
El conjunt no compleix les lleis del Functor. Amb base als Enters definim la congruència mòdul 3.
{-# LANGUAGE PackageImports, OverloadedLists #-} import Data.Set (Set) import qualified Data.Set as Set import "HUnit" Test.HUnit {-| Definim Congruent com un tipus derivat dels Int, amb congruència mòdul 3. El constructor és un morfisme que manté les operacions de les classes que s'esmenten a la clàusula `deriving` i les que ambdós instancien: FerCongruent :: Int -> Congruent L'accessor és el morfisme invers: obtenirEnter :: Congruent -> Int -} newtype Congruent = FerCongruent {obtenirEnter :: Int} -- tipus derivat -- definim la normal d'un valor congruent mòdul 3 normal :: Congruent -> Int normal = (`mod` 3) . obtenirEnter -- aplica el residu mòdul 3 a l'enter original del Congruent instance Eq Congruent where x == y = normal x == normal y instance Ord Congruent where compare x y = normal x `compare` normal y cjt = [1..5] :: Set Int f = obtenirEnter g = FerCongruent -- aplicació de la composició -- conjunt d'enters, doncs `obtenirEnter. FerCongruent == id` v1 = Set.map (f . g) cjt -- composició de les aplicacions -- en aplicar la congruència l'estructura Set manté només els darrers de cada classe v2 = (Set.map f. Set.map g) cjt títolProva = "Prova als conjunts equiv. composició d'aplicacions vs. aplicació de composició" test1 = TestCase $ assertEqual títolProva v1 v2 main :: IO () main = runTestTT test1 >>= print
prova que la regla dels Functor no es compleix als conjunts (l'asserció precedent falla!):
$ stack ghci --package containers --package HUnit Prelude> :load prova2.hs [1 of 1] Compiling Main (prova2.hs, interpreted) Ok, one module loaded. * Main> main ### Failure: prova2.hs:33 Prova als conjunts equiv. composició d'aplicacions vs. aplicació de composició expected: fromList [1,2,3,4,5] but got: fromList [3,4,5] Cases: 1 Tried: 1 Errors: 0 Failures: 1 Counts {cases = 1, tried = 1, errors = 0, failures = 1}
Vegeu també
- Teoria de categories
- Límit d'un functor
Referències
- ↑ Jacobson, 2009, p. 19, def. 1.2.
- ↑ 2,0 2,1 La classe Functor(anglès)
- ↑ transformació natural (anglès)