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

87

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?

lagosta
fonte
2
Muitas das funções em Control.Monad fazem uso de tipos superiores, portanto, você pode querer procurar alguns exemplos. Em F #, as implementações teriam que ser repetidas para cada tipo de mônada concreta.
Lee
1
@Lee, mas você não poderia simplesmente fazer uma interface IMonad<T>e então lançá-la de volta para o exemplo IEnumerable<int>ou IObservable<int>quando terminar? Isso tudo é apenas para evitar o elenco?
lagosta
4
Bem, a transmissão não é segura, então isso responde à sua pergunta sobre segurança de tipo. Outra questão é como returnfuncionaria, uma vez que isso realmente pertence ao tipo de mônada, não a uma instância particular, então você não gostaria de colocá-la na IMonadinterface.
Lee
4
@Lee yeah, eu estava pensando que você teria que lançar o resultado final após a expressão, nada demais porque você apenas fez a expressão para saber o tipo. Mas parece que você também terá que lançar dentro de cada implemento do bindaka SelectManyetc. O que significa que alguém poderia usar a API para bindum IObservablepara um IEnumerablee presumir que funcionaria, o que sim, eca se for esse o caso e não há maneira de contornar isso. Só não tenho 100% de certeza de que não há maneira de contornar isso.
lagosta
5
Ótima pergunta. Ainda estou para ver um único exemplo prático atraente desse recurso de linguagem sendo IRL útil.
JD

Respostas:

78

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.

J. Abrahamson
fonte
3
Vou verificar e editar o código em alguns minutos, estou no meu telefone agora.
J. Abrahamson
12
@ J.Abrahamson +1 para uma boa resposta e ter paciência para digitar isso em seu telefone O_o
Daniel Gratzer
3
@lobsterism A TreeTreeé apenas patológico, mas de forma mais prática significa que você tem dois tipos diferentes de árvores entrelaçadas entre si - levar essa ideia um pouco mais longe pode fornecer algumas noções seguras de tipo muito poderosas, como vermelho estaticamente seguro / árvores negras e o tipo FingerTree estaticamente equilibrado.
J. Abrahamson
3
@JonHarrop Um exemplo padrão do mundo real é abstrair sobre mônadas, por exemplo, com pilhas de efeitos no estilo mtl. Você pode não concordar que isso seja valioso no mundo real, no entanto. Acho que é geralmente claro que as linguagens podem existir com sucesso sem HKTs, então qualquer exemplo fornecerá algum tipo de abstração que é mais sofisticada do que outras linguagens.
J. Abrahamson
2
Você pode ter, por exemplo, subconjuntos de efeitos autorizados em várias mônadas e abstrair quaisquer mônadas que atendam a essa especificação. Por exemplo, mônadas que instanciam o "teletipo" que permite a leitura e escrita no nível do caractere podem incluir IO e abstração de tubo. Você pode abstrair várias implementações assíncronas como outro exemplo. Sem HKTs você limita qualquer tipo composto daquela peça genérica.
J. Abrahamson
62

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.

Luis casillas
fonte
Então, eu estou interessado em seu último pedaço, por que é útil ter um fmapem Function aquando ele já tem uma .operação? Eu entendo por que .faz sentido ser a definição de fmapop, mas eu simplesmente não entendo onde você precisa usar em fmapvez de .. Talvez se você pudesse dar um exemplo onde isso seria útil, me ajudasse a entender.
lagosta
1
Ah, entendi: você pode fazer um fn doublede um functor, onde double [1, 2, 3][2, 4, 6]e double sindá um fn que é o dobro do pecado. Eu posso ver onde se você começar a pensar nessa mentalidade, quando você executa um mapa em um array, você espera um array de volta, não apenas um seq, porque, bem, estamos trabalhando em arrays aqui.
lagosta
@lobsterism: Existem algoritmos / técnicas que dependem da capacidade de abstrair um Functore deixar o cliente da biblioteca selecioná-lo. A resposta de J. Abrahamson fornece um exemplo: dobras recursivas podem ser generalizadas usando functores. Outro exemplo são as mônadas gratuitas; você pode pensar nisso como uma espécie de biblioteca de implementação de interpretador genérico, em que o cliente fornece o "conjunto de instruções" arbitrário Functor.
Luis Casillas
3
Uma resposta tecnicamente sólida, mas me deixa pensando por que alguém iria querer isso na prática. Não me peguei procurando por Haskell's Functorou a SemiGroup. Onde os programas reais mais usam esse recurso de linguagem?
JD
27

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

Ben
fonte
9
Esta está mais perto de ser uma resposta útil do que qualquer uma das outras respostas que li até agora, mas eu ainda gostaria de ver uma única aplicação prática onde tipos superiores são úteis.
JD
“O que você realmente quer essas abstrações é para que você possa ter um código que funcione genericamente com qualquer functor / mônada”. F # obteve mônadas na forma de expressões de computação 13 anos atrás, originalmente apresentando mônadas seq e assíncronas. Hoje F # desfruta de uma terceira mônada, consulta. Com tão poucas mônadas que têm tão pouco em comum, por que você iria querer abstraí-las?
JD
@JonHarrop Você está claramente ciente de que outras pessoas escreveram código usando um grande número de mônadas (e functores, setas, etc; HKTs não são apenas sobre mônadas) em linguagens que suportam HKTs e encontram usos para abstrair sobre eles. E é claro que você não acha que nenhum desses códigos tenha qualquer uso prático e está curioso para saber por que outras pessoas se importariam em escrevê-lo. Que tipo de percepção você espera obter ao voltar para iniciar um debate sobre um post de 6 anos que você já comentou 5 anos atrás?
Ben
"na esperança de ganhar voltando para iniciar um debate sobre um post de 6 anos". Retrospectivo. Com o benefício da retrospectiva, agora sabemos que as abstrações do F # sobre as mônadas permanecem em grande parte sem uso. Portanto, a capacidade de abstrair mais de 3 coisas amplamente diferentes é incomparável.
JD
@JonHarrop O ponto da minha resposta é que mônadas individuais (ou functores, etc.) não são realmente mais úteis do que funcionalidades semelhantes expressas sem uma interface nômade, mas que unificar muitas coisas díspares é. Vou adiar a sua experiência em F #, mas se você está dizendo que tem apenas 3 mônadas individuais (em vez de implementar uma interface monádica para todos os conceitos que poderiam ter uma, como falha, estado, análise, etc), então sim, não é surpreendente que você não se beneficiaria muito com a unificação dessas 3 coisas.
Ben
15

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

Dax Fohl
fonte
2
Vou te dar um +1 por ser a única resposta que menciona algo prático, mas acho que nunca usei IObservablesem código de produção.
JD
5
@JonHarrop Isso parece falso. Em F #, todos os eventos são IObservable, e você usa eventos no capítulo WinForms de seu próprio livro.
Dax Fohl
1
A Microsoft me pagou para escrever esse livro e exigiu que eu cobrisse esse recurso. Não me lembro de usar eventos no código de produção, mas vou olhar.
JD de
A reutilização entre IQueryable e IEnumerable também seria possível, suponho
KolA
Quatro anos depois e eu terminei de procurar: tiramos Rx da produção.
JD
13

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.

Carl
fonte
4
Outra grande explicação técnica sobre o que são tipos superiores me deixa imaginando para que eles são úteis. Onde você aproveitou isso no código real?
JD