haskell - prelude - Las funciones no solo tienen tipos: SON tipos. Y tipos. Y Sorts. Ayuda a volver a pensar

tipo show haskell (2)

Estaba haciendo mi rutina habitual de "Leer un capítulo de LYAH before bed", sintiendo que mi cerebro se expandía con cada muestra de código. En este punto, estaba convencido de que entendía la maravilla central de Haskell, y ahora solo tenía que entender las bibliotecas estándar y las clases de tipos para poder comenzar a escribir software real.

Así que estaba leyendo el capítulo sobre los funtores aplicativos cuando, de repente, el libro afirmaba que las funciones no solo tienen tipos, son tipos y pueden tratarse como tales (por ejemplo, al convertirlas en instancias de clases de tipos). (->) es un constructor de tipos como cualquier otro.

Mi mente explotó una vez más, e inmediatamente salté de la cama, encendí la computadora, fui a GHCi y descubrí lo siguiente:

Prelude> :k (->) (->) :: ?? -> ? -> *

¿Qué diablos significa?
Si (->) es un constructor de tipos, ¿cuáles son los constructores de valores? Puedo adivinar, pero no tengo idea de cómo se define en los data (->) ... = ... | ... | ... tradicionales data (->) ... = ... | ... | ... data (->) ... = ... | ... | ... data (->) ... = ... | ... | ... formato. Es bastante fácil hacer esto con cualquier otro constructor de tipo: data Either ab = Left a | Right b data Either ab = Left a | Right b . Sospecho que mi incapacidad para expresarlo en esta forma está relacionada con la firma de tipo extremadamente extraña.
¿Con qué me he encontrado? Los tipos con mayor nivel tienen firmas de tipo como * -> * -> * . Ahora que lo pienso ... (->) aparece en firmas de tipo también! ¿Esto significa que no solo es un constructor de tipos, sino también un constructor amable? ¿Está relacionado con los signos de interrogación en la firma de tipo?

He leído en alguna parte (ojalá pudiera encontrarlo de nuevo, Google me falla) acerca de poder extender los sistemas de tipos arbitrariamente yendo desde Valores, a Tipos de valores, a Tipos de tipos, a Clases de tipos, a otra cosa de Sorts, a algo más de algo más, y así sucesivamente para siempre. ¿Esto se refleja en la amable firma de (->)? Porque también me he topado con la noción del cubo Lambda y el cálculo de las construcciones sin tomarme el tiempo de investigarlas realmente, y si mal no recuerdo es posible definir funciones que toman tipos y tipos de retorno, toman valores y devuelven valores , tome tipos y devuelva valores, y tome valores que devuelvan tipos.

Si tuviera que adivinar la firma de tipo para una función que toma un valor y devuelve un tipo, probablemente lo expresaría así:

a -> ?

o posiblemente

a -> *

Aunque no veo una razón fundamental inmutable, el segundo ejemplo no se puede interpretar fácilmente como una función de un valor de tipo a a un valor de tipo *, donde * es solo un sinónimo de cadena o algo así.

El primer ejemplo expresa mejor una función cuyo tipo trasciende una firma de tipo en mi mente: "una función que toma un valor de tipo a y devuelve algo que no puede expresarse como un tipo".

En primer lugar, el ?? -> ? -> * ?? -> ? -> * ?? -> ? -> * kind es una extensión específica de GHC. El ? y ?? están ahí para lidiar con los tipos de unboxed, que se comportan de forma diferente a just * (que tiene que estar encuadrado, hasta donde yo sé). Entonces ?? puede ser cualquier tipo normal o un tipo no incluido (por ejemplo, Int# ); ? puede ser cualquiera de esas o una tupla sin caja. Hay más información aquí: Haskell Weird Kinds: Tipo de (->) es ?? ->? -> *

Creo que una función no puede devolver un tipo sin caja porque las funciones son flojas. Como un valor diferido es un valor o un thunk, debe estar encuadrado. En caja solo significa que es un puntero en lugar de solo un valor: es como Integer() vs int en Java.

Dado que probablemente no va a utilizar tipos sin caja en el código de nivel LYAH, puede imaginarse que el tipo de -> es solo * -> * -> * .

Desde el ? y ?? son básicamente una versión más general de * , no tienen nada que ver con géneros ni nada de eso.

Sin embargo, dado que -> es simplemente un constructor de tipos, en realidad puede aplicarlo parcialmente; por ejemplo, (->) e es una instancia de Functor y Monad . Averiguar cómo escribir estas instancias es un buen ejercicio de estiramiento de la mente.

En cuanto a los constructores de valores, deberían simplemente ser lambdas ( / x -> ) o declaraciones de funciones. Como las funciones son tan fundamentales para el lenguaje, obtienen su propia sintaxis.

Tocas muchos puntos interesantes en tu pregunta, así que me temo que esta será una respuesta larga :)

Tipo de (->)

El tipo de (->) es * -> * -> * , si ignoramos las inserciones de GHC de la caja. Pero no hay circularidad, los -> s en el tipo de (->) son flechas amables, no flechas de función. De hecho, para distinguirlos, las flechas amables podrían escribirse como (=>) , y luego el tipo de (->) es * => * => * .

Podemos considerar (->) como un constructor de tipo, o tal vez más bien un operador de tipo. Del mismo modo, (=>) podría ser visto como un operador amable , y como usted sugiere en su pregunta, tenemos que subir un ''nivel''. Volvemos a esto más adelante en la sección Beyond Kinds , pero primero:

Cómo se ve la situación en un lenguaje dependiente

Usted pregunta cómo se vería la firma de tipo para una función que toma un valor y devuelve un tipo. Esto es imposible de hacer en Haskell: ¡las funciones no pueden devolver tipos! Puede simular este comportamiento utilizando clases de tipos y familias de tipos, pero permítanos, por ejemplo, cambiar el lenguaje al lenguaje de tipo dependiente Agda . Este es un lenguaje con una sintaxis similar a la de Haskell en la que los tipos de malabarismo junto con los valores son de naturaleza secundaria.

Para tener algo con qué trabajar, definimos un tipo de datos de números naturales, por conveniencia en la representación unaria como en Aritmética de Peano . Los tipos de datos están escritos en estilo GADT :

data Nat : Set where Zero : Nat Succ : Nat -> Nat

Set es equivalente a * en Haskell, el "tipo" de todos los tipos (pequeños), como los números naturales. Esto nos dice que el tipo de Nat es Set , mientras que en Haskell, Nat no tendría un tipo, tendría un tipo, a saber * . En Agda no hay clases, pero todo tiene un tipo.

Ahora podemos escribir una función que toma un valor y devuelve un tipo. A continuación se muestra una función que toma un número natural n un tipo, y hace iterar el constructor List n aplicado a este tipo. (En Agda, [a] generalmente se escribe List a )

listOfLists : Nat -> Set -> Set listOfLists Zero a = a listOfLists (Succ n) a = List (listOfLists n a)

Algunos ejemplos:

listOfLists Zero Bool = Bool listOfLists (Succ Zero) Bool = List Bool listOfLists (Succ (Succ Zero)) Bool = List (List Bool)

Ahora podemos hacer una función de map que opere en listsOfLists . Necesitamos tomar un número natural que es el número de iteraciones del constructor de la lista. Los casos base son cuando el número es Zero , luego listOfList es solo la identidad y aplicamos la función. El otro es la lista vacía, y se devuelve la lista vacía. El caso del paso es un movimiento de pequeña cantidad que implica: aplicamos mapN al encabezado de la lista, pero esto tiene una capa menos de anidamiento y mapN para el resto de la lista.

mapN : {a b : Set} -> (a -> b) -> (n : Nat) -> listOfLists n a -> listOfLists n b mapN f Zero x = f x mapN f (Succ n) [] = [] mapN f (Succ n) (x :: xs) = mapN f n x :: mapN f (Succ n) xs

En el tipo de mapN , el argumento Nat se llama n , por lo que el resto del tipo puede depender de él. Entonces este es un ejemplo de un tipo que depende de un valor.

_{Como nota al margen, también hay otras dos variables nombradas aquí, a saber, los primeros argumentos, a y b , del tipo Set .} _{Las variables de tipo se cuantifican implícita y universalmente en Haskell, pero aquí debemos deletrearlas y especificar su tipo, a saber, Set .} _{Los corchetes están ahí para hacerlos invisibles en la definición, ya que siempre son deducibles de los otros argumentos.}

El conjunto es abstracto

Usted pregunta qué son los constructores de (->) . Una cosa para señalar es que Set (así como * en Haskell) es abstracto: no se puede coincidir con el patrón. Entonces esto es Agda ilegal:

cheating : Set -> Bool cheating Nat = True cheating _ = False

De nuevo, puede simular la coincidencia de patrones en constructores de tipos en Haskell usando familias de tipos, un ejemplo canoical se da en el blog de Brent Yorgey . ¿Podemos definir -> en el Agda? Como podemos devolver tipos de funciones, podemos definir una versión propia de -> siguiente manera:

_=>_ : Set -> Set -> Set a => b = a -> b

(los operadores de infijo se escriben _=>_ lugar de (=>) ) Esta definición tiene muy poco contenido, y es muy similar a hacer un sinónimo de tipo en Haskell:

type Fun a b = a -> b

Más allá de las clases: tortugas hasta el fondo

Como se prometió anteriormente, todo en Agda tiene un tipo, pero el tipo de _=>_ debe tener un tipo. Esto toca tu punto sobre géneros, que es, por así decirlo, una capa por encima de Set (los tipos). En Agda esto se llama Set1 :

FunType : Set1 FunType = Set -> Set -> Set

¡Y de hecho, hay una jerarquía completa de ellos! Establecer es el tipo de tipos "pequeños": tipos de datos en haskell. Pero luego tenemos Set1 , Set2 , Set3 , y así sucesivamente. Set1 es el tipo de tipos que menciona Set . Esta jerarquía es para evitar inconsistencias como la paradoja de Girard.

Como se notó en su pregunta, -> se usa para tipos y tipos en Haskell, y la misma notación se usa para el espacio funcional en todos los niveles en Agda. Esto debe considerarse como un operador de tipo incorporado, y los constructores son abstracción lambda (o definiciones de funciones). Esta jerarquía de tipos es similar a la configuración en System F omega , y se puede encontrar más información en los capítulos posteriores de Tipos de Pierce y Lenguajes de Programación .

Sistemas de tipo puro

En Agda, los tipos pueden depender de los valores, y las funciones pueden devolver tipos, como se ilustró anteriormente, y también teníamos una jerarquía de tipos. La investigación sistemática de diferentes sistemas de cálculos lambda se investiga con más detalle en Pure Type Systems. Una buena referencia es Lambda Calculi with Types by Barendregt, donde se introducen PTS en la página 96 y muchos ejemplos en la página 99 en adelante. También puedes leer más sobre el cubo lambda allí.