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

• associa a cada objecte $X$ de C un objecte $F(X)$ de D,
• associa a cada morfisme $f\colon X\to Y$ en C un morfisme $F(f)\colon F(X)\to F(Y)$ en D tal que s'hi donen les següents condicions:
  • $F(\mathrm {id} _{X})=\mathrm {id} _{F(X)}\,\!$ per cada objecte $X$ de C,
  • $F(g\circ f)=F(g)\circ F(f)$ per a tot morfisme $f\colon X\to Y\,\!$ i $g\colon Y\to Z$ 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.

{- 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).

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

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

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Functor