haskell - ¿Qué es un funtor contravariante?

applicative functor

Question

El tipo sopla mi mente:

class Contravariant (f :: * -> *) where
  contramap :: (a -> b) -> f b -> f a

Luego leí this , pero contrariamente al título, ya no estaba más iluminado.

¿Alguien puede dar una explicación de qué es un funtor contravariante y algunos ejemplos?

Answer 1

Primero, una nota sobre nuestro amigo, la clase Functor.

Puede pensar en Functor f como una afirmación de que nunca aparece en la "posición negativa". Este es un término esotérico para esta idea: observe que en los siguientes tipos de datos parece que la a actúa como una variable de "resultado".

• newtype IO a = IO (World -> (World, a))

• newtype Identity a = Identity a

• newtype List a = List (forall r. r -> (a -> List a -> r) -> r)

En cada uno de estos ejemplos aparece una posición positiva. En cierto sentido, la a para cada tipo representa el "resultado" de una función. Podría ayudar pensar en a segundo ejemplo como () -> a . Y podría ser útil recordar que el tercer ejemplo es equivalente a data List a = Nil | Cons a (List a) data List a = Nil | Cons a (List a) . En las devoluciones de llamada como a -> List -> r la a aparece en la posición negativa, pero la devolución de llamada en sí misma está en la posición negativa, por lo que la negativa y la negativa se multiplican para ser positivas.

Este esquema para firmar los parámetros de una función se elabora en esta maravillosa publicación de blog .

Ahora note que cada uno de estos tipos admite un Functor . ¡Eso no es un error! Los motores están diseñados para modelar la idea de los funtores covariantes categóricos, que "conservan el orden de las flechas", es decir, fa -> fb en lugar de fb -> fa . En Haskell, los tipos en los que nunca aparece en una posición negativa siempre admiten Functor . Decimos que estos tipos son covariantes en a .

Para decirlo de otra manera, uno podría renombrar la clase Functor para que sea Covariant . Son una y la misma idea.

La razón por la que esta idea está redactada de manera tan extraña con la palabra "nunca" es que a puede aparecer tanto en una ubicación positiva como negativa, en cuyo caso decimos que el tipo es invariante en a . a nunca puede aparecer (como un tipo fantasma), en cuyo caso decimos que el tipo es covariante y contravariante en a - bivariante.

Volver a Contravariante

Entonces, para los tipos en los que nunca aparece en la posición positiva, decimos que el tipo es contravariante en a . Cada tipo de Foo a admitirá una instance Contravariant Foo . Aquí hay algunos ejemplos, tomados del paquete contravariant :

• data Void a ( a es fantasma)
• data Unit a = Unit ( a es fantasma de nuevo)
• newtype Const constant a = Const constant
• newtype WriteOnlyStateVariable a = WriteOnlyStateVariable (a -> IO ())
• newtype Predicate a = Predicate (a -> Bool)
• newtype Equivalence a = Equivalence (a -> a -> Bool)

En estos ejemplos, a es bivariante o simplemente contravariante. o bien nunca aparece o es negativo (en estos ejemplos artificiales, siempre aparece antes de una flecha, por lo que determinar esto es muy simple). Como resultado, cada uno de estos tipos admite una instance Contravariant .

Un ejercicio más intuitivo sería entrecerrar los ojos en estos tipos (que exhiben contravarianza) y luego entrecerrar los ojos en los tipos anteriores (que exhiben covarianza) y ver si puede intuir una diferencia en el significado semántico de a . Tal vez eso sea útil, o tal vez todavía sea un juego de manos abstruso.

¿Cuándo podrían ser útiles en la práctica? Por ejemplo, permítanos dividir una lista de cookies por el tipo de chips que tienen. Tenemos un chipEquality :: Chip -> Chip -> Bool . Para obtener una Cookie -> Cookie -> Bool , simplemente evaluamos runEquivalence . contramap cookie2chip . Equivalence $ chipEquality runEquivalence . contramap cookie2chip . Equivalence $ chipEquality runEquivalence . contramap cookie2chip . Equivalence $ chipEquality .

¡Muy verboso! Pero resolver el problema de la verbosidad inducida por newtype tendrá que ser otra pregunta ...

Otros recursos (agrega enlaces aquí a medida que los encuentres)

• 24 Días de Hackage: contravariante.

• Covarianza, contravarianza y posiciones positivas y negativas.

• Me encantan los profunctores

• Charla: Diversión con los Profesores : No puedo exagerar lo genial que es esta charla

Answer 2

Desde el punto de vista de un programador, la esencia de la funcionalidad es poder adaptar las cosas fácilmente. Lo que quiero decir con "adaptación" aquí es que si tengo un fa y necesito un fb , me gustaría un adaptador que se ajuste a mi fa en mi agujero en forma de fb .

Parece intuitivo que si puedo convertir una a en una b , podría ser capaz de convertir una fa en una fb . Y de hecho ese es el patrón que encarna la clase Functor de Haskell; si proporciono una función a -> b , entonces fmap me permite adaptar las cosas a las cosas de fb , sin preocuparme por lo que sea f . ¹

Por supuesto, hablando de tipos paramterizados como lista de x [x] , Maybe y o IO z aquí, y lo que podemos cambiar con nuestros adaptadores es la x , y o z en esos. Si queremos la flexibilidad para obtener un adaptador de cualquier función posible a -> b entonces, por supuesto, lo que estamos adaptando debe ser igualmente aplicable a cualquier tipo posible.

Lo que es menos intuitivo (al principio) es que hay algunos tipos que se pueden adaptar casi exactamente de la misma manera que los funcionales, solo que están "hacia atrás"; para estos, si queremos adaptar un fa para satisfacer una necesidad de un fb , en realidad necesitamos suministrar una b -> a función, no un a -> b uno.

Mi ejemplo concreto favorito es en realidad el tipo de función a -> r (a para argumento, r para resultado); Todas estas tonterías abstractas tienen mucho sentido cuando se aplican a las funciones (y si ha realizado una programación sustancial, es casi seguro que haya usado estos conceptos sin saber la terminología o cuán ampliamente aplicables son), y las dos nociones son tan obvias. duales entre sí en este contexto.

Es bastante sabido que a -> r es un functor en r . Esto tiene sentido; si tengo un a -> r y necesito un a -> s , entonces podría usar una función r -> s para adaptar mi función original simplemente mediante el procesamiento posterior del resultado. ²

Si, por otro lado, tengo una función a -> r y lo que necesito es una b -> r , entonces nuevamente está claro que puedo abordar mi necesidad preprocesando los argumentos antes de pasarlos a la función original. ¿Pero con qué los preprocesé? La función original es una caja negra; no importa lo que haga, siempre está esperando a . Así que necesito convertir mis valores b en los valores a que espera: mi adaptador de preprocesamiento necesita una b -> a función.

Lo que acabamos de ver es que el tipo de función a -> r es un funtor covariante en r , y un funtor contravariante en a . Pienso que esto indica que podemos adaptar el resultado de una función, y el tipo de resultado "cambia con" el adaptador r -> s , mientras que cuando adaptamos el argumento de una función, el tipo de argumento cambia "en la dirección opuesta" al adaptador.

Curiosamente, la implementación de la función-resultado fmap y la función-argumento contramap son casi exactamente lo mismo: ¡simplemente la composición de la función (el operador . )! La única diferencia es en qué lado compones la función del adaptador: ³

fmap :: (r -> s) -> (a -> r) -> (a -> s)
fmap adaptor f = adaptor . f
fmap adaptor = (adaptor .)
fmap = (.)

contramap'' :: (b -> a) -> (a -> r) -> (b -> r)
contramap'' adaptor f = f . adaptor
contramap'' adaptor = (. adaptor)
contramap'' = flip (.)

Considero que la segunda definición de cada bloque es la más perspicaz; (covariante) el mapeo sobre el resultado de una función es la composición de la izquierda (post-composición si queremos tomar una vista de "esto sucede después de eso"), mientras que el mapeo contravariante sobre el argumento de una función es la composición de la derecha (pre- composición).

Esta intuición se generaliza bastante bien; Si una estructura fx nos puede dar valores de tipo x (al igual que una función a -> r nos da valores r , al menos potencialmente), podría ser un Functor covariante en x , y podríamos usar una función x -> y para Adáptalo para que sea un fy . Pero si una estructura fx recibe valores del tipo x de nosotros (de nuevo, como un argumento de la función a a -> r del tipo a ), entonces podría ser un functor Contravariant y necesitaríamos usar una función y -> x para adaptarnos. a ser un fy

Me parece interesante reflejar que "las fuentes son covariantes, los destinos son contravariantes", la intuición se invierte cuando se piensa desde la perspectiva de un implementador de origen / destino en lugar de un llamador. Si estoy tratando de implementar un fx que recibe valores de x , puedo "adaptar mi propia interfaz", por lo que puedo trabajar con los valores de y (mientras sigo presentando la interfaz de los "valores de x " a mis llamadores) usando una x -> y función. Por lo general, no pensamos de esta manera; incluso como implementador del fx , pienso en adaptar las cosas a las que llamo en lugar de "adaptar la interfaz de mi interlocutor a mí". Pero es otra perspectiva que puedes tomar.

El único uso del mundo semi-real que he hecho de Contravariant (en lugar de usar implícitamente la contravarianza de las funciones en sus argumentos utilizando la composición en la derecha, que es muy común) fue para un tipo Serialiser a que podría serializar los valores de x . Serialiser tenía que ser un Contravariant lugar de un Functor ; dado que puedo serializar Foos, también puedo serializar Bars si puedo Bar -> Foo . ⁴ Pero cuando te das cuenta de que Serialiser a es básicamente a -> ByteString se vuelve obvio; Solo estoy repitiendo un caso especial del ejemplo de a -> r .

En la programación funcional pura, no tiene mucho uso tener algo que "recibe valores" sin que también devuelva algo, por lo que todos los funtores contravariantes tienden a parecerse a funciones, pero casi cualquier estructura de datos sencilla que pueda contener valores de un tipo arbitrario ser un functor covariante en ese tipo de parámetro. Esta es la razón por la cual Functor robó el buen nombre temprano y se usa en todo el lugar (bueno, eso y ese Functor fue reconocido como una parte fundamental de Monad , que ya estaba en uso antes de que Functor fuera definido como una clase en Haskell).

En el imperativo OO, creo que los funtores contravariantes pueden ser significativamente más comunes (pero no abstraídos con un marco unificado como Contravariant ), aunque también es muy fácil tener mutabilidad y efectos secundarios, lo que significa que un tipo parametrizado simplemente no podría ser un funtor en absoluto. (comúnmente: su contenedor estándar de a que es tanto legible como escribible es tanto un emisor como un sumidero de a , y en lugar de significar que es covariante y contravariante resulta que significa que no es ninguno).

¹ La instancia de Functor de cada f individual dice cómo aplicar funciones arbitrarias a la forma particular de esa f , sin preocuparse por los tipos particulares a los que se está aplicando f ; una buena separación de preocupaciones.

² Este functor también es una mónada, equivalente a la mónada Reader . No voy a ir más allá de los funtores en detalle aquí, pero dado el resto de mi publicación, una pregunta obvia sería "¿es el tipo a -> r también una especie de mónada contravariante en a entonces?". Desgraciadamente, la contravarianza no se aplica a las mónadas (ver ¿Hay mónadas contravariantes? ), Pero hay un análogo contravariante de Applicative : https://hackage.haskell.org/package/contravariant-1.4/docs/Data-Functor-Contravariant-Divisible.html

³ Tenga en cuenta que mi contramap'' aquí no coincide con el contramap real de Contravariant implementado en Haskell; no puede crear a -> r una instancia real de Contravariant en el código de Haskell simplemente porque a no es el último parámetro de tipo de (->) . Conceptualmente , funciona perfectamente bien, y siempre se puede usar una envoltura de tipo nuevo para intercambiar los parámetros de tipo y hacer que sea una instancia (la contravariante define el tipo Op para exactamente este propósito).

⁴ Al menos para una definición de "serializar" que no necesariamente incluye poder reconstruir la Barra más adelante, ya que serializaría la Barra de forma idéntica a la Foo a la que se asignó, sin manera de incluir ninguna información sobre la asignación. .

Answer 3

En primer lugar, la respuesta de @ haoformayor es excelente, así que considere esto como un apéndice más que una respuesta completa.

Definición

Una forma en que me gusta pensar acerca de Functor (co / contravariant) es en términos de diagramas. La definición se refleja en los siguientes. (Estoy abreviando contramap con cmap )

      covariant                           contravariant
f a ─── fmap φ ───▶ f b             g a ◀─── cmap φ ─── g b
 ▲                   ▲               ▲                   ▲
 │                   │               │                   │
 │                   │               │                   │
 a ────── φ ───────▶ b               a ─────── φ ──────▶ b

Nota: que el único cambio en esas dos definiciones es la flecha en la parte superior (bueno, y los nombres para que pueda referirme a ellos como cosas diferentes).

Ejemplo

El ejemplo que siempre tengo en mente al hablar de esas funciones es, y luego un ejemplo de f sería type F a = forall r. r -> a type F a = forall r. r -> a (lo que significa que el primer argumento es arbitrario pero fijo r ), o en otras palabras, todas las funciones con una entrada común. Como siempre, la instancia para (covariante) Functor es solo fmap ψ φ = ψ. φ`.

Donde el (contravariante) Functor es todas las funciones con un resultado común - type G a = forall r. a -> r type G a = forall r. a -> r aquí la instancia de Contravariant sería cmap ψ φ = φ . ψ cmap ψ φ = φ . ψ .

Pero, ¿qué diablos significa esto?

φ :: a -> b y ψ :: b -> c

por lo tanto, por lo general (ψ . φ) x = ψ (φ x) o x ↦ y = φ x e y ↦ ψ y tiene sentido, lo que se menciona en la declaración de cmap es que aquí

φ :: a -> b pero ψ :: c -> a

así que ψ no puede tomar el resultado de φ pero puede transformar sus argumentos en algo que use puede usar - por lo tanto, x ↦ y = ψ x y y ↦ φ y es la única opción correcta.

Esto se refleja en los siguientes diagramas, pero aquí nos hemos abstraído del ejemplo de funciones con origen / destino común, a algo que tiene la propiedad de ser covariante / contravariante, que es algo que se ve a menudo en matemáticas y / o haskell.

                 covariant
f a ─── fmap φ ───▶ f b ─── fmap ψ ───▶ f c
 ▲                   ▲                   ▲
 │                   │                   │
 │                   │                   │
 a ─────── φ ──────▶ b ─────── ψ ──────▶ c


               contravariant
g a ◀─── cmap φ ─── g b ◀─── cmap ψ ─── g c
 ▲                   ▲                   ▲
 │                   │                   │
 │                   │                   │
 a ─────── φ ──────▶ b ─────── ψ ──────▶ c

Observación:

En matemáticas usualmente se requiere una ley para llamar algo funtor.

        covariant
   a                        f a
  │  ╲                     │    ╲
φ │   ╲ ψ.φ   ══▷   fmap φ │     ╲ fmap (ψ.φ)
  ▼    ◀                   ▼      ◀  
  b ──▶ c                f b ────▶ f c
    ψ                       fmap ψ

       contravariant
   a                        f a
  │  ╲                     ▲    ▶
φ │   ╲ ψ.φ   ══▷   cmap φ │     ╲ cmap (ψ.φ)
  ▼    ◀                   │      ╲  
  b ──▶ c                f b ◀─── f c
    ψ                       cmap ψ

que es equivalente a decir

fmap ψ . fmap φ = fmap (ψ.φ)

mientras

cmap φ . cmap ψ = cmap (ψ.φ)