Functor

De Viquipèdia
Salta a la navegació Salta a la cerca

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ó[modifica]

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[modifica]

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[modifica]

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 la 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[modifica]

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é[modifica]

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

Referències[modifica]

  1. Jacobson, 2009, p. 19, def. 1.2.
  2. 2,0 2,1 La classe Functor(anglès)
  3. transformació natural (anglès)