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 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
     fmap (f. g)  ==  fmap f. fmap g
-}

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]

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:
           descongrueix :: Congruent -> Int
-}
newtype Congruent = FerCongruent {desCongrueix :: Int} 

mod3 :: Int -> Int
mod3 = (`mod` 3)

instance Eq Congruent where
    x == y = mod3 (desCongrueix x) == mod3 (desCongrueix y)

instance Ord Congruent where
    compare x y = mod3 (desCongrueix x) `compare` mod3 (desCongrueix y)

cjt = [1..5] :: Set Int

v1 = (Set.map desCongrueix . Set.map FerCongruent) cjt
v2 = Set.map (desCongrueix . FerCongruent) cjt

títolProva = "Prova equiv. composició d'aplicacions vs. aplicació de composició"
test1 = TestCase $ assertEqual títolProva v1 v2

main :: IO ()
main = runTestTT test1 >>= print

prova:

$ 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 equiv. composició d'aplicacions vs. aplicació de composició
expected: fromList [3,4,5]
 but got: fromList [1,2,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 Modifica l'enllaç a Wikidata

Referències[modifica]

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