Pregunta ¿Cuál es la historia detrás de un Getter?


Me encontré con Adquiridor definición tener ambos Functor y Contravariant restricción en f.

No es sorprendente que "getter" no pueda hacer mucho con la "parte contenida", pero esta firma parece una Fantasma en un entorno de "van Laarhoven" de (a -> f a) -> s -> f s. Es la restricción implícita "s sabe de a"representado de esta manera en lens?

¿Cómo puedo encontrar el código fuente de algunas instancias concretas de un Getter para que yo pueda ver map y contramap ¿siendo utilizado?


5
2017-08-21 19:20


origen


Respuestas:


La idea de un Getter Es que es una lente de solo lectura. Dado un Getter s a puedes sacar un a fuera de un s, pero no puede poner uno. El tipo se define así:

type Getter s a = forall f. (Contravariant f, Functor f) => (a -> f a) -> s -> f s

Cuando un tipo es a la vez Functor y Contravariant, en realidad no depende de su tipo de argumento:

import Data.Void

change :: (Functor f, Contravariant f) => f a -> f b
change = fmap absurd . contramap absurd

Tal funtor siempre se parecerá mucho a Const b para algunos b.

Entonces una Getter s a Es esencial

type Getter s a = forall b . (a -> b) -> s -> b

pero para que funcione con el resto del ecosistema de lentes, tiene polimorfismo adicional.


8
2017-08-21 19:48



Bueno, un captador es básicamente una función. El isomorfismo es esto:

getter :: (Functor f, Contravariant f) => (s->a) -> (a->f a) -> s->f s
getter f q = contramap f . q . f

Aquí el contramap en efecto, no hará más que obligar a los tipos, porque como dices, combinando Functor y Contravariant equivale a requerir que f x en realidad no contiene un x. Básicamente, garantizar esta es también la única razón por la que Functor la restricción está ahí.


5
2017-08-21 19:46



El tipo

Getter s a = forall f . (Contravariant f, Functor f) => (a -> f a) -> (s -> f s)

es isomorfo al tipo s -> a. Los dos lados del isomorfismo están dados por

toGetter :: (s -> a) -> Getter s a
toGetter h alpha = contramap h . alpha . h
fromGetter :: Getter s a -> (s -> a)
fromGetter getter = getConst . getter Const

No es difícil ver eso fromGetter (toGetter h) igual h.

Hasta este punto (es decir, para implementar toGetter y fromGetter y para demostrar que fromGetter . toGetter = id) no hemos usado el Functor f restricción. Sin embargo, esta restricción es necesaria para probar que toGetter . fromGetter = id.


Primero asume que f es a la vez una covariante Functor y un Contravariant functor Entonces cualquier función g :: x -> y cede funciones fmap g :: f x -> f y y contramap g :: f y -> f x. La parametricidad, combinada con las leyes funcionadoras, implica que estas son mutuamente inversas, es decir f x ≅ f y. Por lo tanto, f Es (hasta el isomorfismo) un funtor constante, por lo que podemos pensar en Getter s a como se define como

Getter s a = forall f0 . (a -> b) -> (s -> b)

(como se menciona en la respuesta de dfeuer). Por el lema Yoneda, esto es isomorfo a s -> a.


Sorprendentemente, si levantamos el Functor f restricción:

OddGetter s a = forall f . Contravariant f => (a -> f a) -> (s -> f s)

entonces obtenemos un subtipo de Getter s a que ya no es isomorfo para s -> a, pero en lugar de s -> Aux a s:

newtype Aux a x = Aux {aAux :: a, gAux :: x -> a}
instance Contravariant (Aux a) where
  contramap f (Aux a g) = Aux a (g . f)

toAux :: a -> Aux a a
toAux a = Aux a id

(Aux a, toAux) es la inicial de todos los pares (F, toF) dónde F es un functor contravariante y toF :: a -> F a, similar a cómo (Const a, Const) es la inicial de todos los pares (F, toF) dónde F Es un funtor co y contravariante y toF :: a -> F a.

Los dos lados del isomorfismo se pueden implementar de la siguiente manera:

toOddGetter :: (s -> Aux a s) -> OddGetter s a
toOddGetter sigma alpha s1 =
    contramap (\s2 -> gAux (sigma s1) s2) $ alpha $ aAux (sigma s1)
fromOddGetter :: OddGetter s a -> (s -> Aux a s)
fromOddGetter getter = getter toAux

Una vez más, es sencillo comprobar que fromOddGetter . toOddGetter = id, que ya demuestra que OddGetter s a es no isomorfo a s -> a. Para probar que fromOddGetter . toOddGetter = id, nuevamente necesitamos un argumento de parametricidad.

La parametricidad implica que, para cualquier transformación natural nu :: forall x . d x -> f x, alguna getter :: OddGetter s a y cualquier alphaD :: a -> d a, tenemos

nu . getter alphaD = getter (nu . alphaD) :: s -> f s

Ahora, instanciamos d con Aux a, alphaD con toAux y nu con factor alpha(para un arbitrario alpha : a -> f a)

factor :: (a -> f a) -> forall x . Aux a x -> f x
factor alpha (Aux a g) = contramap g $ alpha a

que tiene la propiedad de que factor alpha . toAux = alpha. Entonces nosotros tenemos

factor alpha . getter toAux = getter (factor alpha . toAux) = getter alpha :: s -> f s

Ahora cuando aplicamos esto a algunos s1 :: s, encontramos eso getter alpha s1 (el RHS aplicado) es igual

factor alpha (getter toAux s1)
  = contramap (gAux $ getter toAux s1) $ alpha (aAux $ getter toAux s1)
    {-by definition of factor-}
  = contramap (\s2 -> gAux (getter toAux s1) s2) $ alpha $ aAux (getter toAux s1)
    {-by eta-expansion and regrouping-}
  = toOddGetter (getter toAux) alpha s1
    {-by definition of toOddGetter-}
  = toOddGetter (fromOddGetter getter) alpha s1
    {-by definition of fromOddGetter-}

es decir getter = toOddGetter (fromOddGetter getter).


Dados los isomorfismos, es quizás notable que el tipo

OddGetter s a ≅ s -> Aux a s

es un subtipo de

Getter s a ≅ s -> a

La función de "coerción"

\ getter -> getter :: OddGetter s a -> Getter s a

corresponde a la función

\ sigma -> aAux . sigma :: (s -> Aux a s) -> (s -> a)

bajo estos isomorfismos.


1
2017-09-12 10:06