Что такое более высокий тип в Scala?

Question

Вы можете найти следующее в Интернете:

1. Тип с более высоким родом == Конструктор типа?

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

   Некоторые говорят, что это тип с более высоким родом, потому что он абстрагируется от типов, которые будут соответствовать определению.

   Типы с более высоким родом - это типы, которые принимают другие типы и создают новый тип.

   Они также известны как конструктор типов. (Например, в Программирование в Scala).

2. Тип с более высоким родом == конструктор типа, который принимает конструктор типа в качестве параметра типа?

   В статье " Генерика высшего рода" вы можете прочитать

   ... типы, которые абстрагируются над типами, которые абстрагируются над типами ("типы с более высоким родом")... "

   что говорит о том, что

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

   является более родственным типом.

Поэтому, учитывая это, трудно различить конструктор типа, тип с более высоким родом и конструктор типа, который принимает конструкторы типа в качестве параметра типа, поэтому вопрос выше.

Answer 1

Позвольте мне восполнить некоторые из этих недоразумений, объяснив это неоднозначностью. Мне нравится использовать аналогию с уровнем стоимости, чтобы объяснить это, поскольку люди, как правило, лучше знакомы с ней.

Конструктор типа - это тип, который можно применять к аргументам типа для "конструирования" типа.

Конструктор значения - это значение, которое можно применить к аргументам значения, чтобы "создать" значение.

Конструкторы значений обычно называются "функциями" или "методами". Эти "конструкторы" также называются "полиморфными" (потому что они могут использоваться для конструирования "вещей" различной "формы") или "абстракций" (поскольку они абстрагируются от того, что варьируется между различными полиморфными экземплярами).

В контексте абстракции / полиморфизма первый порядок относится к "одноразовому использованию" абстракции: вы абстрагируетесь над типом один раз, но сам этот тип не может абстрагироваться над чем-либо. Java 5 дженерики первого порядка.

Интерпретация первого порядка вышеуказанных характеристик абстракций:

Конструктор типа - это тип, который можно применить к подходящим аргументам типа, чтобы "создать" правильный тип.

Конструктор значения - это значение, которое можно применить к аргументам правильного значения, чтобы "создать" правильное значение.

Подчеркнем, что здесь нет абстракции (думаю, вы могли бы назвать это "нулевым порядком", но я нигде не видел, чтобы это использовалось), например, значение 1 или тип Stringмы обычно говорим что-то "правильное" значение или тип.

Правильное значение "сразу же можно использовать" в том смысле, что оно не ожидает аргументов (оно не абстрагируется от них). Думайте о них как о значениях, которые вы можете легко распечатать / проверить (сериализация функции обманывает!).

Правильный тип - это тип, который классифицирует значения (включая конструкторы значений), конструкторы типов не классифицируют никакие значения (их сначала нужно применить к аргументам правильного типа, чтобы получить правильный тип). Для создания экземпляра типа необходимо (но не достаточно), чтобы это был правильный тип. (Это может быть абстрактный класс или класс, к которому у вас нет доступа.)

"Высший порядок" - это просто общий термин, который означает многократное использование полиморфизма / абстракции. Это означает то же самое для полиморфных типов и значений. Конкретно, абстракция высшего порядка абстрагируется от чего-то, что абстрагируется от чего-то. Для типов термин "более высокий род" является специализированной версией более общего "высшего порядка".

Таким образом, версия нашей характеристики высшего порядка становится:

Конструктор типа - это тип, который можно применять к аргументам типа (правильные типы или конструкторы типов) для "конструирования" правильного типа (конструктора).

Конструктор значения - это значение, которое можно применить к аргументам значения (правильные значения или конструкторы значений), чтобы "создать" правильное значение (конструктор).

Таким образом, "высший порядок" просто означает, что когда вы говорите "абстрагируясь над X", вы действительно это имеете в виду! X то, что абстрагируется, не теряет своих собственных "прав на абстракцию": оно может абстрагировать все, что захочет (Между прочим, я использую здесь глагол "абстрактный" для обозначения: опустить что-то, что не является существенным для определения значения или типа, так что оно может быть изменено / предоставлено пользователем абстракции в качестве аргумента.)

Вот некоторые примеры (вдохновленные вопросами Лутца по электронной почте) правильных значений и типов первого и высшего порядка:

                   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]})#λ

Где используемые классы были определены как:

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

Чтобы избежать косвенного влияния через определение классов, вам нужно как-то выразить функции анонимного типа, которые не могут быть выражены напрямую в Scala, но вы можете использовать структурные типы без слишком больших синтаксических издержек (#λстиль связан с retronym afaik):

В некоторой гипотетической будущей версии Scala, которая поддерживает функции анонимного типа, вы можете сократить эту последнюю строку из примеров до:

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

(Лично я сожалею, что когда-либо говорил о "типах с более высоким родом", в конце концов, это просто типы! Когда вам абсолютно необходимо устранить неоднозначность, я предлагаю сказать такие вещи, как "параметр конструктора типа", "член конструктора типа"). или "псевдоним конструктора типов", чтобы подчеркнуть, что речь идет не только о правильных типах.)

PS: чтобы еще больше усложнить ситуацию, "полиморфный" неоднозначен по-другому, так как полиморфный тип иногда означает универсально выраженный тип, такой как Forall T, T => T, который является правильным типом, так как он классифицирует полиморфные значения (в Scala это значение может быть записано как структурный тип {def apply[T](x: T): T = x})

Answer 2

(Этот ответ является попыткой украсить ответ адрианских мавров некоторой графической и исторической информацией.)

Более старшие виды являются частью Scala с 2.5.

• До этого Scala, как и Java до сих пор, не разрешал использовать конструктор типов ("generics" в Java) для использования в качестве параметра типа для конструктора типов. например

   trait Monad [M[_]]
  

  не представилось возможным.

  В Scala 2.5 система типов была расширена за счет возможности классифицировать типы на более высоком уровне (известный как полиморфизм конструктора типов). Эти классификации известны как виды.

  (Изображение получено из Дженерики Высшего Вида)

  Следствием этого является то, что конструктор типа (например, List) может использоваться так же, как и другие типы в положении параметра типа конструкторов типов, и поэтому они стали первоклассными типами начиная с Scala 2.5. (Подобно функциям, которые являются первоклассными значениями в Scala).

  В контексте системы типов, поддерживающей более высокие виды, мы можем различать собственные типы, такие как Int или же List[Int] из типов первого порядка, таких как List и типы более высокого вида, такие как Functor или же Monad (типы, которые абстрагируются над типами, которые абстрагируются над типами).

  Система типов Java с другой стороны не поддерживает типы и поэтому не имеет типов "более высокого типа".

  Так что это должно быть видно на фоне системы вспомогательных типов.

• В случае Scala вы часто видите примеры конструктора типа, такого как

   trait Iterable[A, Container[_]]
  

  с заголовком "Типы с более высоким родом", например, в Scala для универсальных программистов, раздел 4.3

  Это иногда вводит в заблуждение, потому что многие ссылаются на Container как высший добрый тип, а не Iterable, но что является более точным,

  использование Container в качестве параметра конструктора типа типа с более высоким родом (высшего порядка) здесь Iterable,

Answer 3

Вид обычных типов, таких как Int а также Char, чьи экземпляры являются значениями, является *, Тип унарных конструкторов типа Maybe является * -> *; конструкторы двоичного типа, такие как Either иметь ( карри) вид * -> * -> *, и так далее. Вы можете просматривать типы как Maybe а также Either как функции уровня типа: они принимают один или несколько типов и возвращают тип.

Функция более высокого порядка, если она имеет порядок больше 1, где порядок (неформально) - глубина вложения слева от стрелок функции:

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

Итак, короче говоря, тип с более высоким родом - это просто функция высшего порядка на уровне типа.

• Заказ 0: Int :: *
• Заказ 1: Maybe :: * -> *
• Заказ 2: Functor :: (* -> *) -> Constraint—Higher-kinded: конвертирует конструкторы унарного типа в ограничения класса типов

Answer 4

Я бы сказал: тезисы с более высоким типом по сравнению с конструктором типов. Например рассмотреть

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

Вот Functor является "типом с более высоким родом" (используется в статье "Generics of the Higher Kind"). Это не конкретный ("первого порядка") конструктор типа List (который абстрагируется только над собственными типами). Он абстрагируется от всех унарных ("первого порядка") конструкторов типов (обозначается как F[_]).

Или, если выразить это иначе: в Java есть конструкторы типов (например, List<T>), но у нас нет "типов с более высоким родом", потому что мы не можем абстрагироваться над ними (например, мы не можем написать Functor интерфейс, определенный выше - по крайней мере, не напрямую).

Термин "полиморфизм высшего порядка (конструктор типов)" используется для описания систем, которые поддерживают "типы с более высоким родом".

Answer 5

Scala REPL предоставляет :kind команда, которая

scala> :help kind

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

Например,

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.

---

В :help дает четкие определения, поэтому я думаю, что стоит опубликовать его здесь полностью (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.