Haskell Language
Functor

Introducción

Observaciones

fmap id == id

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

Instancias comunes de Functor

Tal vez

Maybe es un Functor contiene un valor posiblemente ausente:

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

La instancia de Functor de Maybe aplica una función a un valor envuelto en un Just . Si el cálculo ha fallado anteriormente (por lo que el valor Maybe es un Nothing ), entonces no hay ningún valor para aplicar la función, por lo que fmap es un no-op.

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

Podemos verificar las leyes de los funtores para esta instancia usando el razonamiento ecuacional. Por la ley de identidad,

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

Por la ley de composición,

(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

Liza

La instancia de lista de Functor aplica la función a cada valor de la lista en su lugar.

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

Esto también podría escribirse como una lista de comprensión: fmap f xs = [fx | x <- xs] .

Este ejemplo muestra que fmap generaliza el map . map solo funciona en listas, mientras que fmap funciona en un Functor arbitrario.

Se puede demostrar que la ley de identidad se cumple por inducción:

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

y similarmente, la ley de composición:

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

Funciones

No todos los Functor parecen un contenedor. La instancia de Funciones de Functor aplica una función al valor de retorno de otra función.

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

Tenga en cuenta que esta definición es equivalente a fmap = (.) . Así fmap generaliza la composición de funciones.

Una vez más comprobando la ley de identidad:

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

y la ley de composición:

(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

Definición de clase de Functor y Leyes

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

Una forma de verlo es que fmap eleva una función de valores a una función de valores en un contexto f .

Una instancia correcta de Functor debería satisfacer las leyes de los funtores , aunque el compilador no las impone:

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

Hay un alias de infijo de uso fmap para fmap llamado <$> .

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

Reemplazo de todos los elementos de un Functor con un solo valor

El módulo Data.Functor contiene dos combinadores, <$ y $> , que ignoran todos los valores contenidos en un functor, reemplazándolos con un único valor constante.

infixl 4 <$, $>

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

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

void ignora el valor de retorno de un cálculo.

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

Funtores polinomiales

Hay un conjunto útil de combinadores de tipo para construir grandes Functor s a partir de los más pequeños. Estos son instructivos como ejemplos de Functor , y también son útiles como una técnica para la programación genérica, porque se pueden usar para representar una gran clase de functores comunes.

El functor de la identidad.

El functor de la identidad simplemente envuelve su argumento. Es una implementación a nivel de tipo del combinador I del cálculo de SKI.

newtype I a = I a

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

I pueden encontrar, bajo el nombre de Identity , en el módulo Data.Functor.Identity .

El functor constante

El functor constante ignora su segundo argumento, que contiene solo un valor constante. Es un análogo de nivel de tipo de const , el combinador K del cálculo de SKI.

newtype K c a = K c

Tenga en cuenta que K ca no contiene a -valores; K () es isomorfo a Proxy . Esto significa que K implementación de 's fmap no hace ninguna asignación en absoluto!

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

K también se conoce como Const , de Data.Functor.Const .

Los functores restantes en este ejemplo combinan funtores más pequeños en otros más grandes.

Productos funcionales

El producto functor toma un par de functores y los empaca. Es análogo a una tupla, excepto que while (,) :: * -> * -> * opera en types * , (:*:) :: (* -> *) -> (* -> *) -> (* -> *) opera en los 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

Este tipo se puede encontrar, bajo el nombre Product , en el módulo Data.Functor.Product .

Functor coproductos

Al igual que :*: es análogo a (,) :+: es el análogo a nivel de functor de Either de los 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)

:+: se puede encontrar bajo el nombre Sum , en el módulo Data.Functor.Sum .

Composición funcional

Finalmente, :.: Funciona como un nivel de tipo (.) , Tomando la salida de un functor y conectándola a la entrada de otra.

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)

El tipo de Compose se puede encontrar en Data.Functor.Compose

Funtores polinómicos para la programación genérica.

I , K :*: , :+: y :.: Se puede considerar como un kit de bloques de construcción para una cierta clase de tipos de datos simples. El kit se vuelve especialmente poderoso cuando lo combinas con puntos fijos porque los tipos de datos construidos con estos combinadores son automáticamente instancias de Functor . Usted usa el kit para crear un tipo de plantilla, marcando puntos recursivos con I , y luego lo conecta a Fix para obtener un tipo que se puede usar con el zoológico estándar de esquemas de recursión.

Este enfoque de "kit" para diseñar tipos de datos es la idea detrás de las bibliotecas de programación genéricas como generics-sop . La idea es escribir operaciones genéricas usando un kit como el que se presentó anteriormente, y luego usar una clase de tipos para convertir tipos de datos arbitrarios desde y hacia su representación genérica:

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

Functors en la teoría de categorías

Un Functor se define en la teoría de categorías como un mapa que preserva la estructura (un 'homomorfismo') entre categorías. Específicamente, (todos) los objetos se asignan a los objetos, y (todas) las flechas se asignan a las flechas, de manera que se conservan las leyes de la categoría.

La categoría en la que los objetos son tipos de Haskell y los morfismos en funciones de Haskell se denomina Hask . Entonces, un functor de Hask a Hask consistiría en un mapeo de tipos a tipos y un mapeo de funciones a funciones.

La relación que este concepto teórico de la categoría guarda con la estructura de programación de Haskell, Functor es bastante directa. La asignación de tipos a tipos toma la forma de un tipo f :: * -> * , y la asignación de funciones a funciones toma la forma de una función fmap :: (a -> b) -> (fa -> fb) . Poniéndolos juntos en una clase,

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

fmap es una operación que toma una función (un tipo de morfismo), :: a -> b , y la asigna a otra función, :: fa -> fb . Se supone (pero se deja al programador para garantizar) que las instancias de Functor son en realidad functors matemáticos, preservando la estructura categórica de Hask :

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

fmap levanta una función :: a -> b en una subcategoría de Hask de una manera que preserva tanto la existencia de flechas de identidad como la asociatividad de la composición.

La clase Functor solo codifica los functores endo en Hask . Pero en matemáticas, los funtores pueden mapear entre categorías arbitrarias. Una codificación más fiel de este concepto se vería así:

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)

La clase de Functor estándar es un caso especial de esta clase en la que las categorías de origen y destino son Hask . Por ejemplo,

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

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

Functor de derivación

La extensión de lenguaje DeriveFunctor permite a GHC generar instancias de Functor automáticamente.

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