¿Cuándo son útiles los tipos de tipo superior?

He estado haciendo desarrollo en F # por un tiempo y me gusta. Sin embargo, una palabra de moda que sé que no existe en F # es tipos de tipo superior. He leído material sobre tipos de clase alta y creo que entiendo su definición. No estoy seguro de por qué son útiles. ¿Alguien puede proporcionar algunos ejemplos de lo que los tipos de tipo superior facilitan en Scala o Haskell, que requieren soluciones en F #? También para estos ejemplos, ¿cuáles serían las soluciones alternativas sin tipos de tipo superior (o viceversa en F #)? Tal vez estoy tan acostumbrado a solucionarlo que no me doy cuenta de la ausencia de esa función.

(Creo) Entiendo que en lugar de myList |> List.map fo myList |> Seq.map f |> Seq.toListtipos de kinded superiores le permiten simplemente escribir myList |> map fy 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 de Seqtodos modos y luego puedo convertir a lo que quiera después. De nuevo, tal vez estoy demasiado acostumbrado a solucionarlo. Pero, ¿hay algún ejemplo en el que los tipos de tipo superior realmente le ahorren en pulsaciones de teclas o en seguridad de tipos?

Entonces, el tipo de tipo es su tipo simple. Por ejemplo, Inttiene kind, lo *que significa que es un tipo base y se puede instanciar mediante valores. Según una definición imprecisa de tipo de tipo superior (y no estoy seguro de dónde F # dibuja la línea, así que incluyémosla ), los contenedores polimórficos son un gran ejemplo de un tipo de tipo superior.

data List a = Cons a (List a) | Nil

El constructor de Listtipos tiene tipo, lo * -> *que significa que se debe pasar un tipo concreto para que resulte en un tipo concreto: List Intpuede tener habitantes como [1,2,3]pero él Listmismo no.

Voy a suponer que los beneficios de los contenedores polimórficos son obvios, pero * -> *existen tipos más útiles que solo los contenedores. Por ejemplo, las relaciones

data Rel a = Rel (a -> a -> Bool)

o analizadores

data Parser a = Parser (String -> [(a, String)])

Ambos también tienen amabilidad * -> *.

Sin embargo, podemos llevar esto más lejos en Haskell al tener tipos con tipos de orden incluso superior. Por ejemplo, podríamos buscar un tipo con kind (* -> *) -> *. Un ejemplo simple de esto podría ser el Shapeque intenta llenar un recipiente de algún tipo * -> *.

data Shape f = Shape (f ())

[(), (), ()] :: Shape List

Esto es útil para caracterizar Traversables en Haskell, por ejemplo, ya que siempre se pueden dividir en su forma y contenido.

split :: Traversable t => t a -> (Shape t, [a])

Como otro ejemplo, consideremos un árbol que está parametrizado según el tipo de rama que tiene. Por ejemplo, un árbol normal podría ser

data Tree a = Branch (Tree a) a (Tree a) | Leaf

Pero podemos ver que el tipo de rama contiene una Pairde Tree as, por lo que podemos extraer esa pieza del tipo de forma paramétrica

data TreeG f a = Branch a (f (TreeG f a)) | Leaf

data Pair a = Pair a a
type Tree a = TreeG Pair a

Este TreeGconstructor de tipos tiene kind (* -> *) -> * -> *. Podemos usarlo para hacer otras variaciones interesantes como unRoseTree

type RoseTree a = TreeG [] a

rose :: RoseTree Int
rose = Branch 3 [Branch 2 [Leaf, Leaf], Leaf, Branch 4 [Branch 4 []]]

O patológicos como un MaybeTree

data Empty a = Empty
type MaybeTree a = TreeG Empty a

nothing :: MaybeTree a
nothing = Leaf

just :: a -> MaybeTree a
just a = Branch a Empty

O un TreeTree

type TreeTree a = TreeG Tree a

treetree :: TreeTree Int
treetree = Branch 3 (Branch Leaf (Pair Leaf Leaf))

Otro lugar donde esto aparece es en "álgebras de functores". Si dejamos caer algunas capas de abstracción, esto podría considerarse mejor como un pliegue, como sum :: [Int] -> Int. Las álgebras se parametrizan sobre el functor y el portador . El functor tiene amabilidad * -> *y el portador es *tan bueno

data Alg f a = Alg (f a -> a)

tiene amabilidad (* -> *) -> * -> *. Algútil debido a su relación con los tipos de datos y los esquemas de recursividad construidos sobre ellos.

-- | The "single-layer of an expression" functor has kind `(* -> *)`
data ExpF x = Lit Int
            | Add x x
            | Sub x x
            | Mult x x

-- | The fixed point of a functor has kind `(* -> *) -> *`
data Fix f = Fix (f (Fix f))

type Exp = Fix ExpF

exp :: Exp
exp = Fix (Add (Fix (Lit 3)) (Fix (Lit 4))) -- 3 + 4

fold :: Functor f => Alg f a -> Fix f -> a
fold (Alg phi) (Fix f) = phi (fmap (fold (Alg phi)) f)

Finalmente, aunque son teóricamente posibles, nunca he visto un constructor de tipos de tipo aún superior. A veces vemos funciones de ese tipo como mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b, pero creo que tendrás que profundizar en el prólogo de tipos o en la literatura escrita de forma dependiente para ver ese nivel de complejidad en los tipos.

Considere la Functorclase de tipo en Haskell, donde fes una variable de tipo de tipo superior:

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 fdesde aa b, pero lo deja fcomo estaba. Entonces, si usa fmapsobre una lista, obtiene una lista, si lo usa sobre un analizador, obtiene un analizador, y así sucesivamente. Y estas son garantías estáticas en tiempo de compilación.

No sé F #, pero consideremos qué sucede si tratamos de expresar la Functorabstracción en un lenguaje como Java o C #, con herencia y genéricos, pero sin genéricos de tipo 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 método FunnyList<A> implements Functor<A>cuyo mapmétodo devuelva un tipo diferente de colección, o incluso algo más que no sea una colección en absoluto pero que siga siendo un Functor. Además, cuando usa el mapmétodo, no puede invocar ningún método específico de subtipo en el resultado a menos que lo rebaje al tipo que realmente espera. Entonces tenemos dos problemas:

1. El sistema de tipos no nos permite expresar el invariante de que el mapmétodo siempre devuelve la misma Functorsubclase que el receptor.
2. Por lo tanto, no existe una manera estáticamente segura de invocar un Functormétodo no en el resultado de map.

Hay otras formas más complicadas de probar, pero ninguna de ellas funciona realmente. Por ejemplo, puede intentar aumentar el primer intento definiendo subtipos Functorque 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 evitar que los implementadores de esas interfaces más estrechas devuelvan el tipo incorrecto de Functordel mapmétodo, pero como no hay límite para la cantidad de Functorimplementaciones que puede tener, no hay límite para la cantidad de interfaces más estrechas que necesitará.

( EDITAR: Y tenga en cuenta que esto solo funciona porque Functor<B>aparece como el tipo de resultado, por lo que las interfaces secundarias pueden limitarlo. Entonces, AFAIK, no podemos limitar 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 más 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 misteriosa para su desarrollador OOP común y corriente, diablos también para su desarrollador funcional común y corriente) tampoco puede expresar la Functorrestricción deseada :

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 se limita FBa tener lo mismo Fque FA, de modo que cuando declaras un tipo List<A> implements Functor<List<A>, A>, el mapmétodo aún puede devolver un NotAList<B> implements Functor<NotAList<B>, B>.

Prueba final, en Java, usando tipos sin formato (contenedores no parametrizados):

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

Aquí se Fcrearán instancias en tipos no parametrizados como solo Listo Map. Esto garantiza que a FunctorStrategy<List>solo puede devolver a, Listpero ha abandonado el uso de variables de tipo para rastrear los tipos de elementos de las listas.

El meollo del problema aquí es que lenguajes como Java y C # no permiten que los parámetros de tipo tengan parámetros. En Java, si Tes una variable de tipo, puede escribir Ty List<T>, pero no T<String>. Los tipos de tipo superior eliminan esta restricción, por lo que podría 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 fo myList |> Seq.map f |> Seq.toListtipos de kinded superiores le permiten simplemente escribir myList |> map fy 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 de Seqtodos modos y luego puedo convertir a lo que quiera después.

Hay muchos lenguajes que generalizan la idea de la mapfunción 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 desde y hacia Seq, obtiene la operación del mapa "gratis" mediante la reutilización Seq.map.

En Haskell, sin embargo, la Functorclase es más general que eso; no está ligado a la noción de secuencias. Puede implementar fmappara tipos que no tienen una buena asignación a secuencias, como IOacciones, 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 comprender las leyes de functor:

(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 de identidad / noop es lo mismo que no hacer nada.
2. La segunda ley dice que cualquier resultado que pueda producir mapeando dos veces, también puede producirlo mapeando una vez.

Ésta es la razón por la que desea fmapconservar el tipo, porque tan pronto como obtenga mapoperaciones que produzcan un tipo de resultado diferente, se vuelve mucho, mucho más difícil ofrecer garantías como esta.

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

Por lo general, no necesita tipos de tipo superior para implementar una mónada o un funtor (o un funtor aplicativo, una flecha o ...) en particular. Pero hacerlo es principalmente perder el punto.

En general, he descubierto que cuando la gente no ve la utilidad de los functores / mónadas / lo que sea, a menudo es porque están pensando en estas cosas una a la vez . Las operaciones de functor / monad / etc realmente no agregan nada a ninguna instancia (en lugar de llamar a bind, fmap, etc., podría simplemente llamar a las operaciones que usé para implementar bind, fmap, etc.). Para lo que realmente desea estas abstracciones es para poder tener un código que funcione genéricamente con cualquier functor / mónada / 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 una gran cantidad de operaciones útiles que ya se han escrito para usted . Ese es el punto de ver mónadas (y functores, y ...) en todas partes; no para que pueda usar en bindlugar de concate mapimplementar myFunkyListOperation(lo que no me gana nada en sí mismo), sino para que cuando lo necesite myFunkyParserOperationy myFunkyIOOperationpueda reutilizar el código que vi originalmente en términos de listas porque en realidad es monad-genérico .

Pero para abstraer un tipo parametrizado como una mónada con seguridad de tipos , necesita tipos de tipo superior (como se explica en otras respuestas aquí).

Para una perspectiva más específica de .NET, escribí una publicación de blog sobre esto hace un tiempo. El quid de esto es que, con tipos de tipo superior, podría potencialmente reutilizar los mismos bloques LINQ entre IEnumerablesy IObservables, pero sin tipos de tipo superior esto es imposible.

Lo más cerca que se puede conseguir (que me di cuenta después de publicar el blog) es para hacer su propia IEnumerable<T>y IObservable<T>, y los dos se extendía desde una IMonad<T>. Esto le permitiría reutilizar sus bloques LINQ si están indicados IMonad<T>, pero ya no es seguro para los tipos porque le permite mezclar y combinar IObservablesy IEnumerablesdentro del mismo bloque, lo que si bien puede sonar intrigante habilitar esto, debería Básicamente, obtengo un comportamiento indefinido.

Escribí una publicación posterior sobre cómo Haskell hace esto fácil. (Una operación no operativa, en realidad: 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 de tipo superior en Haskell es la Monadinterfaz. Functory Applicativeson de clase superior de la misma manera, por lo que mostraré Functorpara mostrar algo conciso.

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

Ahora, examine esa definición y observe cómo fse usa la variable de tipo . Verá que fno puede significar un tipo que tenga valor. Puede identificar valores en esa firma de tipo porque son argumentos y resultados de funciones. Entonces, las variables de tipo ay bson tipos que pueden tener valores. También lo son las expresiones de tipo f ay f b. Pero no en fsí mismo. fes un ejemplo de una variable de tipo superior. Dado que *es el tipo de tipos que pueden tener valores, fdebe tener el tipo * -> *. Es decir, toma un tipo que puede tener valores, porque sabemos por examen previo que ay bdebe tener valores. Y también sabemos eso f ayf b debe tener valores, por lo que devuelve un tipo que debe tener valores.

Esto hace que se fuse en la definición de Functoruna variable de tipo superior.

Las interfaces Applicativey Monadagregan más, pero son compatibles. Esto significa que también trabajan en variables de tipo con kind * -> *.

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