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

88

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?

langosta
fuente
2
Muchas de las funciones de Control.Monad utilizan tipos superiores, por lo que es posible que desee buscar allí algunos ejemplos. En F #, las implementaciones tendrían que repetirse para cada tipo de mónada concreta.
Lee
1
@Lee, pero ¿no podrías simplemente crear una interfaz IMonad<T>y luego volver a convertirla en, por ejemplo, IEnumerable<int>o IObservable<int>cuando hayas terminado? ¿Es todo esto solo para evitar el casting?
langosta
4
Bueno, la transmisión no es segura, por lo que responde a su pregunta sobre la seguridad de tipos. Otro problema es cómo returnfuncionaría ya que realmente pertenece al tipo de mónada, no a una instancia en particular, por lo que no querrá ponerlo en la IMonadinterfaz en absoluto.
Lee
4
@Lee, sí, estaba pensando que tendrías que lanzar el resultado final después de la expresión, no es problema porque acabas de hacer la expresión para que conozcas el tipo. Pero parece que también tendrías que lanzar dentro de cada impl de bindaka, SelectManyetc. Lo que significa que alguien podría usar la API de binduna IObservablea otra IEnumerabley asumir que funcionaría, lo que sí, si ese es el caso y no hay forma de evitarlo. No estoy 100% seguro de que no haya forma de evitarlo.
langosta
5
Gran pregunta. Todavía tengo que ver un solo ejemplo práctico convincente de que esta característica del lenguaje sea útil en la vida real.
JD

Respuestas:

78

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.

J. Abrahamson
fuente
3
Revisaré y editaré el código en unos minutos, estoy en mi teléfono ahora mismo.
J. Abrahamson
12
@ J.Abrahamson +1 por una buena respuesta y tener la paciencia de escribir eso en su teléfono O_o
Daniel Gratzer
3
@lobsterism A TreeTreees simplemente patológico, pero de manera más práctica significa que tienes dos tipos diferentes de árboles entrelazados entre sí; llevar esa idea un poco más lejos puede darte algunas nociones muy poderosas de tipo seguro, como rojo estáticamente seguro / árboles negros y el pulcro y equilibrado tipo FingerTree.
J. Abrahamson
3
@JonHarrop Un ejemplo estándar del mundo real es la abstracción de mónadas, por ejemplo, con pilas de efectos estilo mtl. Sin embargo, es posible que no esté de acuerdo con que esto sea valioso para el mundo real. Creo que en general está claro que los lenguajes pueden existir con éxito sin HKT, por lo que cualquier ejemplo proporcionará algún tipo de abstracción que sea más sofisticada que otros lenguajes.
J. Abrahamson
2
Puede tener, por ejemplo, subconjuntos de efectos autorizados en varias mónadas y abstraer cualquier mónada que cumpla con esa especificación. Por ejemplo, las mónadas que crean instancias de "teletipo" que permite la lectura y escritura a nivel de caracteres pueden incluir tanto IO como una abstracción de tubería. Puede abstraer varias implementaciones asincrónicas como otro ejemplo. Sin HKT, limita cualquier tipo compuesto a partir de esa pieza genérica.
J. Abrahamson
64

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.

Luis Casillas
fuente
Así que me interesa tu última parte, ¿por qué es útil tener un fmapencendido Function acuando ya tiene una .operación? Entiendo por qué .tiene sentido ser la definición de la fmapoperación, pero no llego a donde alguna vez necesitarías usar en fmaplugar de .. Tal vez si pudiera dar un ejemplo en el que sea útil, me ayudaría a comprender.
langosta
1
Ah, entendido: puedes hacer un fn doublede un funtor, donde double [1, 2, 3]da [2, 4, 6]y double sinda un fn que es el doble del pecado. Puedo ver dónde si empiezas a pensar con esa mentalidad, cuando ejecutas un mapa en una matriz, esperas una matriz de regreso, no solo una secuencia, porque, bueno, estamos trabajando en matrices aquí.
langosta
@lobsterism: Hay algoritmos / técnicas que se basan en poder abstraer un Functory dejar que el cliente de la biblioteca lo elija. La respuesta de J. Abrahamson proporciona un ejemplo: los pliegues recursivos se pueden generalizar mediante el uso de functores. Otro ejemplo son las mónadas libres; puede pensar en ellos como una especie de biblioteca de implementación de intérpretes genéricos, donde el cliente proporciona el "conjunto de instrucciones" de forma arbitraria Functor.
Luis Casillas
3
Una respuesta técnicamente sólida, pero me deja preguntándome por qué alguien querría esto en la práctica. No me he encontrado buscando a Haskell's Functoro a SemiGroup. ¿Dónde utilizan más los programas reales esta función de lenguaje?
JD
28

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í).

Ben
fuente
9
Esta está más cerca de ser una respuesta útil que cualquiera de las otras respuestas que he leído hasta ahora, pero aún me gustaría ver una sola aplicación práctica donde los tipos más altos son útiles.
JD
"Para lo que realmente quieres estas abstracciones es para poder tener un código que funcione genéricamente con cualquier functor / mónada". F # obtuvo mónadas en forma de expresiones de cálculo hace 13 años, originalmente luciendo mónadas seq y async. Hoy F # disfruta de una tercera mónada, consulta. Con tan pocas mónadas que tienen tan poco en común, ¿por qué querrías abstraerlas?
JD
@JonHarrop Es claramente consciente de que otras personas han escrito código utilizando una gran cantidad de mónadas (y functores, flechas, etc.; los HKT no se tratan solo de mónadas) en lenguajes que admiten HKT y encuentran usos para abstraerlos. Y claramente no cree que nada de ese código tenga ningún uso práctico, y siente curiosidad por saber por qué otras personas se molestarían en escribirlo. ¿Qué tipo de información espera obtener al regresar para iniciar un debate sobre una publicación de hace 6 años que ya comentó hace 5 años?
Ben
"esperando ganar volviendo para iniciar un debate sobre un puesto de 6 años". Retrospectivo. Con el beneficio de la retrospectiva, ahora sabemos que las abstracciones de F # sobre las mónadas permanecen en gran parte sin usar. Por lo tanto, la capacidad de abstraer más de 3 cosas muy diferentes es poco convincente.
JD
@JonHarrop El punto de mi respuesta es que las mónadas individuales (o functores, etc.) no son realmente más útiles que una funcionalidad similar expresada sin una interfaz nómada, pero unificar muchas cosas dispares sí lo es. Me referiré a su experiencia en F #, pero si dice que solo tiene 3 mónadas individuales (en lugar de implementar una interfaz monádica para todos los conceptos que podrían tener una, como falla, estado, análisis, etc.), entonces sí, no es de extrañar que no obtenga muchos beneficios al unificar esas 3 cosas.
Ben
15

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).

Dax Fohl
fuente
2
Te daré un +1 por ser la única respuesta que menciona algo práctico, pero no creo que lo haya usado nunca IObservablesen código de producción.
JD
5
@JonHarrop Esto parece falso. En F # todos los eventos son IObservable, y usa eventos en el capítulo WinForms de su propio libro.
Dax Fohl
1
Microsoft me pagó para escribir ese libro y me pidió que cubriera esa característica. No recuerdo haber usado eventos en el código de producción, pero miraré.
JD
La reutilización entre IQueryable e IEnumerable también sería posible, supongo
KolA
Cuatro años después y terminé de buscar: sacamos Rx de producción.
JD
13

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.

Carl
fuente
4
Otra gran explicación técnica de qué son los tipos superiores me deja preguntándome para qué son útiles. ¿Dónde ha aprovechado esto en código real?
JD