¿Qué hace la palabra clave `forall` en Haskell / GHC?

https://stackoverflow.com/questions/3071136

28-09-2019
|

Pregunta

Me estoy empezando a entender cómo se utiliza la palabra clave forall en los llamados "tipos existenciales" como esto:

data ShowBox = forall s. Show s => SB s

Esto es sólo un subconjunto, sin embargo, de cómo se utiliza forall y yo simplemente no puede envolver la cabeza en torno a su uso en cosas como esta:

runST :: forall a. (forall s. ST s a) -> a

o explicar por qué son diferentes:

foo :: (forall a. a -> a) -> (Char, Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))

O toda la materia RankNTypes ...

Me tienden a preferir clara, libre de jerga Inglés en lugar de los tipos de lenguaje que son normales en ambientes académicos. La mayor parte de las explicaciones que intentan leer sobre esto (los que me pueden encontrar a través de motores de búsqueda) tienen estos problemas:

Son incompletos. En ellas se explica una parte de la utilización de esta palabra clave (como "tipos existenciales") que me hace sentir feliz hasta que leí el código que utiliza de una manera completamente diferente (como runST, foo y bar anterior).
Están densamente cargado de supuestos que he leído lo último en lo que sea rama de la matemática discreta, teoría de la categoría o el álgebra abstracta es muy popular esta semana. (Si no leí las palabras "consultar el documento de lo para más detalles de la implementación" de nuevo, será demasiado pronto.)
Están escritos en formas que suelen acudir los conceptos más simples en tortuosamente torcido y la gramática y la semántica fracturado.

Así que ...

En la pregunta real. ¿Alguien puede explicar por completo la palabra clave forall en claro y sencillo Inglés (o, si existe en algún lugar, seleccione una explicación tan clara, que he echado de menos) que no asume que soy un matemático sumida en la jerga?

Editado para añadir:

Hubo dos respuestas stand-out de los de mayor calidad por debajo, pero por desgracia sólo pueden elegir uno de la mejor. de Norman respuesta fue detallado y útil , explicar las cosas de una manera que mostraba algunos de los fundamentos teóricos de forall y, al mismo tiempo que me muestra algunas de las implicaciones prácticas de la misma. respuesta de yairchu cubrió un área que nadie más mencionado (variables de tipo con ámbito) e ilustrado todos los conceptos con código y una sesión GHCi. Si fuera posible seleccionar tanto lo mejor, lo haría. Por desgracia no puedo y, después de ver las dos respuestas de cerca, he decidido que yairchu Ha bordes ligeramente fuera de Norman debido al código ilustrativo y explicación adjunta. Esto es un poco injusto, sin embargo, porque realmente necesitaba las dos respuestas para entender esto hasta el punto de que forall no me deja con una leve sensación de miedo cuando lo vea en una declaración de tipo.

Solución

Empecemos con un ejemplo de código:

foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b
foob postProcess onNothin onJust mval =
    postProcess val
    where
        val :: b
        val = maybe onNothin onJust mval

Este código no se compila (error de sintaxis) en la llanura Haskell 98. Se requiere una extensión para apoyar la palabra clave forall.

Básicamente, hay 3 diferentes usos comunes de la palabra clave forall (o al menos por lo que Parece ), y cada uno tiene su propia extensión Haskell: ScopedTypeVariables, RankNTypes / Rank2Types, ExistentialQuantification.

El código anterior no conseguir un error de sintaxis con cualquiera de los habilitados, pero único tipo comprobaciones con ScopedTypeVariables habilitado.

Variables Scoped Tipo:

Las variables de tipo Scoped ayuda a uno para especificar los tipos de cláusulas where código dentro. Esto hace que la b en val :: b el mismo que el b en foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b.

Un punto de confundir : es posible que escuche que cuando se omite el forall de un tipo que es en realidad todavía existe implícitamente. ( de la respuesta de Norman: "normalmente idiomas omiten la forall de tipos polimórficos "). Esta afirmación es correcta, pero se refiere a los otros usos de forall, y no al uso ScopedTypeVariables.

Rank-N-Tipos:

Empecemos con que mayb :: b -> (a -> b) -> Maybe a -> b es equivalente a mayb :: forall a b. b -> (a -> b) -> Maybe a -> b, excepto para cuando ScopedTypeVariables está habilitada.

Esto significa que funciona para cada a y b.

digamos Vamos que quieren hacer algo como esto.

ghci> let putInList x = [x]
ghci> liftTup putInList (5, "Blah")
([5], ["Blah"])

¿Cuál debe ser el tipo de este liftTup? Es liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b). Para ver por qué, vamos a tratar de código que:

ghci> let liftTup liftFunc (a, b) = (liftFunc a, liftFunc b)
ghci> liftTup (\x -> [x]) (5, "Hello")
    No instance for (Num [Char])
    ...
ghci> -- huh?
ghci> :t liftTup
liftTup :: (t -> t1) -> (t, t) -> (t1, t1)

"Hmm .. ¿por qué GHC inferir que la tupla debe contener dos del mismo tipo? Vamos a decir que no tienen que ser"

-- test.hs
liftTup :: (x -> f x) -> (a, b) -> (f a, f b)
liftTup liftFunc (t, v) = (liftFunc t, liftFunc v)

ghci> :l test.hs
    Couldnt match expected type 'x' against inferred type 'b'
    ...

Hmm. así que aquí GHC no apliquemos liftFunc en v porque v :: b y liftFunc quiere una x. Realmente queremos que nuestra función para obtener una función que acepta cualquier x posible!

{-# LANGUAGE RankNTypes #-}
liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b)
liftTup liftFunc (t, v) = (liftFunc t, liftFunc v)

Así que no es liftTup que funcione para todos x, que es la función que se hace que lo hace.

existencial Cuantificación:

El uso Vamos a un ejemplo:

-- test.hs
{-# LANGUAGE ExistentialQuantification #-}
data EQList = forall a. EQList [a]
eqListLen :: EQList -> Int
eqListLen (EQList x) = length x

ghci> :l test.hs
ghci> eqListLen $ EQList ["Hello", "World"]
2

¿Cómo es tan diferente de Rank-N-Type?

ghci> :set -XRankNTypes
ghci> length (["Hello", "World"] :: forall a. [a])
    Couldnt match expected type 'a' against inferred type '[Char]'
    ...

Con Rank-N-Tipos, forall a significaba que su expresión debe adaptarse a todas las posibles as. Por ejemplo:

ghci> length ([] :: forall a. [a])
0

Una lista vacía funciona como una lista de cualquier tipo.

Así que con existencial-Cuantificación, foralls en las definiciones data significan que, el valor contenido puede ser de cualquier tipo adecuado, no es que debe ser de todos tipos adecuados.

Otros consejos

Puede cualquiera completamente explicar la palabra clave forall de forma clara, la llanura Inglés?

n. (Bueno, tal vez Don Stewart puede.)

Estas son las barreras para un simple, clara explicación o forall:

Es un cuantificador. Usted tiene un tener al menos un poco de lógica (cálculo de predicados) que han visto un cuantificador universal o existencial. Si usted nunca ha visto cálculo de predicados o no se siente cómodo con los cuantificadores (y he visto a los estudiantes durante doctorado que califican los exámenes que no se sienten cómodos), entonces para ti, no hay una explicación sencilla de forall.
Es un type cuantificador. Si usted no ha visto System F y conseguido un poco de práctica escribiendo tipos polimórficos, que va a encontrar forall confuso. La experiencia con Haskell o ML no es suficiente, ya que normalmente estos idiomas omiten el forall de tipos polimórficos. (En mi opinión, esto es un error del lenguaje de diseño.)
En Haskell, en particular, forall se utiliza en formas que encuentran problemas. (No soy un teórico tipo, pero mi trabajo me pone en contacto con una gran cantidad de de la teoría de tipos, y estoy muy a gusto con él.) Para mí, la principal fuente de confusión es que forall se utiliza para codificar un tipo que yo preferiría escribir con exists. Está justificado por un poco complicado de tipo isomorfismo implica cuantificadores y flechas, y cada vez que quiera entenderlo, tengo que mirar las cosas y resolver el isomorfismo mí mismo.

Si no se siente cómodo con la idea de isomorfismo tipo, o si usted no tiene ningún pensamiento sobre la práctica isomorfismos tipo, este uso de forall va a obstaculizar usted.
Mientras que el concepto general de forall es siempre el mismo (obligatorio introducir una variable de tipo), los detalles de los diferentes usos puede variar significativamente. Inglés informal no es una muy buena herramienta para explicar las variaciones. Para entender realmente lo que está pasando, que necesita algo de matemáticas. En este caso las matemáticas relevantes se pueden encontrar en el texto introductorio de Benjamin Pierce Tipos y Lenguajes de Programación , que es un libro muy bueno.

En cuanto a los ejemplos particulares,

runST debe hacer que su dolor de cabeza. tipos de mayor rango (forall a la izquierda de una flecha) rara vez se encuentran en la naturaleza. Os animo a leer el periódico que introdujo runST: "Lazy funcionales Hilos del Estado" . Este es un muy buen papel, y que le dará una mejor intuición para el tipo de runST en particular, y para este tipo de rango superior en general. La explicación tomar varias páginas, que está muy bien hecho, y yo no voy a tratar de condensar aquí.
Considere
```
foo :: (forall a. a -> a) -> (Char,Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))
```
Si llamo bar, que puede simplemente elegir cualquier tipo a que me gusta, y yo se lo puede transmitir una función de tipo a al tipo a. Por ejemplo, puedo pasar el (+1) función o la reverse función. Se puede pensar en el forall como diciendo "tengo la oportunidad de escoger el tipo de ahora". (La palabra técnica para escoger el tipo es creación de instancias .)

Las restricciones a llamar foo son mucho más estrictas: el argumento a foo debe es una función polimórfica. Con ese tipo, las únicas funciones que pueden pasar a foo son id o una función que siempre diverge o errores, como undefined. La razón es que con foo, la forall está a la izquierda de la flecha, de modo que la persona que llama de foo no me dan a elegir lo que es a-sino que es el aplicación de foo que llega a escoger lo que es a. Debido forall está a la izquierda de la flecha, en lugar de por encima de la flecha como en bar, la creación de instancias tiene lugar en el cuerpo de la función en lugar de en el lugar de llamada.

Resumen: completa explicación de la palabra clave forall requiere matemáticas y sólo puede entenderse por alguien que ha estudiado las matemáticas. Incluso las explicaciones parciales son difíciles de entender sin matemáticas. Pero tal vez mis explicaciones parciales, no matemáticas ayudan un poco. Ir leer Launchbury y Peyton Jones en runST!

Adición: Dicho "arriba", "abajo", "a la izquierda de". Esto no tiene nada que ver con el Pruebas maneras tipos se escriben y todo lo relacionado con los árboles de sintaxis abstracta. En la sintaxis abstracta, un forall toma el nombre de una variable de tipo, y luego hay un tipo completo "por debajo" del forall. Una flecha toma dos tipos (argumento y tipo de resultado) y forma un nuevo tipo (el tipo de función). El tipo de argumento es "a la izquierda de" la flecha; es hijo izquierdo de la flecha en el árbol de sintaxis abstracta.

Ejemplos:

En forall a . [a] -> [a], la forall está por encima de la flecha; lo que es a la izquierda de la flecha es [a].

En

forall n f e x . (forall e x . n e x -> f -> Fact x f) -> Block n e x -> f -> Fact x f

el tipo de paréntesis, sería llamado "un forall a la izquierda de una flecha". (Estoy usando tipos como este en un optimizador que estoy trabajando.)

Mi respuesta original:


¿Alguien puede explicar por completo la palabra clave forall en claro y sencillo Inglés

Como Norman indica, es muy difícil dar una explicación sencilla y clara, Inglés de un término técnico de la teoría de tipos. Todos estamos tratando sin embargo.

No sólo es realmente una cosa que recordar acerca de 'forall': se une a los tipos cierto margen . Una vez que entienda eso, todo es bastante fácil. Es el equivalente a 'lambda' (o una forma de 'dejar') en el nivel de tipo - Norman Ramsey utiliza la noción de "izquierda" / "por encima" de transmitir este mismo concepto de alcance en su excelente respuesta .

La mayoría de los usos de '' forall son muy simples, y se pueden encontrar las introdujeron en la Manual de uso de GHC, S7.8 ., Particularmente la excelente S7.8.5 en anidada formas de 'forall'.

En Haskell, que suele dejar fuera de la carpeta para este tipo, cuando el tipo es universalmente cuantificó, así:

length :: forall a. [a] -> Int

es equivalente a:

length :: [a] -> Int

Eso es todo.

Ya que se puede obligar a variables de tipo ahora hasta cierto alcance, que puede tener alcances otros que el nivel superior ( " universalmente cuantificado "), al igual que el primer ejemplo, donde la variable tipo sólo es visible dentro de la estructura de datos. Esto permite para los tipos ocultos ( " tipos existenciales "). O podemos tener arbitraria anidamiento de enlaces ( "rango tipos N").

Para comprender en profundidad los sistemas de tipo, tendrá que aprender un poco de jerga. Eso es la naturaleza de la informática. Sin embargo, los usos simples, como la de arriba, deben ser capaz de ser captada intuitivamente, mediante analogía con 'dejar' en el nivel de valor. UN gran introducción es Launchbury y Peyton Jones .


Están densamente cargado de supuestos que he leído lo último en lo que sea rama de la matemática discreta, teoría de la categoría o el álgebra abstracta es muy popular esta semana. (Si no leí las palabras "consultar el documento alguno para detalles de la implementación" de nuevo, será demasiado pronto.)

Er, ¿qué pasa con la lógica de primer orden sencillo? forall es bastante claramente en referencia a cuantificación universal , y en ese contexto, el término existencial tiene más sentido también, aunque sería menos difícil si hubiera una palabra clave exists. Ya sea que la cuantificación es efectivamente universal o existencial depende de la colocación del cuantificador en relación con la que las variables se utilizan en qué lado de una flecha de función y que todo es un poco confuso.

Así que, si eso no funciona, o si simplemente no les gusta la lógica simbólica, desde una perspectiva más funcional de programación-ish se puede pensar en las variables de tipo tan sólo estar (implícita) type parámetros a la función. Funciones que toman los parámetros de tipo en este sentido se escriben tradicionalmente usando un lambda de capital por la razón que sea, lo que voy a escribir aquí como /\.

Por lo tanto, tenga en cuenta la función id:

id :: forall a. a -> a id x = x

puede volver a escribir como lambdas, moviendo el "parámetro de tipo" fuera de la firma tipo y añadir anotaciones de tipos de línea:

id = /\a -> (\x -> x) :: a -> a

Aquí está la misma cosa hecha a const:

const = /\a b -> (\x y -> x) :: a -> b -> a

Por lo que su función bar podría ser algo como esto:

bar = /\a -> (\f -> ('t', True)) :: (a -> a) -> (Char, Bool)

Tenga en cuenta que el tipo de la función dada a bar como un argumento depende del parámetro de tipo de bar. Considere si tuviera algo como esto en su lugar:

bar2 = /\a -> (\f -> (f 't', True)) :: (a -> a) -> (Char, Bool)

Aquí bar2 está aplicando la función a algo de tipo Char, dando así bar2 cualquier tipo de parámetro que no sea Char provocará un error de tipo.

Por otra parte, esto es lo foo podría ser:

foo = (\f -> (f Char 't', f Bool True))

A diferencia de bar, foo en realidad no toma ningún parámetro de tipo en absoluto! Se necesita una función que sí toma un parámetro de tipo, a continuación, se aplica esa función a dos diferente tipos.

Así que cuando ves una forall en una firma de tipo, sólo piensa en él como un expresión lambda para las firmas de tipos . Al igual que lambdas regulares, el alcance de forall se extiende lo más a la derecha como sea posible, hasta paréntesis que encierra, y al igual que las variables de la envolvente en un lambda regular, las variables de tipo vinculados por un forall sólo son de alcance dentro de la expresión cuantificada.

Post scriptum : Tal vez usted podría preguntarse - ahora que estamos pensando en las funciones que tienen parámetros de tipo, por qué no podemos hacer algo más interesante con los parámetros que ponerlos en una firma de tipo ? La respuesta es que se puede!

Una función que pone variables tipo junto con una etiqueta y devuelve un nuevo tipo es un constructor de tipo , que se podría escribir algo como esto:

Either = /\a b -> ...

Pero necesitaría completamente nueva notación, ya que la forma en que se escribe este tipo, como Either a b, ya es sugerente de "aplicar el Either función de estos parámetros".

Por otra parte, una función de este tipo de partidos "patrón" en sus parámetros de tipo, que regresan valores diferentes para diferentes tipos, es un método de una clase de tipo . Una ligera expansión a mi sintaxis /\ anterior sugiere algo como esto:

fmap = /\ f a b -> case f of Maybe -> (\g x -> case x of Just y -> Just b g y Nothing -> Nothing b) :: (a -> b) -> Maybe a -> Maybe b [] -> (\g x -> case x of (y:ys) -> g y : fmap [] a b g ys [] -> [] b) :: (a -> b) -> [a] -> [b]

En lo personal, creo que prefiero syn real de Haskellimpuestos ...

Una función que "Corresponde al modelo" sus parámetros de tipo y devuelve un arbitrarias, tipo existente es un tipo de familia o dependencia funcional - en el primer caso, incluso ya se ve mucho a una definición de función.

Aquí está una explicación rápida y sucia en términos claros que es muy probable que estar ya familiarizado.

La palabra clave forall está realmente sólo se utiliza de una manera en Haskell. Siempre significa lo mismo que cuando lo ves.

universal cuantificación

A tipo universalmente cuantificado es un tipo de la forma forall a. f a. Un valor de ese tipo puede ser pensado como una función que toma un Tipo a como su argumento y devuelve un valor de tipo f a. Excepto que en Haskell estos argumentos de tipo se transmiten implícitamente por el sistema de tipos. Esta "función" tiene que darle el mismo valor, independientemente del tipo que recibe, por lo que el valor es polimórfica .

Por ejemplo, considere el tipo forall a. [a]. Un valor de ese tipo da otro tipo a y le da una copia de una lista de elementos de esa misma a tipo. Sólo hay una posible implementación, por supuesto. Tendría que darle la lista vacío porque a podría ser absolutamente cualquier tipo. La lista vacía es el único valor lista que es polimórfico en su tipo de elemento (ya que no tiene elementos).

O el tipo forall a. a -> a. La persona que llama de la función tal proporciona tanto una a tipo y un valor de tipo a. La aplicación entonces tiene que devolver un valor de ese mismo tipo a. Sólo hay una posible implementación de nuevo. Se tendría que devolver el mismo valor que se le dio.

existencial cuantificación

Un tipo existencialmente cuantificada tendría la forma exists a. f a, si Haskell apoyó esa notación. Un valor de este tipo puede ser pensado como un par (o un "producto") que consiste en un a tipo y un valor de tipo f a.

Por ejemplo, si tiene un valor de tipo exists a. [a], usted tiene una lista de elementos de algún tipo. Podría ser de cualquier tipo, pero incluso si usted no sabe lo que es que hay mucho que podría hacer a la lista un ejemplo. Se podría revertirla, o podría contar el número de elementos, o realizar cualquier otra operación de la lista que no depende del tipo de los elementos.

OK, así que espera un minuto. ¿Por qué el uso de Haskell forall para denotar un tipo de "existencial" como la siguiente?

data ShowBox = forall s. Show s => SB s

Puede ser confuso, pero en realidad describe el tipo de datos de la constructora SB:

SB :: forall s. Show s => s -> ShowBox

Una vez construido, se puede pensar en un valor de tipo ShowBox que consiste en dos cosas. Es un conjunto s tipo con un valor de tipo s. En otras palabras, se trata de un valor de un tipo existencialmente cuantificada. ShowBox realmente podría ser escrito como exists s. Show s => s, si Haskell apoyó esa notación.

runST y amigos

Dado que, ¿cómo es esto diferente?

foo :: (forall a. a -> a) -> (Char,Bool) bar :: forall a. ((a -> a) -> (Char, Bool))

Vamos primera toma bar. Se necesita un a tipo y función del tipo de a -> a, y produce un valor de tipo (Char, Bool). Podríamos elegir Int como el a y darle una función del tipo Int -> Int por ejemplo. Pero foo es diferente. Se requiere que la aplicación de foo poder pasar cualquier tipo que quiere la función que le damos. Así que la única función que podríamos razonablemente damos es id.

Ahora debería ser capaz de abordar el significado del tipo de runST:

runST :: forall a. (forall s. ST s a) -> a

Así runST tiene que ser capaz de producir un valor de tipo a, no importa qué tipo damos como a. Para ello, se necesita un argumento de tipo forall s. ST s a que bajo el capó es sólo una función del tipo forall s. s -> (a, s). Esa función entonces tiene que ser capaz de producir un valor de tipo (a, s) no importa de qué tipo es la implementación de runST decide dar como s.

OK, ¿y qué? El beneficio es que esto pone una limitación a la persona que llama de runST en que el tipo a no puede implicar la s tipo en absoluto. No se puede pasar un valor de tipo ST s [s], por ejemplo. Lo que esto significa en la práctica es que la aplicación de runST está libre para realizar mutación con el valor de tipo s. El sistema de tipos garantiza que esta mutación es local a la aplicación de runST.

El tipo de runST es un ejemplo de un rango-2 tipo polimórfico porque el tipo de su argumento contiene un cuantificador forall. El tipo de foo anterior es también de rango 2. Un tipo polimórfico ordinaria, como la de bar, es rango-1, pero se convierte en rango-2 si se requieren los tipos de argumentos para ser polimórficos, con su propio cuantificador forall. Y si una función toma argumentos de rango-2, entonces su tipo es de rango 3, y así sucesivamente. En general, un tipo que toma argumentos polimórficas de n rango tiene n + 1 rango.

La razón por la que hay diferentes usos de esta palabra clave es que realmente se utiliza en al menos dos extensiones del sistema de diferente tipo:. Tipos de rango superior, y los existenciales

Es probablemente el mejor sólo para leer y comprender esas dos cosas por separado, en lugar de tratar de obtener una explicación de por qué 'forall' es un bit apropiado de sintaxis en ambos al mismo tiempo.


¿Alguien puede explicar por completo la palabra clave forall en claro y sencillo Inglés (o, si existe en algún lugar, seleccione una explicación tan clara, que he echado de menos) que no asume que soy un matemático sumida en la jerga?

Voy a tratar de explicar sólo el significado y tal vez la aplicación de forall en el contexto de Haskell y sus sistemas de tipo.

Pero antes de entender que me gustaría dirigir a una charla muy accesible y agradable por Runar Bjarnason titulado " Restricciones liberar, Libertades Restringir ". La charla está llena de ejemplos de casos de uso del mundo real, así como ejemplos en Scala para apoyar esta afirmación, aunque no menciona forall. Voy a tratar de explicar el punto de vista forall a continuación.

CONSTRAINTS LIBERATE, LIBERTIES CONSTRAIN

Es muy importante para digerir y creer esta declaración para proceder con la siguiente explicación, por lo que insto a ver la charla (al menos partes de la misma).

Ahora un ejemplo muy común, que muestra la expresividad del sistema de tipos de Haskell es este tipo de firma:

foo :: a -> a

Se dice que dado este tipo de firma, sólo hay una función que puede satisfacer este tipo y que es la función identity o lo que es más conocido popularmente id.

En las etapas iniciales de mi aprendizaje Haskell, siempre se preguntaba el siguiente funciones:

foo 5 = 6 foo True = False

que ambos satisfacen la firma tipo anterior, entonces ¿por qué la gente Haskell afirman que es id solos, que satisface el tipo de firma?

Eso es porque hay una forall implícita escondido en la declaración de tipo. El tipo real es:

id :: forall a. a -> a

Así que, ahora volvamos a la declaración: Restricciones liberan, las libertades restricción

Traducción que para el sistema de tipos, esta afirmación se convierte en:

Una restricción en el nivel de tipo, se convierte en una libertad a nivel plazo

y

Una libertad en el nivel de tipo, se convierte en una restricción a nivel plazo

Vamos a tratar de probar la primera declaración:

Una restricción en el nivel de tipo ..

Así que poner un obstáculo en nuestra firma de tipo

foo :: (Num a) => a -> a

se convierte en una libertad a nivel plazo nos da la libertad o la flexibilidad para escribir todo esto

foo 5 = 6 foo 4 = 2 foo 7 = 9 ...

Lo mismo se puede observar al restringir a con cualquier otra clase de tipos, etc.

Así que ahora lo que este tipo de firma: foo :: (Num a) => a -> a traduce es:

∃a , st a -> a, ∀a ∈ Num

Esto se conoce como cuantificación existencial, que se traduce en existe algunos casos de a para los que una función cuando alimenta algo de los rendimientos a tipo algo del mismo tipo, y aquellos casos todos pertenecen a la conjunto de números.

Por lo tanto podemos ver la adición de una restricción (que a debe pertenecer al conjunto de los Números), libera el nivel plazo para tener varias implementaciones posibles.

Ahora que se acerca a la segunda afirmación y la que realmente lleva la explicación de forall:

Una libertad en el nivel de tipo, se convierte en una restricción a nivel plazo

Así que ahora vamos a liberar el la función en el nivel de tipo:

foo :: forall a. a -> a

Ahora bien, esto se traduce en:

∀a , a -> a

Lo que significa que la implementación de este tipo de firma debe ser tal que es a -> a para todas las circunstancias.

Así que ahora esto comienza con nosotros limitando a nivel plazo. Podemos escribir ya no

foo 5 = 7

ya que esta aplicación no satisfaría si ponemos a como Bool. a puede ser un Char o una [Char]o un tipo de datos personalizado. En todas las circunstancias debe devolver algo del tipo similar. Esta libertad en el nivel de tipo es lo que se conoce como universal Cuantificación y la única función que puede satisfacer esto es

foo a = a

que se conoce comúnmente como la función identity

Por lo tanto forall es un liberty en el nivel de tipo, cuyo propósito real es constrain el nivel plazo a una aplicación particular.

¿Cómo es existencial existencial?


Con existencial-Cuantificación, foralls en las definiciones data significan   que, el valor puede ser de cualquier tipo adecuado, no contenía   que debe ser de todos tipos adecuados.   - respuesta de Yachiru

Una explicación de por qué forall en las definiciones data son isomorfos a (exists a. a) (pseudo-Haskell) se puede encontrar en "de Wikilibros Haskell / tipos cuantificada existencialmente" .

El siguiente es un breve resumen textualmente:

data T = forall a. MkT a -- an existential datatype MkT :: forall a. a -> T -- the type of the existential constructor

Cuando de coincidencia de patrón / deconstrucción MkT x, ¿cuál es el tipo de x?

foo (MkT x) = ... -- -- what is the type of x?

x puede ser cualquier tipo (como se indica en el forall), y por lo que es tipo es:

x :: exists a. a -- (pseudo-Haskell)

Por lo tanto, los siguientes son isomorfos:

data T = forall a. MkT a -- an existential datatype data T = MkT (exists a. a) -- (pseudo-Haskell)

forall significa forall

Mi interpretación sencilla de todo esto, es que "forall realmente significa 'para todos'". Una distinción importante que hacer es el impacto de forall en el Definición contra la función aplicación .

A forall significa la definición del valor o función debe ser polimórfico.

Si lo que se define es un polimórfica valor , entonces significa que el valor debe ser válido para todos a adecuado, que es bastante restrictivo.

Si lo que se define es un polimórfica función , entonces significa que la función debe ser válido para todos a adecuado, que no es tan restrictivo porque sólo porque la función es polimórfico no lo hace significa el parámetro siendo aplicado tiene que ser polimórfico. Es decir, si la función es válida para todos a, a continuación, por el contrario cualquier a adecuado puede ser aplicado para la función. Sin embargo, el tipo de parámetro sólo se puede elegir una vez en la definición de función.

Si un forall está dentro tipo del parámetro de función (es decir, un Rank2Type), entonces significa que el aplicado parámetro debe ser realmente polimórfica, para ser coherente con la idea de medios forall definición es polimórfico. En este caso, el tipo del parámetro se puede elegir más de una vez en la definición de función ( "y es elegido por la implementación de la función ", como salir en punta por Norman )

Por lo tanto, la razón por la cual las definiciones data existencial permite cualquier a es porque el constructor de datos es un polimorfo Función

MkT :: forall a. a -> T

tipo de MKT :: a -> *

Lo que significa que cualquier a se puede aplicar a la función. A diferencia de, digamos, un polimórfica valor

valueT :: forall a. [a]

tipo de Valuet :: a

Lo que significa que el Definición de Valuet debe ser polimórficos. En este caso, valueT se puede definir como lista vacía [] de todo tipo.

[] :: [t]

Diferencias

A pesar de que el significado de forall es consistente en ExistentialQuantification y RankNType, los existenciales tiene una diferencia desde el constructor data se puede utilizar en la coincidencia de patrones. Como se documenta en la ghc guía del usuario :


Cuando coincidencia de patrones, cada coincidencia de patrón introduce un nuevo, distinto, tipo para cada variable de tipo existencial. Estos tipos no se pueden unificar con cualquier otro tipo, ni pueden escapar del alcance de la coincidencia de patrón.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow