haskell - parametrico - qué es el polimorfismo en la poo

Algebraicamente interpretando el polimorfismo

Question

Entonces entiendo la interpretación algebraica básica de los tipos:

Either a b ~ a + b
(a, b) ~ a * b
a -> b ~ b^a
()   ~ 1
Void ~ 0 -- from Data.Void

... y que estas relaciones son verdaderas para tipos concretos, como Bool , a diferencia de tipos polimórficos como a . También sé cómo traducir las firmas de tipo con tipos polimórficos en sus representaciones de tipo concreto simplemente traduciendo la codificación de la Iglesia de acuerdo con el siguiente isomorfismo:

(forall r . (a -> r) -> r) ~ a

Entonces si tengo:

id :: forall a . a -> a

Sé que no significa id ~ a^a , pero en realidad significa:

id :: forall a . (() -> a) -> a
id ~ ()
   ~ 1

Similar:

pair :: forall r . (a -> b -> r) -> r
pair ~ ((a, b) -> r) - > r
     ~ (a, b)
     ~ a * b

Lo cual me lleva a mi pregunta. ¿Cuál es la interpretación "algebraica" de esta regla?

(forall r . (a -> r) -> r) ~ a

Para cada isomorfismo de tipo concreto, puedo señalar una regla algebraica equivalente, como:

(a, (b, c)) ~ ((a, b), c)
a * (b * c) = (a * b) * c

a -> (b -> c) ~ (a, b) -> c
(c^b)^a = c^(b * a)

Pero no entiendo la igualdad algebraica que es análoga a:

(forall r . (a -> r) -> r) ~ a

Answer 1

(Reescrito para mayor claridad)

Parece que hay dos partes en tu pregunta. Uno está implícito y pregunta cuál es la interpretación algebraica de forall , y el otro pregunta sobre la transformación cont / Yoneda, cuya respuesta de sdcvvc ya se cubrió bastante bien.

Intentaré abordar la interpretación algebraica de forall para ti. Usted menciona que A -> B es B^A pero me gustaría llevar eso un paso más allá y expandirlo a B * B * B * ... * B ( |A| veces). Aunque tenemos exponenciación como una notación para una multiplicación repetida como esa, existe una notación más flexible, ∏ (mayúscula Pi) que representa productos indexados arbitrarios. Hay dos componentes para un Pi: el rango de valores sobre los que queremos multiplicar y la expresión que estamos multiplicando. Por ejemplo, en el nivel de valor, puede expresar la función factorial como un fact i = ∏ [1..i] (λx -> x) .

Volviendo al mundo de los tipos, podemos ver el operador de exponenciación en la correspondencia A -> B ~ B^A como Pi: B^A ~ ∏ A (λ_ -> B) . Esto dice que estamos definiendo un producto A -ary de B s, de modo que las B s no pueden depender de la A particular que hemos elegido. Claro, es equivalente a una exponenciación simple, pero nos permite pasar a casos en los que hay una dependencia.

En el caso más general, obtenemos tipos dependientes, como lo que ve en Agda o Coq: en la sintaxis Agda, replicate : Bool -> ((n : Nat) -> Vec Bool n) es una posible aplicación de un tipo Pi, que podría expresarse más explícitamente como replicate : Bool -> ∏ Nat (Vec Bool) , o más como replicate : ∏ Bool (λ_ -> ∏ Nat (Vec Bool)) .

Tenga en cuenta que, como cabría esperar del álgebra subyacente, puede fusionar ambos ∏ s en la definición de replicate anterior en un único ∏ abarca el producto cartesiano de los dominios: ∏ Bool (/_ -> ∏ Nat (Vec Bool)) es equivalente a ∏ (Bool, Nat) (λ(_, n) -> Vec Bool n) tal como lo sería en el "nivel de valor". Esto es simplemente inestable desde la perspectiva de la teoría de tipos.

Me doy cuenta de que su pregunta era sobre polimorfismo, así que dejaré de hablar sobre tipos dependientes, pero son relevantes: por lo general, en Haskell es más o menos equivalente a un ∏ con un dominio sobre el tipo (tipo) de tipos, * . De hecho, el comportamiento similar a la función del polimorfismo se puede observar directamente en el núcleo de GHC, que los tipifica como capital lambdas (Λ). Como tal, un tipo polimórfico como forall a. a -> a forall a. a -> a es en realidad solo ∏ * (Λ a -> (a -> a)) (usando la notación now ahora que distinguimos entre tipos y valores), que puede expandirse al producto infinito (Bool -> Bool, Int -> Int, () -> (), (Int -> Bool) -> (Int -> Bool), ...) para todos los tipos posibles. La instanciación de la variable de tipo es simplemente proyectar el elemento adecuado del producto * -ary (o aplicar la función de tipo).

Ahora, por la gran pieza que perdí en mi versión original de esta respuesta: parametricidad. La parametricidad puede describirse de diferentes maneras, pero ninguna de las que conozco (ver tipos como relaciones, o (di) naturalidad en la teoría de categorías) realmente tiene una interpretación muy algebraica. Para nuestros propósitos, sin embargo, se reduce a algo bastante simple: no se puede emparejar con patrones en * . Sé que GHC te permite hacer eso al nivel de tipo con familias de tipos, pero solo puedes cubrir un trozo finito de * cuando lo haces, por lo que siempre hay puntos en los que tu familia de tipos no está definida.

Lo que esto significa, desde el punto de vista del polimorfismo, es que cualquier función de tipo F que escribamos en ∏ * F debe ser constante (es decir, ignorar por completo el tipo sobre el que fue polimórfica) o pasar el tipo sin cambios. Por lo tanto, ∏ * (Λ _ -> B) es válido porque ignora su argumento, y corresponde a forall a. B forall a. B El otro caso es algo así como ∏ * (Λ x -> Maybe x) , que corresponde a forall a. Maybe a forall a. Maybe a , que no ignora el argumento tipo, sino que solo "lo pasa". Como tal, un ∏ A que tiene un dominio irrelevante A (como cuando A = * ) puede verse como una intersección más indexada A -ary (seleccionando los elementos comunes en todas las instancias del índice), en lugar de un producto.

Fundamentalmente, en el nivel de valor, las reglas de parametricidad evitan cualquier comportamiento extraño que pueda sugerir que los tipos son más grandes de lo que realmente son. Como no tenemos typecase, no podemos construir un valor de tipo for all forall a. B forall a. B que hace algo diferente en función de a qué se creó a instancia. Por lo tanto, aunque el tipo es técnicamente una función * -> B , siempre es una función constante y, por lo tanto, es equivalente a un único valor de B Usando la interpretación ∏ , es de hecho equivalente a un producto infinito * -ary de B s, pero esos valores B siempre deben ser idénticos, por lo que el producto infinito es efectivamente tan grande como un solo B

Del mismo modo, aunque ∏ * (Λ x -> (x -> x)) (aka, forall a. a -> a ) es técnicamente equivalente a un producto infinito de funciones, ninguna de esas funciones puede inspeccionar el tipo, por lo que todas son restringido para que solo devuelva su valor de entrada y no haga ningún negocio divertido como (+1) : Int -> Int cuando se crea una instancia en Int . Como solo hay una función (asumiendo un lenguaje total) que no puede inspeccionar el tipo de su argumento pero debe devolver un valor del mismo tipo, el producto infinito es, por lo tanto, tan grande como un solo valor.

Ahora, sobre su pregunta directa sobre (forall r . (a -> r) -> r) ~ a . Primero, expresemos su ~ operador más formalmente. Es realmente isomorfismo, por lo que necesitamos dos funciones que vayan y vuelvan, y un argumento de que son inversas.

data Iso a b = Iso 
  { to   :: a -> b
  , from :: b -> a
  -- proof1 :: forall x. to (from x) == x
  -- proof2 :: forall x. from (to x) == x
  }

y ahora expresamos su pregunta original en términos más formales. Su pregunta equivale a construir un término de lo siguiente (impredicativo, por lo que GHC tiene problemas con él, pero vamos a sobrevivir) escriba:

forall a. Iso (forall r. (a -> r) -> r) a

Lo cual, utilizando mi terminología anterior, equivale a ∏ * (Λ a -> Iso (∏ * (Λ r -> ((a -> r) -> r))) a) . Una vez más, tenemos un producto infinito que no puede inspeccionar su argumento tipo. Por handwaving, podemos argumentar que los únicos valores posibles considerando las reglas de parametricidad (las otras dos pruebas se respetan automáticamente) para y from son ($ id) y flip id .

Si esto se siente insatisfactorio, es probable que sea porque la interpretación algebraica de forall realidad no agregó nada a la prueba. En realidad, es simplemente una vieja teoría de tipos, pero espero poder ofrecer algo que se sienta un poco menos categórico que la forma de Yoneda. Sin embargo, vale la pena señalar que en realidad no necesitamos usar parametricidad para escribir proof1 y proof2 arriba. La parametricidad solo entra en escena cuando queremos decir que ($ id) y flip id son nuestras únicas opciones para ay from (que no podemos probar en Agda o Coq, por esa razón).

Answer 2

Algunos enlaces al nLab :

• El cuantificador universal , corresponde al producto dependiente .

• El cuantificador existencial corresponde a la suma dependiente (coproducto dependiente).

Por lo tanto, en los ajustes de la teoría de categorías:

Type               | Modeled¹ as               | In category
-------------------+---------------------------+-------------
Unit               | Terminal object           | CCC
Bottom             | Initial object            |
Record             | Product                   |
Union              | Sum (coproduct)           |
Function           | Exponential               |
-------------------+---------------------------+-------------
Dependent product² | Right adjoint to pullback | LCCC
Dependent sum      | Left adjoint to pullback  |

¹) en la categoría apropiada ─ CCC para subconjunto total y no polimórfico de Haskell ( link ), CPO para rasgos no totales de Haskell ( link ), LCCC para idiomas dependientes.

²) La cuantificación total es un caso especial de producto dependiente:

∀(x :: *). y[x] ~ ∏(x : Set)y[x]

donde Set es el universe de todos los tipos pequeños.

Answer 3

Es una pregunta interesante. No tengo una respuesta completa, pero esto fue demasiado tiempo para un comentario.

La firma de tipo (forall r. (a -> r) -> r) se puede expresar como yo diciendo

Para cualquier tipo r que quieras nombrar, si me das una función que toma a y produce una r , entonces te devolveré una r .

Ahora, esto tiene que funcionar para cualquier tipo r , pero puede ser un tipo específico a . Entonces, la forma en que puedo sacar este truco es tener a sentada en alguna parte, alimentar la función (que produce una r para mí) y luego devolvérsela.

Pero si tengo a sentada, podría dártelo:

Si me das un 1, te daré una a .

que corresponde a la firma de tipo 1 -> a o simplemente a . Por este argumento informal tenemos

(forall r. (a -> r) -> r) ~ a

El siguiente paso sería generar la expresión algebraica correspondiente, pero no tengo claro cómo las cantidades algebraicas interactúan con la cuantificación universal. Es posible que tengamos que esperar a un experto!

Answer 4

Este es el lema famoso de Yoneda para el functor de identidad.

Consulte this publicación para obtener una introducción legible y cualquier libro de texto de teoría de categorías para obtener más información.

En pocas palabras, dado f :: forall r. (a -> r) -> r f :: forall r. (a -> r) -> r puede aplicar f id para obtener una a , y a la inversa, dado x :: a puede tomar ($x) para obtener todo forall r. (a -> r) -> r forall r. (a -> r) -> r .

Estas operaciones son mutuamente inversas. Prueba:

Obviamente ($x) id == x . Voy a mostrar que

($(f id)) == f ,

como las funciones son iguales cuando son iguales en todos los argumentos, tomemos x :: a -> r y demostremos que

($(f id)) x == fx ie

x (f id) == fx .

Como f es polimórfico, funciona como una transformación natural; este es el diagrama de naturalidad para f :

               f_A
     Hom(A, A)  →  A
(x.)      ↓        ↓ x
     Hom(A, R)  →  R
               f_R

Entonces x . f == f . (x.) x . f == f . (x.) x . f == f . (x.) .

Tapar la identidad, (x . f) id == fx . QED

Answer 5

Para (intentar) responder la pregunta real (que es menos interesante que las respuestas a los problemas más generales planteados), la pregunta está mal formada debido a un "error de tipo"

Either ~ (+) 
(,)    ~ (*)
(->) b ~ flip (^)
()   ~ 1
Void ~ 0 

Todos estos tipos de mapas a enteros, y tipos de constructores a funciones en naturales. En cierto sentido, tiene un functor de la categoría de tipos a la categoría de naturales. En la otra dirección, "olvidas" cosas, ya que los tipos conservan la estructura algebraica mientras que los naturales la tiran. Es decir, Either () () puede obtener un natural único, pero dado que es natural, puede obtener muchos tipos.

Pero esto es diferente:

(forall r . (a -> r) -> r) ~ a

¡Mapea un tipo a otro tipo! No es parte del functor anterior. Es solo un isomorfismo dentro de la categoría de tipos. Démosle un símbolo diferente, <=>

Ahora tenemos

(forall r . (a -> r) -> r) <=> a

Ahora nota que no solo podemos enviar tipos a nats y flechas a flechas, sino también algunos isomorfismos a otros isomorfismos:

(a, (b, c)) <=> ((a, b), c) ~ a * (b * c) = (a * b) * c

Pero algo sutil está sucediendo aquí. En cierto sentido, el último isomorfismo en pares es verdadero porque la identidad algebraica es verdadera. Esto quiere decir que el "isomorfismo" en este último simplemente significa que los dos tipos son equivalentes bajo la imagen de nuestro functor a los nats.

El isomorfismo anterior que tenemos que probar directamente, que es donde comenzamos a llegar a la pregunta subyacente, se le da a nuestro functor a los nats, lo que hace forall r. ¿mapa para? Pero la respuesta es esa para todos los forall r. no es un tipo, ni una flecha significativa entre tipos.

Al introducir forall, nos hemos alejado de los tipos de primer orden. No hay ninguna razón para esperar que todo encaje en nuestro Functor anterior, y de hecho, no es así.

De modo que podemos explorar, como otros lo han hecho anteriormente, por qué se sostiene el isomorfismo (que a su vez es muy interesante), pero al hacerlo hemos abandonado el núcleo algebraico de la cuestión. Una pregunta que puede ser respondida, creo, es, dada la categoría de tipos de orden superior y constructores como flechas entre ellos, ¿qué significa Functor para eso?

Editar : Entonces ahora tengo otro enfoque que muestra por qué agregar polimorfismo hace que las cosas se vuelvan locas. Comenzamos haciendo una pregunta más simple: ¿tiene un tipo polimórfico dado cero o más de cero habitantes? Este es el tipo de problema de habitar , y termina siendo, a través de Curry-Howard, un problema en la realizabilidad modificada , ya que es lo mismo que preguntar si una fórmula en alguna lógica es realizable en un modelo computacional apropiado. Ahora, como explica esa página, esto es decidible en el cálculo lambda simplemente tipeado, pero es PSPACE completo. Pero una vez que pasamos a algo más complicado, agregando polimorfismo por ejemplo y yendo al Sistema F, ¡se vuelve indecidible!

Entonces, si no podemos decidir si un tipo arbitrario está habitado en absoluto, ¡es evidente que no podemos decidir cuántos habitantes tiene!