scala - metafora - ¿Cuándo son útiles los tipos de mayor nivel?

libro diario ejercicios resueltos pdf

Question

He estado haciendo dev en F # por un tiempo y me gusta. Sin embargo, una palabra de moda que sé que no existe en F # es de tipo de mayor nivel. He leído material sobre tipos de mayor nivel, y creo que entiendo su definición. No estoy seguro de por qué son útiles. ¿Puede alguien proporcionar algunos ejemplos de lo que los tipos de mayor nivel hacen más fácil en Scala o Haskell, que requieren soluciones en F #? También para estos ejemplos, ¿cuáles serían las soluciones sin tipos de alto grado (o viceversa en F #)? Tal vez estoy tan acostumbrado a trabajar a su alrededor que no noto la ausencia de esa característica.

(Creo) Obtengo que en lugar de myList |> List.map f o myList |> Seq.map f |> Seq.toList tipos de myList |> Seq.map f |> Seq.toList más altos te permiten simplemente escribir myList |> map f y devolverá una 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 me convierto a Seq todos modos y luego puedo convertir 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 mayor nivel realmente lo salven en pulsaciones de tecla o en seguridad tipo?

Answer 1

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

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

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

No sé F #, pero consideremos qué sucede si tratamos de expresar la abstracción de Functor en un lenguaje como Java o C #, con herencia y genéricos, pero no genéricos de alto nivel. 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 de 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 usa el método de map no puede invocar ningún método específico de subtipo en el resultado a menos que lo baje al tipo que realmente espera. Entonces tenemos dos problemas:

1. El sistema de tipo no nos permite expresar el invariante de que el método de map siempre devuelve la misma subclase de Functor que el receptor.
2. Por lo tanto, no existe una manera estática de seguridad de tipos para invocar un método que no sea de Functor en el resultado del map .

Hay otras formas más complicadas que puedes probar, pero ninguna de ellas realmente funciona. Por ejemplo, puede intentar aumentar el primer intento definiendo subtipos de Functor que restrinjan 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 a los implementadores de esas interfaces más estrechas que no devuelvan el tipo incorrecto de Functor del método del map , pero dado que no hay límite para la cantidad de implementaciones de Functor 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 restringirlo. Por lo tanto, 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 => ma -> (a -> mb) -> mb .)

Otro intento es usar genéricos recursivos para intentar que la interfaz restrinja el tipo de resultado del subtipo al subtipo mismo. 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 arcaica para su desarrollador de OOP común y corriente, diablos para su desarrollador funcional ordinario también) todavía no puede expresar la restricción de Functor 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 restringe que FB tenga la misma F que FA -que cuando declara un tipo List<A> implements Functor<List<A>, A> , el método de map aún puede devolver un NotAList<B> implements Functor<NotAList<B>, B> .

Prueba final, en Java, usando tipos sin procesar (contenedores sin paramétricos):

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

Aquí F se instanciará a tipos sin parametrizar como simplemente List o Map . Esto garantiza que una FunctorStrategy<List> solo puede devolver una 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 los 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 mayor nivel 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) Obtengo que en lugar de myList |> List.map f o myList |> Seq.map f |> Seq.toList tipos de myList |> Seq.map f |> Seq.toList más altos te permiten simplemente escribir myList |> map f y devolverá una 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 me convierto a Seq todos modos y luego puedo convertir lo que quiera después.

Hay muchos lenguajes que generalizan la idea de la función del map esta manera, modelándola como si, en el fondo, el mapeo se tratara de secuencias. Esta observación suya es en ese sentido: si tiene un tipo que admite la conversión Seq desde Seq , obtiene la operación de mapa "gratis" al volver a Seq.map .

En Haskell, sin embargo, la clase Functor es más general que eso; no está ligado a la noción de secuencias. Puede implementar fmap para tipos que no tienen un buen mapeo de secuencias, como acciones IO , 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" en realidad no está vinculado a las secuencias. Lo mejor es entender las leyes de fideicomiso:

(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 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 producir mapeando una vez.

Es por eso que quiere que fmap preserve el tipo, porque tan pronto como obtiene operaciones de map que producen un tipo de resultado diferente, se vuelve mucho, mucho más difícil hacer garantías como esta.

Answer 2

El ejemplo más utilizado de polimorfismo de tipo de mayor nivel en Haskell es la interfaz Monad . Functor y Applicative son de mayor nivel de la misma manera, por lo que mostraré Functor para 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 tenga valor. Puede identificar valores en esa firma tipo porque son argumentos ay resultados de una función. Entonces, las variables de tipo b son tipos que pueden tener valores. También lo son las expresiones de tipo fa y fb . Pero no f sí mismo. f es un ejemplo de una variable de tipo de mayor nivel. Dado que * es el tipo de tipos que pueden tener valores, f debe tener el tipo * -> * . Es decir, se necesita un tipo que pueda tener valores, porque sabemos por un examen previo que a y b deben tener valores. Y también sabemos que fa y fb deben tener valores, por lo que devuelve un tipo que debe tener valores.

Esto hace que la f utilizada en la definición de Functor una variable de tipo de mayor nivel.

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

Trabajar en tipos de mayor nivel 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 modifican otros tipos.

Answer 3

Entonces, el tipo de tipo es su tipo simple. Por ejemplo, Int tiene kind * que significa que es un tipo base y puede crearse una instancia por valores. Por alguna definición suelta de tipo de mayor nivel (y no estoy seguro de dónde dibuja F # la línea, así que vamos a incluirlo), 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 tipos List tiene kind * -> * que significa que debe pasarse un tipo concreto para dar como resultado un tipo concreto: List Int puede tener habitantes como [1,2,3] pero List no puede.

Voy a suponer que los beneficios de los contenedores polimórficos son obvios, pero existen tipos de 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 kind * -> * .

Sin embargo, podemos llevar esto más allá en Haskell al tener tipos con tipos incluso de orden superior. Por ejemplo, podríamos buscar un tipo con tipo (* -> *) -> * . Un ejemplo simple de esto podría ser Shape que intenta llenar un contenedor de tipo * -> * .

data Shape f = Shape (f ())

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

Esto es útil para caracterizar Traversable s 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 en 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 un Pair de Tree a y así podemos extraer esa pieza del tipo paramétricamente

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

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

Este constructor tipo TreeG tiene kind (* -> *) -> * -> * . Podemos usarlo para hacer interesantes otras variaciones como un RoseTree

type RoseTree a = TreeG [] a

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

O patológicos como 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 funtores". Si dejamos caer algunas capas de abstracción, podríamos considerarlo mejor como un pliegue, como sum :: [Int] -> Int . Las álgebras se parametrizan sobre el funtor y la portadora . El funtor tiene kind * -> * y el tipo de operador * por lo que en conjunto

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

tiene kind (* -> *) -> * -> * . Alg útil debido a su relación con los tipos de datos y esquemas de recursión construidos encima de 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 mayor calidad. A veces vemos funciones de ese tipo, como mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b ejemplo, mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b , pero creo que deberás profundizar en el tipo de prólogo o en la literatura dependiente. para ver ese nivel de complejidad en tipos.

Answer 4

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

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

En general, he descubierto que cuando la gente no ve la utilidad de functors / monads / whatevers, a menudo es porque están pensando en estas cosas de a una por vez . Las operaciones de Functor / mónada / etc realmente no agregan nada a una sola instancia (en lugar de llamar a bind, fmap, etc. Podría simplemente llamar a cualquier operación que use para implementar bind, fmap, etc.). Lo que realmente quieres para estas abstracciones es que puedas tener un código que funcione genéricamente con cualquier functor / mónada / etc.

En un contexto en el que se utiliza ampliamente dicho código genérico, esto significa que cada vez que escriba una nueva instancia de mónada, su tipo obtiene inmediatamente acceso a una gran cantidad 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 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 volver a utilizar el código que vi originalmente en términos de listas porque en realidad es monad-genérico.

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

Answer 5

Para una perspectiva más específica de .NET, escribí una publicación de blog sobre esto hace un tiempo. El quid de la cuestión es que, con tipos de mayor nivel, podría reutilizar los mismos bloques LINQ entre IEnumerables e IObservables , pero sin tipos de alto nivel esto es imposible.

Lo más cercano que se pudo obtener (lo descubrí después de publicar el blog) es hacer su propio IEnumerable<T> e IObservable<T> y los extendí a ambos desde un IMonad<T> . Esto le permitiría reutilizar sus bloques LINQ si se indican como IMonad<T> , pero ya no es seguro, ya que le permite mezclar y combinar IObservables e IEnumerables dentro del mismo bloque, lo que a pesar de que puede sonar intrigante para permite esto, básicamente obtendrías un comportamiento indefinido.

Escribí una publicación posterior sobre cómo Haskell hace esto fácil. (Un no-op, en realidad, restringir un bloque a cierto tipo de mónada requiere código, lo que permite la reutilización es el valor predeterminado).