¿Cuándo son útiles los tipos de kinded superiores?

Considere la clase de tipo Functor en Haskell, donde f es una variable de tipo de mayor kinded:

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

Lo que dice esta firma de tipo es que fmap cambia el parámetro de tipo de un f de a a b, pero deja f como estaba. Así que si usas fmap sobre una lista obtienes una lista, si la usas sobre un analizador obtienes un analizador, y así sucesivamente. Y estas son static, garantías en tiempo de compilación.

No lo sé F#, pero vamos a considerar lo que sucede si tratamos de exprese la abstracción Functor en un lenguaje como Java o C#, con herencia y genéricos, pero no genéricos de clase superior. Primer intento:

interface Functor<A> {
    Functor<B> map(Function<A, B> f);
}

El problema con este primer intento es que una implementación de la interfaz puede devolver cualquier clase que implemente Functor. Alguien podría escribir un FunnyList<A> implements Functor<A> cuyo método map devuelve un tipo diferente de colección, o incluso algo más que no es una colección en absoluto, pero sigue siendo un Functor. Además, cuando se utiliza el map método no puedes invocar ningún método específico de subtipo en el resultado a menos que lo bajes al tipo que realmente esperas. Así que tenemos dos problemas:

1. El sistema de tipos no nos permite expresar el invariante de que el método map siempre devuelve la misma subclase Functor que el receptor.
2. Por lo tanto, no hay una manera estáticamente segura de invocar un método no-Functor sobre el resultado de map.

Hay otras formas más complicadas de puedo intentarlo, pero ninguno de ellos realmente funciona. Por ejemplo, podría intentar aumentar el primer intento definiendo subtipos de Functor que restringen el tipo de resultado:

interface Collection<A> extends Functor<A> {
    Collection<B> map(Function<A, B> f);
}

interface List<A> extends Collection<A> {
    List<B> map(Function<A, B> f);
}

interface Set<A> extends Collection<A> {
    Set<B> map(Function<A, B> f);
}

interface Parser<A> extends Functor<A> {
    Parser<B> map(Function<A, B> f);
}

// …

Esto ayuda a prohibir que los implementadores de esas interfaces más estrechas devuelvan el tipo incorrecto de Functor del método map, pero como no hay límite para cuántas implementaciones Functor puede tener, no hay límite para cuántas interfaces más estrechas necesitará.

(EDITAR: Y tenga en cuenta que esto solo funciona porque Functor<B> aparece como el tipo de resultado, por lo que las interfaces hijo pueden reducirlo. Así que AFAIK no podemos restringir ambos usos de Monad<B> en la siguiente interfaz:

interface Monad<A> {
    <B> Monad<B> flatMap(Function<? super A, ? extends Monad<? extends B>> f);
}

En Haskell, con variables de tipo de rango superior, esto es (>>=) :: Monad m => m a -> (a -> m b) -> m b.)

Otro intento es usar genéricos recursivos para intentar que la interfaz restrinja el tipo de resultado del subtipo al subtipo en sí. Ejemplo de juguete:

/**
 * A semigroup is a type with a binary associative operation.  Law:
 *
 * > x.append(y).append(z) = x.append(y.append(z))
 */
interface Semigroup<T extends Semigroup<T>> {
    T append(T arg);
}

class Foo implements Semigroup<Foo> {
    // Since this implements Semigroup<Foo>, now this method must accept 
    // a Foo argument and return a Foo result. 
    Foo append(Foo arg);
}

class Bar implements Semigroup<Bar> {
    // Any of these is a compilation error:

    Semigroup<Bar> append(Semigroup<Bar> arg);

    Semigroup<Foo> append(Bar arg);

    Semigroup append(Bar arg);

    Foo append(Bar arg);

}

Pero este tipo de técnica (que es bastante arcana para su desarrollador de OOP run-of-the-mill, heck a su desarrollador funcional run-of-the-mill también) todavía no puede expresar la restricción deseada Functor tampoco:

interface Functor<FA extends Functor<FA, A>, A> {
    <FB extends Functor<FB, B>, B> FB map(Function<A, B> f);
}

El problema aquí es que esto no restringe FB para tener el mismo F que FA-de modo que cuando se declara un tipo List<A> implements Functor<List<A>, A>, el método map puede todavía devolver un NotAList<B> implements Functor<NotAList<B>, B>.

Último intento, en Java, usando tipos raw (contenedores sin procesar):

interface FunctorStrategy<F> {
    F map(Function f, F arg);
} 

Aquí F se instanciará a unparametrized tipos como solo List o Map. Esto garantiza que un FunctorStrategy<List> solo puede devolver un List, pero ha abandonado el uso de variables de tipo para rastrear los tipos de elementos de las listas.

El corazón del problema aquí es que lenguajes como Java y C# no permiten que los parámetros de tipo tengan parámetros. En Java, si T es una variable de tipo, puede escribir T y List<T>, pero no T<String>. Los tipos de clase superior eliminan esta restricción, para que pueda tener algo como esto (no completamente pensado):

interface Functor<F, A> {
    <B> F<B> map(Function<A, B> f);
}

class List<A> implements Functor<List, A> {

    // Since F := List, F<B> := List<B>
    <B> List<B> map(Function<A, B> f) {
        // ...
    }

}

Y abordando este bit en particular:

(Creo) entiendo que en lugar de myList |> List.map f o myList |> Seq.map f |> Seq.toList los tipos más altos le permiten simplemente escribir myList |> map f y devolverá un List. Eso es genial (suponiendo que sea correcto), pero parece un poco mezquino? (¿Y no podría hacerse simplemente permitiendo la sobrecarga de funciones?) Normalmente convierto a Seq de todos modos y luego puedo convertir a lo que quiera después.

Hay muchos idiomas que generalizan la idea de la función map de esta manera, modelándola como si, en el fondo, el mapeo se tratara de secuencias. Esta observación suya está en ese espíritu: si tiene un tipo que admite la conversión hacia y desde Seq, obtiene la operación de mapa "gratis" reutilizando Seq.map.

En Haskell, sin embargo, la clase Functor es más general que eso; no está ligada a la noción de secuencias. Puede implementar fmap para tipos que no tienen una buena asignación a secuencias, como IO acciones, combinadores de analizadores, funciones, etc.:

instance Functor IO where
    fmap f action =
        do x <- action
           return (f x)

 -- This declaration is just to make things easier to read for non-Haskellers 
newtype Function a b = Function (a -> b)

instance Functor (Function a) where
    fmap f (Function g) = Function (f . g)  -- `.` is function composition

El concepto de "mapeo" realmente no está ligado a secuencias. Es mejor entender las leyes funtor:

(1) fmap id xs == xs
(2) fmap f (fmap g xs) = fmap (f . g) xs

Muy informalmente:

1. La primera ley dice que mapear con una función identity/noop es lo mismo que no hacer nada.
2. La segunda ley dice que cualquier resultado que se puede producir mapeando dos veces, también se puede producir mapeando una vez.

Esta es la razón por la que desea fmap para preservar la type-porque tan pronto como obtienes map operaciones que producen un tipo de resultado diferente, se vuelve mucho, mucho más difícil hacer garantías como esta.

No quiero repetir información en algunas respuestas excelentes ya aquí, pero hay un punto clave que me gustaría agregar.

Por lo general, no se necesitan tipos de mayor kinded para implementar una mónada en particular, o functor (o functor aplicativo, o flecha, o ...). Pero hacerlo es sobre todo perder el punto.

En general, he encontrado que cuando la gente no ve la utilidad de los funtores/mónadas/lo que sea, a menudo es porque están pensando en estas cosas una a la vez. Las operaciones Functor/monad/etc realmente no agregan nada a ninguna instancia (en lugar de llamar a bind, fmap, etc, podría llamar a cualquier operación que usara para implementar bind, fmap, etc). Para lo que realmente quieres estas abstracciones es para que puedas tener código que funcione genéricamente con cualquier functor/monad/etc.

En un contexto donde dicho código genérico se usa ampliamente, esto significa que cada vez que escribe una nueva instancia de mónada, su tipo obtiene acceso inmediatamente a un gran número de operaciones útiles que ya se han escrito para usted. Ese es el punto de ver mónadas (y funtores, y ...) en todas partes; no para que pueda usar bind en lugar de concat y map para implementar myFunkyListOperation (que no me gana nada en sí mismo), sino para que cuando necesite myFunkyParserOperation y myFunkyIOOperation pueda reutilizar el código que originalmente vi en términos de listas porque en realidad es monada-genérica.

Pero abstraer a través de un tipo parametrizado como una mónada con tipo seguridad, necesita tipos de mayor calidad (como se explica en otras respuestas aquí).

Para una perspectiva más específica de.NET, escribí una entrada de blog sobre esto hace un tiempo. El quid de esto es, con tipos de mayor kinded, que potencialmente podría reutilizar los mismos bloques LINQ entre IEnumerables y IObservables, pero sin tipos de mayor kinded esto es imposible.

Lo más cercano que podrías conseguir (me di cuenta después de publicar el blog) es hacer tu propio IEnumerable<T> y IObservable<T> y extenderlos ambos desde un IMonad<T>. Esto le permitiría reutilizar sus bloques LINQ si se denotan IMonad<T>, pero entonces ya no es typesafe porque le permite mezclar y combinar IObservables y IEnumerables dentro del mismo bloque, lo que si bien puede sonar intrigante para habilitar esto, básicamente solo obtendría un comportamiento indefinido.

Escribí un post posterior sobre cómo Haskell hace esto fácil. (Un no-op, realmente restricting restringir un bloque a un cierto tipo de mónada requiere código; habilitar la reutilización es el valor predeterminado).

El ejemplo más utilizado de polimorfismo de tipo superior en Haskell es la interfaz Monad. Functor y Applicative son de clase superior de la misma manera, así que voy a mostrar Functor con el fin de mostrar algo conciso.

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

Ahora, examine esa definición, mirando cómo se usa la variable de tipo f. Verás que f no puede significar un tipo que tiene valor. Puede identificar valores en esa firma de tipo porque son argumentos y resultados de una función. Así que las variables de tipo a y b son tipos que pueden tener valores. También lo son las expresiones de tipo f a y f b. Pero no f en sí. f es un ejemplo de una variable de tipo de kinded superior. Dado que * es el tipo de tipos que pueden tener valores, f debe tener el tipo * -> *. Es decir, toma un tipo que puede tener valores, porque sabemos por el examen anterior que a y b deben tener valores. Y también sabemos que f a y f b deben tener valores, por lo que devuelve un tipo que debe tener valor.

Esto hace que el f utilizado en la definición de Functor una variable de tipo de mayor kinded.

Las interfaces Applicative y Monad añaden más, pero son compatibles. Esto significa que trabajan en variables de tipo con kind * -> * también.

Trabajar en tipos de tipo superior introduce un nivel adicional de abstracción: no se limita a crear abstracciones sobre tipos básicos. También puede crear abstracciones sobre tipos que modifiquen otros tipos.