Por que você precisa de tipos mais altos?

Alguns idiomas permitem classes e funções com parâmetros de tipo (como List<T>onde Tpode ser um tipo arbitrário). Por exemplo, você pode ter uma função como:

List<S> Function<S, T>(List<T> list)

No entanto, alguns idiomas permitem que esse conceito seja estendido um nível mais alto, permitindo que você tenha uma função com a assinatura:

K<S> Function<K<_>, S, T>(K<T> arg)

Onde em K<_>si é um tipo como List<_>esse tem um parâmetro de tipo. Esse "tipo parcial" é conhecido como construtor de tipos.

Minha pergunta é: por que você precisa dessa capacidade? Faz sentido ter um tipo como, List<T>porque todos List<T>são quase exatamente iguais, mas todos K<_>podem ser totalmente diferentes. Você pode ter um Option<_>e um List<_>que não possuem nenhuma funcionalidade comum.

Como ninguém mais respondeu à pergunta, acho que vou tentar. Vou ter que ficar um pouco filosófico.

A programação genérica trata de abstrair tipos semelhantes, sem a perda de informações de tipo (o que acontece com o polimorfismo de valor orientado a objetos). Para fazer isso, os tipos devem necessariamente compartilhar algum tipo de interface (um conjunto de operações, não o termo OO) que você pode usar.

Nas linguagens orientadas a objetos, os tipos satisfazem uma interface em virtude de classes. Cada classe tem sua própria interface, definida como parte de seu tipo. Como todas as classes List<T>compartilham a mesma interface, você pode escrever um código que funcione independentemente da Tsua escolha. Outra maneira de impor uma interface é uma restrição de herança e, embora as duas pareçam diferentes, elas são parecidas se você pensar sobre isso.

Na maioria das linguagens orientadas a objetos, List<>não é um tipo adequado em si. Não possui métodos e, portanto, não possui interface. É só List<T>que tem essas coisas. Essencialmente, em termos mais técnicos, os únicos tipos que você pode abstrair significativamente são aqueles com esse tipo *. Para fazer uso de tipos mais avançados em um mundo orientado a objetos, você deve formular restrições de tipo de maneira consistente com essa restrição.

Por exemplo, conforme mencionado nos comentários, podemos visualizar Option<>eList<> como "mapeáveis", no sentido de que, se você tiver uma função, poderá converter um Option<T>em um Option<S>ou a List<T>em a List<S>. Lembrando que as classes não podem ser usadas para abstrair diretamente tipos mais altos, criamos uma interface:

IMappable<K<_>, T> where K<T> : IMappable<K<_>, T>

E então implementamos a interface em ambos List<T> e Option<T>como IMappable<List<_>, T>e IMappable<Option<_>, T>respectivamente. O que fizemos foi usar tipos de tipo mais alto para colocar restrições nos tipos reais (sem tipo mais alto) Option<T>e List<T>. É assim que é feito no Scala, embora o Scala tenha recursos como características, variáveis ​​de tipo e parâmetros implícitos que o tornam mais expressivo.

Em outros idiomas, é possível abstrair diretamente sobre tipos de tipos mais altos. Em Haskell, uma das maiores autoridades em sistemas de tipos, podemos codificar uma classe de tipo para qualquer tipo, mesmo que ela tenha um tipo mais alto. Por exemplo,

class Mappable mp where
    map :: mp a -> mp b

Essa é uma restrição colocada diretamente em um tipo (não especificado) mp que utiliza um parâmetro de tipo e requer que seja associado à função mapque transforma um mp<a>em um mp<b>. Podemos então escrever funções que restringem tipos de tipos mais altos, Mappableassim como nas linguagens orientadas a objetos, você pode colocar uma restrição de herança. Bem, mais ou menos.

Em resumo, sua capacidade de usar tipos de tipos mais altos depende de sua capacidade de restringi-los ou de usá-los como parte das restrições de tipo.