Quando os tipos de tipo superior são úteis?

Tenho feito desenvolvimento em F # há um tempo e gosto disso. No entanto, um chavão que eu sei que não existe no F # é tipos de tipo superior. Eu li material sobre tipos de classe superior e acho que entendo sua definição. Só não sei por que eles são úteis. Alguém pode fornecer alguns exemplos de quais tipos de tipo superior facilitam em Scala ou Haskell, que requerem soluções alternativas em F #? Também para esses exemplos, quais seriam as soluções alternativas sem tipos de tipo superior (ou vice-versa em F #)? Talvez eu esteja tão acostumado a trabalhar com isso que não percebo a ausência desse recurso.

(Eu acho) Eu entendo que em vez de myList |> List.map fou myList |> Seq.map f |> Seq.toListtipos de tipo superior permitem que você simplesmente escreva myList |> map fe ele retornará um List. Isso é ótimo (presumindo que esteja correto), mas parece meio mesquinho? (E isso não poderia ser feito simplesmente permitindo a sobrecarga de funções?) Normalmente, eu converto para de Seqqualquer maneira e, em seguida, posso converter para o que quiser. Novamente, talvez eu esteja acostumado a trabalhar com isso. Mas há algum exemplo em que tipos de tipo superior realmente salvem você tanto no pressionamento de teclas quanto na segurança de digitação?

Portanto, o tipo de um tipo é o seu tipo simples. Por exemplo, Inttem tipo, o *que significa que é um tipo base e pode ser instanciado por valores. Por alguma definição vaga de tipo de tipo superior (e não tenho certeza de onde F # traça a linha, então vamos apenas incluí-lo) os contêineres polimórficos são um ótimo exemplo de tipo de tipo superior.

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

O construtor de Listtipo tem tipo, o * -> *que significa que deve ser passado um tipo concreto para resultar em um tipo concreto: List Intpode ter habitantes semelhantes, [1,2,3]mas Listele próprio não pode.

Vou supor que os benefícios dos recipientes polimórficos são óbvios, mas * -> *existem tipos de tipo mais úteis do que apenas os recipientes. Por exemplo, as relações

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

ou analisadores

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

ambos também têm espécie * -> *.

Podemos levar isso mais longe em Haskell, no entanto, tendo tipos com tipos de ordem ainda mais alta. Por exemplo, podemos procurar um tipo com tipo (* -> *) -> *. Um exemplo simples disso pode ser Shapetentar encher um recipiente desse tipo * -> *.

data Shape f = Shape (f ())

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

Isso é útil para caracterizar Traversables em Haskell, por exemplo, pois eles sempre podem ser divididos em sua forma e conteúdo.

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

Como outro exemplo, vamos considerar uma árvore que está parametrizada no tipo de branch que possui. Por exemplo, uma árvore normal pode ser

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

Mas podemos ver que o tipo de branch contém a Pairde Tree as e, portanto, podemos extrair essa parte do tipo parametricamente

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

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

Este TreeGconstrutor de tipo tem tipo (* -> *) -> * -> *. Podemos usá-lo para fazer outras variações interessantes, como umRoseTree

type RoseTree a = TreeG [] a

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

Ou patológicos como um 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

Ou um TreeTree

type TreeTree a = TreeG Tree a

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

Outro lugar onde isso aparece é em "álgebras de functores". Se eliminarmos algumas camadas de abstração, isso pode ser melhor considerado como uma dobra, como sum :: [Int] -> Int. As álgebras são parametrizadas no functor e na portadora . O functor tem tipo * -> *e o tipo de portadora, de *modo completo

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

tem tipo (* -> *) -> * -> *. Algútil por causa de sua relação com tipos de dados e esquemas de recursão construídos sobre eles.

-- | 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, embora sejam teoricamente possíveis, nunca vi um construtor de tipo ainda mais alto. Às vezes vemos funções desse tipo, como mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b, mas acho que você terá que cavar no prólogo de tipos ou na literatura com tipos dependentes para ver esse nível de complexidade nos tipos.

Considere a Functorclasse de tipo em Haskell, onde fé uma variável de tipo de tipo superior:

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

O que essa assinatura de tipo diz é que fmap muda o parâmetro de tipo de fde apara b, mas deixa fcomo estava. Portanto, se você usar fmapsobre uma lista, obterá uma lista; se usá-la sobre um analisador, obterá um analisador, e assim por diante. E essas são garantias estáticas em tempo de compilação.

Não sei F #, mas vamos considerar o que acontece se tentarmos expressar a Functorabstração em uma linguagem como Java ou C #, com herança e genéricos, mas sem genéricos de tipo superior. Primeira tentativa:

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

O problema com essa primeira tentativa é que uma implementação da interface pode retornar qualquer classe que implemente Functor. Alguém poderia escrever um FunnyList<A> implements Functor<A>cujo mapmétodo retorne um tipo diferente de coleção, ou mesmo algo que não seja uma coleção, mas ainda seja um Functor. Além disso, ao usar o mapmétodo, você não pode invocar nenhum método específico de subtipo no resultado, a menos que seja reduzido ao tipo que você realmente espera. Portanto, temos dois problemas:

1. O sistema de tipo não nos permite expressar a invariante de que o mapmétodo sempre retorna a mesma Functorsubclasse que o receptor.
2. Portanto, não há uma maneira estaticamente segura de invocar um Functormétodo não relacionado ao resultado de map.

Existem outras maneiras mais complicadas que você pode tentar, mas nenhuma delas realmente funciona. Por exemplo, você pode tentar aumentar na primeira tentativa, definindo subtipos Functorque restringem o 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);
}

// …

Isso ajuda a impedir que os implementadores dessas interfaces mais estreitas retornem o tipo errado de Functordo mapmétodo, mas como não há limite para quantas Functorimplementações você pode ter, não há limite para quantas interfaces mais estreitas você precisará.

( EDITAR: E observe que isso só funciona porque Functor<B>aparece como o tipo de resultado e, portanto, as interfaces filhas podem restringi-lo. Portanto, não podemos restringir os dois usos de Monad<B>na seguinte interface: AFAIK :

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

Em Haskell, com variáveis ​​do tipo de classificação superior, isso é (>>=) :: Monad m => m a -> (a -> m b) -> m b.)

Outra tentativa é usar genéricos recursivos para tentar fazer com que a interface restrinja o tipo de resultado do subtipo ao próprio subtipo. Exemplo de brinquedo:

/**
 * 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);

}

Mas esse tipo de técnica (que é bastante misteriosa para o seu desenvolvedor OOP comum, mas para o seu desenvolvedor funcional comum também) ainda não consegue expressar a Functorrestrição desejada :

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

O problema aqui é que isso não se restringe FBa ter o mesmo Fque FA- então, quando você declara um tipo List<A> implements Functor<List<A>, A>, o mapmétodo ainda pode retornar a NotAList<B> implements Functor<NotAList<B>, B>.

Tentativa final, em Java, usando tipos brutos (contêineres não parametrizados):

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

Aqui Fserá instanciado para tipos não parametrizados como apenas Listou Map. Isso garante que a FunctorStrategy<List>só possa retornar a List- mas você abandonou o uso de variáveis ​​de tipo para rastrear os tipos de elemento das listas.

O cerne do problema aqui é que linguagens como Java e C # não permitem que parâmetros de tipo tenham parâmetros. Em Java, se Tfor uma variável de tipo, você pode escrever Te List<T>, mas não T<String>. Os tipos de tipo superior removem essa restrição, de modo que você poderia ter algo assim (não totalmente 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) {
        // ...
    }

}

E abordando este bit em particular:

(Eu acho) Eu entendo que em vez de myList |> List.map fou myList |> Seq.map f |> Seq.toListtipos de tipo superior permitem que você simplesmente escreva myList |> map fe ele retornará um List. Isso é ótimo (presumindo que esteja correto), mas parece meio mesquinho? (E isso não poderia ser feito simplesmente permitindo a sobrecarga de funções?) Normalmente, eu converto para de Seqqualquer maneira e, em seguida, posso converter para o que quiser.

Existem muitas linguagens que generalizam a ideia da mapfunção dessa forma, modelando-a como se, no fundo, o mapeamento fosse sobre sequências. Esta sua observação segue esse espírito: se você tem um tipo que suporta a conversão de e para Seq, você obtém a operação do mapa "gratuitamente" ao reutilizar Seq.map.

Em Haskell, entretanto, a Functorclasse é mais geral do que isso; não está vinculado à noção de sequências. Você pode implementar fmappara tipos que não têm um bom mapeamento para sequências, como IOações, combinadores de analisador, funções, 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

O conceito de "mapeamento" realmente não está vinculado a sequências. É melhor entender as leis do functor:

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

Muito informalmente:

1. A primeira lei diz que mapear com uma função identidade / noop é o mesmo que não fazer nada.
2. A segunda lei diz que qualquer resultado que você pode produzir mapeando duas vezes, você também pode produzir mapeando uma vez.

É por isso que você deseja fmappreservar o tipo - porque assim que você obtém mapoperações que produzem um tipo de resultado diferente, se torna muito, muito mais difícil fazer garantias como essa.

Não quero repetir informações em algumas respostas excelentes já aqui, mas há um ponto-chave que gostaria de acrescentar.

Você geralmente não precisa de tipos de tipo superior para implementar qualquer mônada ou functor em particular (ou functor aplicativo, ou seta, ou ...). Mas fazer isso é basicamente perder o ponto.

Em geral, descobri que quando as pessoas não veem a utilidade de functores / mônadas / sei lá o quê, geralmente é porque estão pensando nessas coisas uma de cada vez . As operações Functor / monad / etc realmente não adicionam nada a qualquer instância (em vez de chamar bind, fmap, etc, eu poderia apenas chamar quaisquer operações que usei para implementar bind, fmap, etc). O que você realmente quer essas abstrações é para que você possa ter um código que funcione genericamente com qualquer functor / monad / etc.

Em um contexto em que esse código genérico é amplamente usado, isso significa que sempre que você escreve uma nova instância de mônada, seu tipo imediatamente ganha acesso a um grande número de operações úteis que já foram escritas para você . Esse é o ponto de ver mônadas (e functores, e ...) em todos os lugares; não para que eu possa usar bindem vez de concate mappara implementar myFunkyListOperation(o que me ganha nada em si), mas sim de modo que quando eu venho a necessidade myFunkyParserOperatione myFunkyIOOperationeu possa voltar a utilizar o código que originalmente viu em termos de listas, porque isso é realmente mônada-generic .

Mas para abstrair em um tipo parametrizado como uma mônada com segurança de tipo , você precisa de tipos de tipo superior (como também explicado em outras respostas aqui).

Para uma perspectiva mais específica do .NET, escrevi uma postagem no blog sobre isso há algum tempo. O ponto crucial é que, com tipos de tipo superior, você poderia potencialmente reutilizar os mesmos blocos LINQ entre IEnumerablese IObservables, mas sem tipos de tipo superior isso é impossível.

O mais próximo que você poderia começar (eu descobri depois de postar o blog) é fazer o seu próprio IEnumerable<T>e IObservable<T>e estendeu ambos de um IMonad<T>. Isso permitiria que você reutilizasse seus blocos LINQ se eles estivessem denotados IMonad<T>, mas não é mais seguro de digitação porque permite que você misture e combine IObservablese IEnumerablesdentro do mesmo bloco, que embora possa parecer intrigante habilitar isso, você basicamente obter algum comportamento indefinido.

Escrevi um post posterior sobre como Haskell torna isso fácil. (Um no-op, na verdade - restringir um bloco a um certo tipo de mônada requer código; permitir a reutilização é o padrão).

O exemplo mais usado de polimorfismo de tipo superior em Haskell é a Monadinterface. Functore Applicativesão de tipo superior da mesma maneira, então vou mostrar Functorpara mostrar algo conciso.

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

Agora, examine essa definição, observando como a variável de tipo fé usada. Você verá que isso fnão pode significar um tipo que tenha valor. Você pode identificar valores nessa assinatura de tipo porque eles são argumentos e resultados de funções. Portanto, as variáveis ​​de tipo ae bsão tipos que podem ter valores. Assim como as expressões de tipo f ae f b. Mas não fela mesma. fé um exemplo de uma variável de tipo de tipo superior. Dado que esse *é o tipo de tipo que pode ter valores, fdeve ter o tipo * -> *. Ou seja, é preciso um tipo que pode ter valores, porque sabemos de um exame anterior que ae bdeve ter valores. E também sabemos disso f aef b deve ter valores, portanto, retorna um tipo que deve ter valores.

Isso faz com que o seja fusado na definição de Functoruma variável de tipo de tipo superior.

As interfaces Applicativee Monadadicionam mais, mas são compatíveis. Isso significa que eles funcionam em variáveis ​​de tipo com kind * -> *também.

Trabalhar em tipos de tipo superior introduz um nível adicional de abstração - você não está restrito a apenas criar abstrações sobre tipos básicos. Você também pode criar abstrações sobre tipos que modificam outros tipos.