O que é um tipo de classe superior em Scala?

275

Você pode encontrar o seguinte na web:

  1. Tipo de classificação superior == tipo de construtor?

    class AClass[T]{...} // For example, class List[T]

    Alguns dizem que esse é um tipo de classificação mais alta, porque abstrai sobre tipos que seriam compatíveis com a definição.

    Tipos de classificação superior são aqueles que usam outros tipos e constroem um novo tipo

    Estes também são conhecidos como construtor de tipos . (Por exemplo, em Programação no Scala ).

  2. Tipo de classificação superior == construtor de tipos que usa o construtor de tipos como um parâmetro de tipo?

    No artigo Genéricos de tipo superior , você pode ler

    ... tipos que abstraem sobre tipos que abstraem sobre tipos ('tipos superiores') ... "

    o que sugere que

    class XClass[M[T]]{...} // or
    
    trait YTrait[N[_]]{...} // e.g. trait Functor[F[_]]

    é um tipo de classificação superior.

Portanto, com isso em mente, é difícil distinguir entre construtor de tipo , tipo superior e construtor de tipo que toma construtores de tipo como parâmetro de tipo , portanto, a pergunta acima.

Lutz
fonte
Adicionado o Functor de Landei como exemplo.
Lutz

Respostas:

284

Deixe-me compensar o começo de uma confusão confusa com alguma desambiguação. Eu gosto de usar a analogia com o nível de valor para explicar isso, pois as pessoas tendem a estar mais familiarizadas com ela.

Um construtor de tipo é um tipo que você pode aplicar aos argumentos de tipo para "construir" um tipo.

Um construtor de valor é um valor que você pode aplicar aos argumentos de valor para "construir" um valor.

Construtores de valor são geralmente chamados de "funções" ou "métodos". Também se diz que esses "construtores" são "polimórficos" (porque podem ser usados ​​para construir "coisas" de "forma" variável) ou "abstrações" (uma vez que abstraem o que varia entre instanciações polimórficas diferentes).

No contexto de abstração / polimorfismo, primeira ordem se refere ao "uso único" da abstração: você abstrai um tipo uma vez, mas esse tipo em si não pode abstrair nada. Os genéricos Java 5 são de primeira ordem.

A interpretação de primeira ordem das caracterizações acima de abstrações é:

Um construtor de tipo é um tipo que você pode aplicar a argumentos de tipo adequados para "construir" um tipo adequado.

Um construtor de valor é um valor que você pode aplicar a argumentos de valor adequados para "construir" um valor adequado.

Para enfatizar, não há abstração envolvida (acho que você poderia chamar isso de "ordem zero", mas eu nunca vi isso usado em nenhum lugar), como o valor 1ou o tipo String, geralmente dizemos que algo é um valor ou tipo "adequado".

Um valor adequado é "imediatamente utilizável" no sentido de que não está aguardando argumentos (não é abstraído sobre eles). Pense neles como valores que você pode imprimir / inspecionar facilmente (serializar uma função é trapaça!).

Um tipo adequado é um tipo que classifica valores (incluindo construtores de valor); os construtores de tipo não classificam nenhum valor (eles primeiro precisam ser aplicados aos argumentos de tipo corretos para produzir um tipo adequado). Para instanciar um tipo, é necessário (mas não suficiente) que seja um tipo adequado. (Pode ser uma classe abstrata ou uma classe à qual você não tem acesso.)

"Ordem superior" é simplesmente um termo genérico que significa uso repetido de polimorfismo / abstração. Significa o mesmo para tipos e valores polimórficos. Concretamente, uma abstração de ordem superior abstrai sobre algo que abstrai sobre algo. Para tipos, o termo "tipo superior" é uma versão para fins especiais da "ordem superior" mais geral.

Assim, a versão superior de nossa caracterização se torna:

Um construtor de tipo é um tipo que você pode aplicar aos argumentos de tipo (tipos adequados ou construtores de tipo) para "construir" um tipo adequado (construtor).

Um construtor de valor é um valor que você pode aplicar a argumentos de valor (valores adequados ou construtores de valor) para "construir" um valor adequado (construtor).

Assim, "ordem superior" significa simplesmente que, quando você diz "abstraindo sobre X", realmente entende! O Xque é abstraído não perde seus próprios "direitos de abstração": pode abstrair tudo o que deseja. (A propósito, eu uso o verbo "abstract" aqui para significar: deixar de fora algo que não é essencial para a definição de um valor ou tipo, para que possa ser variado / fornecido pelo usuário da abstração como argumento .)

Aqui estão alguns exemplos (inspirados nas perguntas de Lutz por email) de valores e tipos adequados, de primeira e de mais alta ordem:

                   proper    first-order           higher-order

values             10        (x: Int) => x         (f: (Int => Int)) => f(10)
types (classes)    String    List                  Functor
types              String    ({type λ[x] = x})#λ   ({type λ[F[x]] = F[String]})#λ

Onde as classes usadas foram definidas como:

class String
class List[T]
class Functor[F[_]]

Para evitar a indireção através da definição de classes, é necessário expressar de alguma forma funções de tipo anônimo, que não são expressáveis ​​diretamente no Scala, mas você pode usar tipos estruturais sem muita sobrecarga sintática (o estilo é devido a https://stackoverflow.com / users / 160378 / retronym afaik):

Em alguma versão futura hipotética do Scala que suporta funções do tipo anônimo, você pode encurtar a última linha dos exemplos para:

types (informally) String    [x] => x              [F[x]] => F[String]) // I repeat, this is not valid Scala, and might never be

(Em uma nota pessoal, lamento já ter falado sobre "tipos de classe superior", eles são apenas tipos afinal! Quando você absolutamente precisar desambiguar, sugiro dizer coisas como "parâmetro do construtor de tipo", "membro do construtor de tipo" , ou "alias do construtor de tipos", para enfatizar que você não está falando apenas de tipos adequados.)

ps: Para complicar ainda mais, "polimórfico" é ambíguo de uma maneira diferente, pois um tipo polimórfico às vezes significa um tipo quantificado universalmente, como Forall T, T => T, que é um tipo adequado, pois classifica valores polimórficos (em Scala, esse valor pode ser escrito como o tipo estrutural {def apply[T](x: T): T = x})

Adriaan Moors
fonte
1
veja também: adriaanm.github.com/research/2010/10/06/…
Adriaan Moors
5
De Adriaan "Type Construtor Polimorfismo" artigo agora em adriaanm.github.com/research/2010/10/06/...
Steven Shaw
Eu continuo lendo-o como parentes superior e imaginando uma alma gêmea
Janac Meena
110

(Esta resposta é uma tentativa de decorar a resposta de Adriaan Moors com algumas informações gráficas e históricas.)

Tipos superiores são parte do Scala desde 2.5.

  • Antes disso, o Scala, como Java até agora, não permitia usar o construtor de tipo ("genéricos" em Java) para ser usado como parâmetro de tipo para um construtor de tipo. por exemplo

     trait Monad [M[_]]

    não foi possível.

    No Scala 2.5, o sistema de tipos havia sido estendido pela capacidade de classificar tipos em um nível superior (conhecido como polimorfismo de construtor de tipos ). Essas classificações são conhecidas como tipos.

    Realização de tipo e tipo, ** derivada ** de "Genéricos de um tipo superior" (Imagem derivada de genéricos de tipo superior )

    A conseqüência é que esse tipo de construtor (por exemplo List) poderia ser usado como outros tipos na posição de parâmetro de tipo de construtores de tipo e, portanto, eles se tornaram tipos de primeira classe desde o Scala 2.5. (Semelhante às funções que são valores de primeira classe no Scala).

    No contexto de um sistema de tipos que suporta tipos mais altos, podemos distinguir tipos adequados , tipos como Intou List[Int]de tipos de primeira ordem como Liste tipos de tipos mais altos como Functoror Monad(tipos que abstraem sobre tipos que abstraem sobre tipos).

    O sistema de tipos de Java, por outro lado, não suporta tipos e, portanto, não possui tipos de "tipo superior".

    Portanto, isso deve ser visto no contexto do sistema de tipos de suporte.

  • No caso do Scala, você costuma ver exemplos de um construtor de tipos como

     trait Iterable[A, Container[_]]

    com o título "Tipos superiores", por exemplo, em Scala para programadores genéricos, seção 4.3

    Isso às vezes é missleading, porque muitos se referem Containercomo tipo superior kinded e não Iterable, mas o que é é mais preciso,

    o uso de Containercomo parâmetro construtor de tipo de um tipo superior (de ordem superior) aqui Iterable.

Lutz
fonte
80

O tipo de tipos comuns como Inte Char, cujas instâncias são valores, é *. O tipo de construtores de tipo unário como Maybeé * -> *; construtores de tipo binário, como Eitherhave ( curried ) * -> * -> *, e assim por diante. Você pode visualizar tipos como Maybee Eithercomo funções no nível de tipo: eles pegam um ou mais tipos e retornam um tipo.

Uma função é de ordem superior se tiver uma ordem maior que 1, onde a ordem é (informalmente) a profundidade de aninhamento, à esquerda, das setas de função:

  • Ordem 0: 1 :: Int
  • Ordem 1: chr :: Int -> Char
  • Order 2: fix :: (a -> a) -> a,map :: (a -> b) -> [a] -> [b]
  • Ordem 3: ((A -> B) -> C) -> D
  • Ordem 4: (((A -> B) -> C) -> D) -> E

Portanto, para encurtar a história, um tipo de tipo superior é apenas uma função de ordem superior no nível de tipo.

  • Ordem 0: Int :: *
  • Ordem 1: Maybe :: * -> *
  • Ordem 2: Functor :: (* -> *) -> Constraint- de tipo mais alto: converte construtores de tipo unário em restrições de classe de tipo
Jon Purdy
fonte
Ok, entendi, o que seria um exemplo em Scala para (* ⇒ *) ⇒ * e (* ⇒ *) ⇒ (* ⇒ *)? O Functor de Landei se encaixaria na primeira categoria ou melhor, na segunda?
Lutz
1
@lutz: Seria na primeira categoria: Functorproduz um tipo adequado (bem, característica, mas mesma ideia) Functor[F[_]]de um construtor de tipos F.
9119 Jon Purdy
1
@ Jon: Um post muito esclarecedor, obrigado. O conversor de tipos pode (* => *) => (* => *)ser expresso em Scala? Se não, em outro idioma?
Eugen Labun
@ JonPurdy A comparação entre * ⇒ * ⇒ *com o curry é muito útil. Obrigado!
Lifu Huang 18/09/16
(* ⇒ *) ⇒ (* ⇒ *)também pode ser escrito (* ⇒ *) ⇒ * ⇒ *. Pode ser expresso em Scala como Foo[F[_], T]. É o tipo de tipo como (em Haskell) newtype Twice f a = Twice (f (f a))(por exemplo, Twice Maybe IntMaybe (Maybe Int), Twice [] Char[[Char]]) ou algo mais interessante como a mônada livre data Free f a = Pure a | Free (f (Free f a)).
Jon Purdy
37

Eu diria: Um tipo de tipo mais alto abstrai um construtor de tipo. Por exemplo, considere

trait Functor [F[_]] {
   def map[A,B] (fn: A=>B)(fa: F[A]): F[B]
}

Aqui Functorestá um "tipo superior" (conforme usado no artigo "Genéricos de um tipo superior" ). Não é um construtor de tipo concreto ("de primeira ordem") List(que abstrai apenas tipos adequados). Ele abstrai todos os construtores do tipo unário ("de primeira ordem") (como indicado em F[_]).

Ou, de outra forma: em Java, temos claramente tipos de construtores (por exemplo List<T>), mas não temos "tipos de classificação superior", porque não podemos abstrair sobre eles (por exemplo, não podemos escrever a Functorinterface definida acima - pelo menos não diretamente ).

O termo "polimorfismo de ordem superior (construtor de tipos)" é usado para descrever sistemas que suportam "tipos de classificação superior".

Landei
fonte
Foi o que pensei, mas parece contradizer a resposta de Jon, em que um "construtor de tipo concreto" já é um "tipo superior".
Lutz
3
Sim. De acordo com a resposta de Jon (como eu a entendo) List<T>em Java, seria um construtor de tipo unário, pois tem claramente esse tipo * -> *. O que está faltando na resposta de Jon é que você deve ser capaz de abstrair a "coisa toda" (e não apenas a segunda *como em Java) para chamá-la de um tipo de classificação superior.
Landei 6/06/11
@ Landai: O artigo Scala para programadores genéricos na seção 4.3 sugere que a característica Iterable [A, Container [_]] seja do tipo superior (embora não esteja claro se Iterator ou Container se destina) onde, do outro lado, vero690 em a seção 2.3.1 usa o termo construtor de tipo superior para algo como (* -> *) -> * (operador de tipo parametrizado com construtor de tipo de ordem superior) que se parece com o traço Iterator ou Functor.
Lutz
1
Provavelmente está certo, mas acho que estamos começando a dividir os cabelos aqui. O ponto importante em relação aos tipos de classificação superior é que não apenas os construtores de tipos estão envolvidos (peça um polimorfismo de construtor de tipo), mas que somos capazes de abstrair sobre o tipo concreto desses construtores de tipo (polimorfismo de construtor de tipo de ordem superior). Temos a capacidade de abstrair o que queremos sem restrições (referentes a tipos e construtores de tipos), o que torna menos interessante nomear todas as versões possíveis desse recurso. E isso machuca meu cérebro.
Landei
2
Em geral, é importante distinguir definições e referências aqui. A definição def succ(x: Int) = x+1introduz o "construtor de valor" (veja minha outra resposta para o que quero dizer com isso) succ(ninguém se referiria a esse valor como succ (x: Int)). Por analogia, Functoré o tipo (de fato de tipo mais alto) definido em sua resposta. Novamente, você não deve se referir a ele como Functor[F[_]](o que é F? O que é _? Eles não estão no escopo! Infelizmente, o açúcar sintático para os existenciais turva as águas aqui, abreviando F[_]para F[T forSome {type T}])
Adriaan Moors
1

O Scala REPL fornece um :kindcomando que

scala> :help kind

:kind [-v] <type>
Displays the kind of a given type.

Por exemplo,

scala> trait Foo[A]
trait Foo

scala> trait Bar[F[_]]
trait Bar

scala> :kind -v Foo
Foo's kind is F[A]
* -> *
This is a type constructor: a 1st-order-kinded type.

scala> :kind -v Foo[Int]
Foo[Int]'s kind is A
*
This is a proper type.

scala> :kind -v Bar
Bar's kind is X[F[A]]
(* -> *) -> *
This is a type constructor that takes type constructor(s): a higher-kinded type.

scala> :kind -v Bar[Foo]
Bar[Foo]'s kind is A
*
This is a proper type.

Ele :helpfornece definições claras, então acho que vale a pena publicá-la aqui na íntegra (Scala 2.13.2)

scala> :help kind

:kind [-v] <type>
Displays the kind of a given type.

    -v      Displays verbose info.

"Kind" is a word used to classify types and type constructors
according to their level of abstractness.

Concrete, fully specified types such as `Int` and `Option[Int]`
are called "proper types" and denoted as `A` using Scala
notation, or with the `*` symbol.

    scala> :kind Option[Int]
    Option[Int]'s kind is A

In the above, `Option` is an example of a first-order type
constructor, which is denoted as `F[A]` using Scala notation, or
* -> * using the star notation. `:kind` also includes variance
information in its output, so if we ask for the kind of `Option`,
we actually see `F[+A]`:

    scala> :k -v Option
    Option's kind is F[+A]
    * -(+)-> *
    This is a type constructor: a 1st-order-kinded type.

When you have more complicated types, `:kind` can be used to find
out what you need to pass in.

    scala> trait ~>[-F1[_], +F2[_]] {}
    scala> :kind ~>
    ~>'s kind is X[-F1[A1],+F2[A2]]

This shows that `~>` accepts something of `F[A]` kind, such as
`List` or `Vector`. It's an example of a type constructor that
abstracts over type constructors, also known as a higher-order
type constructor or a higher-kinded type.
Mario Galic
fonte