haskell - ¿Cuál es el propósito de Rank2Types?

polymorphism higher-rank-types

Question

No soy muy hábil en Haskell, así que esta podría ser una pregunta muy fácil.

¿Qué limitación de idioma resuelve Rank2Types ? ¿Las funciones en Haskell ya no admiten los argumentos polimórficos?

Answer 1

¿Las funciones en Haskell ya no admiten los argumentos polimórficos?

Lo hacen, pero solo del rango 1. Esto significa que aunque puede escribir una función que toma diferentes tipos de argumentos sin esta extensión, no puede escribir una función que use su argumento como tipos diferentes en la misma invocación.

Por ejemplo, la siguiente función no se puede escribir sin esta extensión porque g se usa con diferentes tipos de argumentos en la definición de f :

f g = g 1 + g "lala"

Tenga en cuenta que es perfectamente posible pasar una función polimórfica como argumento para otra función. Entonces algo como map id ["a","b","c"] es perfectamente legal. Pero la función solo puede usarlo como monomórfico. En el map ejemplo, se usa id como si tuviera tipo String -> String . Y, por supuesto, también puede pasar una función monomórfica simple del tipo dado en lugar de id . Sin rank2types no hay forma de que una función requiera que su argumento sea una función polimórfica y, por lo tanto, tampoco la forma de usarlo como una función polimórfica.

Answer 2

Es difícil entender el polimorfismo de rango superior a menos que estudie System F directamente, porque Haskell está diseñado para ocultar los detalles de eso en interés de la simplicidad.

Pero básicamente, la idea aproximada es que los tipos polimórficos realmente no tienen la a -> b que tienen en Haskell; en realidad, se ven así, siempre con cuantificadores explícitos:

id :: ∀a.a → a
id = Λt.λx:t.x

Si no conoce el símbolo "∀", se lee como "para todos"; ∀x.dog(x) significa "para todo x, x es un perro". "Λ" es capital lambda, usado para abstraer sobre parámetros de tipo; lo que dice la segunda línea es que id es una función que toma un tipo t , y luego devuelve una función que está parametrizada por ese tipo.

Verá, en el Sistema F, no puede simplemente aplicar una función como esa id a un valor de inmediato; primero debe aplicar la función to a un tipo para obtener una función λ que aplique a un valor. Así por ejemplo:

(Λt.λx:t.x) Int 5 = (λx:Int.x) 5
                  = 5

Standard Haskell (es decir, Haskell 98 y 2010) simplifica esto para usted al no tener ninguno de estos tipos de cuantificadores, capital lambdas y aplicaciones de tipo, sino que detrás de las escenas GHC los coloca cuando analiza el programa para su compilación. (Esto es todo el tiempo de compilación, creo, sin sobrecarga en tiempo de ejecución).

Pero el manejo automático de Haskell de esto significa que asume que "∀" nunca aparece en la rama de la izquierda de una función ("→") tipo. Rank2Types y RankNTypes desactivan esas restricciones y le permiten anular las reglas predeterminadas de Haskell para RankNTypes dónde insertar forall .

Por qué querrías hacer esto? Porque el Sistema F completo e irrestricto es muy poderoso y puede hacer muchas cosas interesantes. Por ejemplo, escriba hidden y la modularidad se puede implementar utilizando tipos de rango superior. Tomemos por ejemplo una vieja función simple del siguiente tipo de rango 1 (para establecer la escena):

f :: ∀r.∀a.((a → r) → a → r) → r

Para usar f , la persona que llama primero debe elegir qué tipos usar para r y a , luego proporcionar un argumento del tipo resultante. Entonces puedes elegir r = Int y a = String :

f Int String :: ((String → Int) → String → Int) → Int

Pero ahora compare eso con el siguiente tipo de rango superior:

f'' :: ∀r.(∀a.(a → r) → a → r) → r

¿Cómo funciona una función de este tipo? Bueno, para usarlo, primero especifica qué tipo usar para r . Digamos que elegimos Int :

f'' Int :: (∀a.(a → Int) → a → Int) → Int

Pero ahora ∀a está dentro de la flecha de función, por lo que no puede elegir qué tipo de uso usará; debe aplicar f'' Int a una Λ función del tipo apropiado. Esto significa que la implementación de f'' escoge qué tipo usar para a , no quien llama a f'' . Sin tipos de rango superior, por el contrario, la persona que llama siempre elige los tipos.

Para que sirve esto? Bueno, para muchas cosas en realidad, pero una idea es que puedes usar esto para modelar cosas como la programación orientada a objetos, donde los "objetos" agrupan algunos datos ocultos junto con algunos métodos que funcionan con los datos ocultos. Por ejemplo, un objeto con dos métodos, uno que devuelve un Int y otro que devuelve un String , podría implementarse con este tipo:

myObject :: ∀r.(∀a.(a → Int, a -> String) → a → r) → r

¿Como funciona esto? El objeto se implementa como una función que tiene algunos datos internos de tipo oculto a . Para usar realmente el objeto, sus clientes pasan una función de "devolución de llamada" que el objeto llamará con los dos métodos. Por ejemplo:

myObject String (Λa. λ(length, name):(a → Int, a → String). λobjData:a. name objData)

Aquí estamos, básicamente, invocando el segundo método del objeto, aquel cuyo tipo es a → String para un desconocido a . Bueno, desconocido para los clientes de myObject ; pero estos clientes sí saben, a partir de la firma, que podrán aplicar cualquiera de las dos funciones y obtener un Int o un String .

Para un ejemplo real de Haskell, a continuación se muestra el código que escribí cuando aprendí RankNTypes . Esto implementa un tipo llamado ShowBox que agrupa un valor de algún tipo oculto junto con su instancia Show class. Tenga en cuenta que en el ejemplo de la parte inferior, hago una lista de ShowBox cuyo primer elemento se creó a partir de un número y el segundo de una cadena. Como los tipos están ocultos mediante el uso de tipos de rango superior, esto no infringe la verificación de tipo.

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ImpredicativeTypes #-}

type ShowBox = forall b. (forall a. Show a => a -> b) -> b

mkShowBox :: Show a => a -> ShowBox
mkShowBox x = /k -> k x

-- | This is the key function for using a ''ShowBox''.  You pass in
-- a function @k@ that will be applied to the contents of the 
-- ShowBox.  But you don''t pick the type of @k@''s argument--the 
-- ShowBox does.  However, it''s restricted to picking a type that
-- implements @Show@, so you know that whatever type it picks, you
-- can use the ''show'' function.
runShowBox :: forall b. (forall a. Show a => a -> b) -> ShowBox -> b
-- Expanded type:
--
--     runShowBox 
--         :: forall b. (forall a. Show a => a -> b) 
--                   -> (forall b. (forall a. Show a => a -> b) -> b)
--                   -> b
--
runShowBox k box = box k


example :: [ShowBox] 
-- example :: [ShowBox] expands to this:
--
--     example :: [forall b. (forall a. Show a => a -> b) -> b]
--
-- Without the annotation the compiler infers the following, which
-- breaks in the definition of ''result'' below:
--
--     example :: forall b. [(forall a. Show a => a -> b) -> b]
--
example = [mkShowBox 5, mkShowBox "foo"]

result :: [String]
result = map (runShowBox show) example

PD: para cualquiera que lea esto y se pregunte cómo es que ExistentialTypes en GHC, creo que la razón es porque está usando este tipo de técnica detrás de escena.

Answer 3

Los tipos de rango más alto no son tan exóticos como las otras respuestas han hecho. Créalo o no, muchos lenguajes orientados a objetos (¡incluidos Java y C #!) Los caracterizan. (Por supuesto, nadie en esas comunidades los conoce por el nombre aterrador "tipos de rango superior").

El ejemplo que voy a dar es una implementación de libro de texto del patrón Visitor, que utilizo todo el tiempo en mi trabajo diario. Esta respuesta no pretende ser una introducción al patrón de visitante; ese conocimiento está available elsewhere .

En esta fatua aplicación imaginaria de recursos humanos, deseamos operar con empleados que pueden ser personal permanente o contratistas temporales. Mi variante preferida del patrón Visitor (y de hecho la que es relevante para RankNTypes ) parametriza el tipo de devolución del visitante.

interface IEmployeeVisitor<T>
{
    T Visit(PermanentEmployee e);
    T Visit(Contractor c);
}

class XmlVisitor : IEmployeeVisitor<string> { /* ... */ }
class PaymentCalculator : IEmployeeVisitor<int> { /* ... */ }

El punto es que una cantidad de visitantes con diferentes tipos de devolución pueden operar con los mismos datos. Esto significa que IEmployee debe expresar ninguna opinión sobre lo que T debe ser.

interface IEmployee
{
    T Accept<T>(IEmployeeVisitor<T> v);
}
class PermanentEmployee : IEmployee
{
    // ...
    public T Accept<T>(IEmployeeVisitor<T> v)
    {
        return v.Visit(this);
    }
}
class Contractor : IEmployee
{
    // ...
    public T Accept<T>(IEmployeeVisitor<T> v)
    {
        return v.Visit(this);
    }
}

Deseo llamar su atención sobre los tipos. Observe que IEmployeeVisitor cuantifica universalmente su tipo de devolución, mientras que IEmployee cuantifica dentro de su método Accept , es decir, en un rango superior. Traduciendo clunkily de C # a Haskell:

data IEmployeeVisitor r = IEmployeeVisitor {
    visitPermanent :: PermanentEmployee -> r,
    visitContractor :: Contractor -> r
}

newtype IEmployee = IEmployee {
    accept :: forall r. IEmployeeVisitor r -> r
}

Entonces ahí lo tienes. Los tipos de rango superior aparecen en C # cuando escribe tipos que contienen métodos genéricos.

Answer 4

Para aquellos familiarizados con los lenguajes orientados a objetos, una función de rango superior es simplemente una función genérica que espera como argumento otra función genérica.

Por ejemplo, en TypeScript podría escribir:

type WithId<T> = T & { id: number }
type Identifier = <T>(obj: T) => WithId<T>
type Identify = <TObj>(obj: TObj, f: Identifier) => WithId<TObj>

Vea cómo el tipo de función genérico Identify demanda una función genérica del tipo Identifier . Esto hace que Identify una función de rango superior.

Answer 5

La respuesta de Luis Casillas brinda mucha información excelente sobre lo que significan los tipos de rango 2, pero ampliaré un punto que no abarcó. Exigir que un argumento sea polimórfico no solo permite que se use con múltiples tipos; también restringe lo que esa función puede hacer con su (s) argumento (s) y cómo puede producir su resultado. Es decir, le da a quien llama menos flexibilidad. ¿Por qué querrías hacer eso? Comenzaré con un simple ejemplo:

Supongamos que tenemos un tipo de datos

data Country = BigEnemy | MediumEnemy | PunyEnemy | TradePartner | Ally | BestAlly

y queremos escribir una función

f g = launchMissilesAt $ g [BigEnemy, MediumEnemy, PunyEnemy]

eso toma una función que se supone que debe elegir uno de los elementos de la lista que se le da y devolver una acción IO lanzando misiles en ese objetivo. Podríamos darle a f un tipo simple:

f :: ([Country] -> Country) -> IO ()

El problema es que podríamos correr accidentalmente

f (/_ -> BestAlly)

y entonces estaríamos en un gran problema! Dando f un rango 1 tipo polimórfico

f :: ([a] -> a) -> IO ()

no ayuda en absoluto, porque elegimos el tipo a cuando llamamos f , y solo lo especializamos en Country y usamos nuestro /_ -> BestAlly nuevamente. La solución es usar un tipo de rango 2:

f :: (forall a . [a] -> a) -> IO ()

Ahora se requiere que la función que pasamos sea polimórfica, así que /_ -> BestAlly no escribirá verificación! De hecho, ninguna función que devuelva un elemento que no esté en la lista que se le asignará hará una comprobación de tipo (aunque algunas funciones que entran en bucles infinitos o producen errores y, por lo tanto, nunca regresan, lo harán).

Lo anterior está ideado, por supuesto, pero una variación de esta técnica es clave para hacer que la mónada de ST segura.

Answer 6

Las diapositivas del curso Haskell de Bryan O''Sullivan en Stanford me ayudaron a entender Rank2Types .