haskell - sencillos - ¿Cuál es la diferencia entre el polimorfismo paramétrico y los tipos de tipo superior?

qué es el polimorfismo en la poo

Question

Estoy bastante seguro de que no son lo mismo. Sin embargo, estoy atascado por la idea común de que "Rust no admite" tipos de tipo más alto (HKT), sino que ofrece polimorfismo paramétrico . Traté de entender esto y entender la diferencia entre estos, pero me enredé cada vez más.

A mi entender, hay tipos de clase superior en Rust, al menos los conceptos básicos. Usando la notación "*", un HKT tiene una especie de, por ejemplo, * -> * . Por ejemplo, Maybe sea ​​de tipo * -> * y podría implementarse así en Haskell.

data Maybe a = Just a | Nothing

Aquí,

• Maybe sea ​​un tipo constructor y deba aplicarse a un tipo concreto para convertirse en un tipo concreto de tipo "*".
• Just a y Nothing son constructores de datos.

En los libros de texto sobre Haskell, esto se usa a menudo como un ejemplo para un tipo de clase superior. Sin embargo, en Rust se puede implementar simplemente como una enumeración, que después de todo es un tipo de suma :

enum Maybe<T> {
    Just(T),
    Nothing,
}

¿Dónde está la diferencia? A mi entender, este es un ejemplo perfectamente perfecto de un tipo de clase superior.

1. Si en Haskell esto se usa como un ejemplo de libro de texto de HKT, ¿por qué se dice que Rust no tiene HKT? ¿Acaso la enumeración Maybe no se califica como un HKT?
2. ¿Debería decirse que Rust no es totalmente compatible con HKT?
3. ¿Cuál es la diferencia fundamental entre HKT y polimorfismo paramétrico?

Esta confusión continúa al mirar las funciones, puedo escribir una función paramétrica que toma un Maybe , y para mi entender un HKT como un argumento de función.

fn do_something<T>(input: Maybe<T>) {
    // implementation
}

de nuevo, en Haskell eso sería algo así como

do_something :: Maybe a -> ()
do_something :: Maybe a -> ()
do_something _ = ()

Lo que lleva a la cuarta pregunta.

4. ¿Dónde termina exactamente el soporte para los tipos de clase superior? ¿Cuál es el ejemplo mínimo para hacer que el sistema de tipos de Rust no pueda expresar HKT?

Preguntas relacionadas:

Pasé por muchas preguntas relacionadas con el tema (incluidos los enlaces que tienen a las publicaciones del blog, etc.) pero no pude encontrar una respuesta a mis preguntas principales (1 y 2).

1. En Haskell, ¿son los "tipos de tipo más alto" * los tipos realmente? ¿O simplemente denotan colecciones de tipos * concretos * y nada más?
2. Estructura genérica sobre un tipo genérico sin parámetro de tipo
3. Tipos más altos en Scala
4. ¿Qué tipos de problemas ayudan a resolver mejor el "polimorfismo de clase superior"?
5. Tipos de datos abstractos versus polimorfismo paramétrico en Haskell

Actualizar

Gracias por las muchas buenas respuestas que son muy detalladas y que han ayudado mucho. Decidí aceptar la respuesta de Andreas Rossberg ya que su explicación fue la que más me ayudó a encontrar el camino correcto. Especialmente la parte sobre terminología.

Estaba realmente encerrado en el ciclo de pensar que todo lo que es de tipo * -> * ... -> * es de clase superior . La explicación que subrayó la diferencia entre * -> * -> * y (* -> *) -> * fue crucial para mí.

Answer 1

Alguna terminología:

• El tipo * veces se llama tierra . Puedes considerarlo como una orden 0
• Cualquier tipo de formulario * -> * -> ... -> * con al menos una flecha es de primer orden .
• Un tipo de orden superior es uno que tiene una "flecha anidada a la izquierda", por ejemplo, (* -> *) -> * .

El orden es esencialmente la profundidad de anidación del lado izquierdo de las flechas, por ejemplo, (* -> *) -> * es de segundo orden, ((* -> *) -> *) -> * es de tercer orden, etc. . (FWIW, la misma noción se aplica a los tipos en sí mismos: una función de segundo orden es aquella cuyo tipo tiene, por ejemplo, la forma (A -> B) -> C )

Los tipos de tipo no terrestre (orden> 0) también se denominan constructores de tipo (y algunas publicaciones solo se refieren a tipos de tipo terrestre como "tipos"). Un tipo de orden superior (constructor) es aquel cuyo tipo es de orden superior (orden> 1).

En consecuencia, un tipo de tipo superior es el que toma un argumento de tipo no-fundamental. Eso requeriría variables de tipo de tipo no terrestre, que no se admiten en muchos idiomas. Ejemplos en Haskell:

type Ground = Int
type FirstOrder a = Maybe a  -- a is ground
type SecondOrder c = c Int   -- c is a first-order constructor
type ThirdOrder c = c Maybe  -- c is second-order

Los dos últimos son de clase superior.

Del mismo modo, el polimorfismo de tipo superior describe la presencia de valores polimórficos (paramétricamente) que se abstraen sobre tipos que no son fundamentales. Una vez más, pocos idiomas soportan eso. Ejemplo:

f : forall c. c Int -> c Int  -- c is a constructor

La afirmación de que Rust admite el polimorfismo paramétrico "en lugar" de los tipos de tipo superior no tiene sentido. Ambas son diferentes dimensiones de parametrización que se complementan entre sí. Y cuando combinas ambos tienes un polimorfismo de clase superior.

Answer 2

El polimorfismo paramétrico simplemente se refiere a la propiedad de que la función no puede hacer uso de ninguna característica particular de un tipo (o tipo) en su definición; Es una caja negra completa. El ejemplo estándar es length :: [a] -> Int , que solo funciona con la estructura de la lista, no con los valores particulares almacenados en la lista.

El ejemplo estándar de HKT es la clase Functor , donde fmap :: (a -> b) -> fa -> fb . A diferencia de la length , donde a tiene kind * , f tiene kind * -> * . fmap también muestra polimorfismo paramétrico, porque fmap no puede hacer uso de ninguna propiedad de a o b en su definición.

fmap muestra un polimorfismo ad hoc, ya que la definición se puede adaptar al tipo específico de constructor f para el que está definida. Es decir, hay definiciones separadas de fmap para f ~ [] , f ~ Maybe , etc. La diferencia es que f se "declara" como parte de la definición de typeclass, en lugar de ser parte de la definición de fmap . (De hecho, se agregaron clases de tipos para admitir cierto grado de polimorfismo ad hoc. Sin clases de tipo, solo existe el polimorfismo paramétrico. Puede escribir una función que admita un tipo concreto o cualquier tipo concreto, pero no una colección más pequeña entre ellas).

Answer 3

Un ejemplo simple de lo que Rust no puede hacer es algo como la clase Functor de Haskell.

class Functor f where
    fmap :: (a -> b) -> f a -> f b

-- a couple examples:
instance Functor Maybe where
    -- fmap :: (a -> b) -> Maybe a -> Maybe b
    fmap _ Nothing  = Nothing
    fmap f (Just x) = Just (f x)

instance Functor [] where
    -- fmap :: (a -> b) -> [a] -> [b]
    fmap _ []     = []
    fmap f (x:xs) = f x : fmap f xs

Tenga en cuenta que las instancias están definidas en el constructor de tipo, Maybe o [] , en lugar del tipo aplicado en su totalidad Maybe a o [a] .

Esto no es sólo un truco de salón. Tiene una fuerte interacción con el polimorfismo paramétrico. Dado que las variables de tipo a y b en el tipo fmap no están limitadas por la definición de clase, las instancias de Functor no pueden cambiar su comportamiento basándose en ellas. Esta es una propiedad increíblemente sólida para razonar sobre el código de los tipos, y de dónde proviene la fuerza del sistema de tipos de Haskell.

Tiene otra propiedad: puede escribir código que sea abstracto en variables de tipo de clase superior. Aquí hay un par de ejemplos:

focusFirst :: Functor f => (a -> f b) -> (a, c) -> f (b, c)
focusFirst f (a, c) = fmap (/x -> (x, c)) (f a)

focusSecond :: Functor f => (a -> f b) -> (c, a) -> f (c, b)
focusSecond f (c, a) = fmap (/x -> (c, x)) (f a)

Admito que esos tipos comienzan a parecer tonterías abstractas. Pero resultan ser realmente prácticos cuando tienes un par de ayudantes que aprovechan la abstracción de mayor clase.

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    -- fmap :: (a -> b) -> Identity a -> Identity b
    fmap f (Identity x) = Identity (f x)

newtype Const c b = Const { getConst :: c }

instance Functor (Const c) where
    -- fmap :: (a -> b) -> Const c a -> Const c b
    fmap _ (Const c) = Const c

set :: ((a -> Identity b) -> s -> Identity t) -> b -> s -> t
set f b s = runIdentity (f (/_ -> Identity b) s)

get :: ((a -> Const a b) -> s -> Const a t) -> s -> a
get f s = getConst (f (/x -> Const x) s)

(Si cometí algún error allí, ¿puede alguien simplemente corregirlos? Reimplemento el punto de inicio más básico de la lens desde la memoria sin un compilador).

Las funciones focusFirst y focusSecond se pueden pasar como el primer argumento para get o set , porque la variable de tipo f en sus tipos se puede unificar con los tipos más concretos en get y set . Ser capaz de abstraer sobre la variable de tipo de tipo más alto f permite que las funciones de una forma particular se puedan usar como definidores y captadores en tipos de datos arbitrarios. Esta es una de las dos ideas principales que llevaron a la biblioteca de lens . No podría existir sin este tipo de abstracción.

(Para lo que vale la pena, la otra idea clave es que la definición de lentes como una función que permite que la composición de las lentes sea una composición de función simple).

Así que no, hay más que simplemente poder aceptar una variable de tipo. La parte importante es poder usar variables de tipo que correspondan a constructores de tipo, en lugar de algún tipo concreto (si se desconoce).

Answer 4

Voy a resumirlo: un tipo de orden superior es solo una función de orden superior de nivel de tipo.

Pero toma un minuto

Considere los transformadores de monad :

newtype StateT s m a :: * -> (* -> *) -> * -> *

Aquí,

- s is the desired type of the state
- m is a functor, another monad that StateT will wrap
- a is the return type of an expression of type StateT s m

¿Cuál es el tipo de clase superior?

m :: (* -> *)

Porque toma un tipo de tipo * y devuelve un tipo de tipo * .

Es como una función en tipos, es decir, un tipo constructor de tipo

* -> *

En lenguajes como Java, no puedes hacer

class ClassExample<T, a> {
    T<a> function()
}

En Haskell T tendría kind *->* , pero un tipo de Java (es decir, class) no puede tener un parámetro de tipo de ese tipo, un tipo de tipo superior.

Además, si no lo sabe, en Haskell básico una expresión debe tener un tipo que tenga kind * , es decir, un "tipo concreto". Cualquier otro tipo como * -> * .

Por ejemplo, no puede crear una expresión de tipo Maybe . Tiene que ser tipos aplicados a un argumento como Maybe Int , Maybe String , etc. En otras palabras, constructores de tipos totalmente aplicados.