Scala 中的高级类型是什么？

What is a higher kinded type in Scala?

提问by Lutz

You can find the following on the web:

您可以在网络上找到以下内容：

1. Higher kinded type == type constructor?

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

   Some say this is a higher kinded type, because it abstracts over types which would be compliant with the definition.

   Higher kinded typesare types which take other types and construct a new type

   These though are also known as type constructor. (For example, in Programming in Scala).

2. Higher kinded type == type constructor which takes type constructor as a type parameter?

   In the paper Generics of a Higher Kind, you can read

   ... types that abstract over types that abstract over types ('higher-kinded types') ..."

   which suggests that

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

   is a higher kinded type.

1. 高级类型 == 类型构造函数？

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

   有人说这是一种更高级的类型，因为它抽象了符合定义的类型。

   高级类型是采用其他类型并构造新类型的类型

   这些也被称为类型构造函数。（例如，在 Scala 编程中）。

2. 将类型构造函数作为类型参数的高级类型 == 类型构造函数？

   在论文Generics of a Higher Kind 中，您可以阅读

   ... 对类型进行抽象的类型（'高级类型'）...”

   这表明

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

   是一种更高级的类型。

So with this in mind, it is difficult to distinguish between type constructor, higher kinded typeand type constructor which takes type constructors as type parameter, therefore the question above.

因此，考虑到这一点，很难区分类型构造函数、更高级的类型和将类型构造函数作为类型参数的类型构造函数，因此出现了上述问题。

回答by Adriaan Moors

Let me make up for starting some of this confusion by pitching in with some disambiguation. I like to use the analogy to the value level to explain this, as people tend to be more familiar with it.

让我通过消除歧义来弥补开始的一些混乱。我喜欢用价值水平来类比来解释这一点，因为人们往往更熟悉它。

A type constructor is a type that you can apply to type arguments to "construct" a type.

A value constructor is a value that you can apply to value arguments to "construct" a value.

类型构造函数是一种可以应用于类型参数以“构造”类型的类型。

值构造函数是一个值，您可以将其应用于值参数以“构造”一个​​值。

Value constructors are usually called "functions" or "methods". These "constructors" are also said to be "polymorphic" (because they can be used to construct "stuff" of varying "shape"), or "abstractions" (since they abstract over what varies between different polymorphic instantiations).

值构造函数通常称为“函数”或“方法”。这些“构造函数”也被称为“多态的”（因为它们可用于构造不同“形状”的“东西”）或“抽象”（因为它们抽象了不同多态实例之间的差异）。

In the context of abstraction/polymorphism, first-order refers to "single use" of abstraction: you abstract over a type once, but that type itself cannot abstract over anything. Java 5 generics are first-order.

在抽象/多态的上下文中，一阶是指抽象的“一次性使用”：您对一个类型进行一次抽象，但该类型本身不能对任何内容进行抽象。Java 5 泛型是一阶的。

The first-order interpretation of the above characterizations of abstractions are:

上述抽象特征的一阶解释是：

A type constructor is a type that you can apply to proper type arguments to "construct" a proper type.

A value constructor is a value that you can apply to proper value arguments to "construct" a proper value.

类型构造函数是一种类型，您可以将其应用于正确的类型参数以“构造”正确的类型。

值构造函数是一个值，您可以将其应用于适当的值参数以“构造”适当的值。

To emphasize there's no abstraction involved (I guess you could call this "zero-order", but I have not seen this used anywhere), such as the value 1or the type String, we usually say something is a "proper" value or type.

为了强调不涉及抽象（我想你可以称之为“零阶”，但我没有看到在任何地方使用过），例如 value1或 type String，我们通常说某物是“正确的”值或类型。

A proper value is "immediately usable" in the sense that it is not waiting for arguments (it does not abstract over them). Think of them as values that you can easily print/inspect (serializing a function is cheating!).

一个适当的值是“立即可用的”，因为它不等待参数（它不抽象它们）。将它们视为可以轻松打印/检查的值（序列化函数是作弊！）。

A proper type is a type that classifies values (including value constructors), type constructors do not classify any values (they first need to be applied to the right type arguments to yield a proper type). To instantiate a type, it's necessary (but not sufficient) that it be a proper type. (It might be an abstract class, or a class that you don't have access to.)

正确类型是对值进行分类的类型（包括值构造函数），类型构造函数不对任何值进行分类（它们首先需要应用于正确的类型参数以产生正确的类型）。要实例化一个类型，它是一个适当的类型是必要的（但不是充分的）。（它可能是一个抽象类，或者一个您无权访问的类。）

"Higher-order" is simply a generic term that means repeated use of polymorphism/abstraction. It means the same thing for polymorphic types and values. Concretely, a higher-order abstraction abstracts over something that abstracts over something. For types, the term "higher-kinded" is a special-purpose version of the more general "higher-order".

“高阶”只是一个通用术语，表示重复使用多态性/抽象。对于多态类型和值，这意味着同样的事情。具体来说，高阶抽象抽象了抽象事物。对于类型，术语“higher-kinded”是更通用的“higher-order”的特殊用途版本。

Thus, the higher-order version of our characterization becomes:

因此，我们表征的高阶版本变为：

A type constructor is a type that you can apply to type arguments (proper types or type constructors) to "construct" a proper type (constructor).

A value constructor is a value that you can apply to value arguments (proper values or value constructors) to "construct" a proper value (constructor).

类型构造函数是一种可以应用于类型参数（正确类型或类型构造函数）以“构造”正确类型（构造函数）的类型。

值构造函数是可以应用于值参数（正确值或值构造函数）以“构造”正确值（构造函数）的值。

Thus, "higher-order" simply means that when you say "abstracting over X", you really mean it! The Xthat is abstracted over does not lose its own "abstraction rights": it can abstract all it wants. (By the way, I use the verb "abstract" here to mean: to leave out something that is not essential for the definition of a value or type, so that it can be varied/provided by the user of the abstraction as an argument.)

因此，“高阶”仅意味着当您说“对 X 进行抽象”时，您是认真的！该X被抽象在不失去自己的“抽象权利”：它可以抽象所有就是了。（顺便说一句，我在这里使用动词“抽象”的意思是：省略对值或类型的定义不是必需的东西，以便抽象的用户可以将其作为参数进行更改/提供.)

Here are some examples (inspired by Lutz's questions by email) of proper, first-order and higher-order values and types:

以下是一些正确、一阶和高阶值和类型的示例（受 Lutz 通过电子邮件提出的问题启发）：

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

Where the used classes were defined as:

其中使用的类定义为：

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

To avoid the indirection through defining classes, you need to somehow express anonymous type functions, which are not expressible directly in Scala, but you can use structural types without too much syntactic overhead (the #λ-style is due to https://stackoverflow.com/users/160378/retronymafaik):

为了避免通过定义类的间接性，您需要以某种方式表达匿名类型函数，这些函数在 Scala 中无法直接表达，但您可以使用结构类型而无需太多语法开销（#λ-style 是由于https://stackoverflow.com /users/160378/retronymafaik）：

In some hypothetical future version of Scala that supports anonymous type functions, you could shorten that last line from the examples to:

在支持匿名类型函数的某些假设的 Scala 未来版本中，您可以将示例中的最后一行缩短为：

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

(On a personal note, I regret ever having talked about "higher-kinded types", they're just types after all! When you absolutely need to disambiguate, I suggest saying things like "type constructor parameter", "type constructor member", or "type constructor alias", to emphasize that you're not talking about just proper types.)

（就我个人而言，我很遗憾曾经谈论过“高级类型”，它们毕竟只是类型！当你绝对需要消除歧义时，我建议说诸如“类型构造函数参数”、“类型构造函数成员”之类的东西，或“类型构造函数别名”，以强调您不是在谈论正确的类型。）

ps: To complicate matters further, "polymorphic" is ambiguous in a different way, since a polymorphic type sometimes means a universally quantified type, such as Forall T, T => T, which is a proper type, since it classifies polymorphic values (in Scala, this value can be written as the structural type {def apply[T](x: T): T = x})

ps：更复杂的是，“多态”以不同的方式含糊不清，因为多态类型有时意味着普遍量化的类型，例如Forall T, T => T，这是一个适当的类型，因为它对多态值进行分类（在 Scala 中，这个值可以是写成结构类型{def apply[T](x: T): T = x}）

回答by Lutz

(This answer is an attempt to decorate Adriaan Moors answer by some graphical and historical information.)

（这个答案是试图通过一些图形和历史信息来装饰 Adriaan Moors 的答案。）

Higher kinded types are part of Scala since 2.5.

从 2.5 开始，更高级的类型是 Scala 的一部分。

• Before that Scala, as Java till now, did not allow to use type constructor ("generics" in Java) to be used as type parameter to a type constructor. e.g.

   trait Monad [M[_]]
  

  was not possible.

  In Scala 2.5 the type system had been extended by the ability to classify types on a higher level (known as type constructor polymorphism). These classifications are known as kinds.

  (Picture derived from Generics of a Higher Kind)

  The consequence is, that type constructor (e.g. List) could be used just as other types in type parameter position of type constructors and so they became first class types since Scala 2.5. (Similar to functions which are first class values in Scala).

  In the context of a type system supporting higher kinds, we can distinguish proper types, types like Intor List[Int]from first-order types like Listand types of a higher kindlike Functoror Monad(types which abstract over types which abstract over types).

  The type system of Java on the other side does not support kinds and therefore has no types of a "higher kind".

  So this has to be seen against the background of the supporting type system.

• In the case of Scala you often see examples of a type constructor like

   trait Iterable[A, Container[_]]
  

  with the headline "Higher kinded types", e.g. in Scala for generic programmers, section 4.3

  This is sometimes missleading, because many refer to Containeras higher kinded typeand not Iterable, but what is more precise is,

  the use of Containeras type constructor parameter of a higher kinded (higher-order) type here Iterable.

• 在此之前，作为 Java 的 Scala 不允许使用类型构造函数（Java 中的“泛型”）作为类型构造函数的类型参数。例如

   trait Monad [M[_]]
  

  不可能。

  在 Scala 2.5 中，类型系统通过在更高级别对类型进行分类的能力进行了扩展（称为类型构造函数多态性）。这些分类称为种类。

  （图片来自高级泛型）

  结果是，该类型构造函数（例如List）可以在类型构造函数的类型参数位置中与其他类型一样使用，因此它们成为自 Scala 2.5 以来的第一类类型。（类似于 Scala 中的第一类值的函数）。

  在支持更高类型的类型系统的上下文中，我们可以区分正确类型、类型 like Intor List[Int]from 一阶类型 likeList和更高类型的类型like Functoror Monad（抽象类型的类型，抽象类型）。

  另一方面，Java 的类型系统不支持种类，因此没有“更高种类”的类型。

  所以这必须在支持类型系统的背景下看到。

• 在 Scala 的情况下，您经常会看到类型构造函数的示例，例如

   trait Iterable[A, Container[_]]
  

  标题为“高级类型”，例如在Scala 中为通用程序员，第 4.3 节

  这有时会产生误导，因为许多人将其Container称为更高级的类型而不是Iterable，但更准确的是，

  Container此处使用更高种类（高阶）类型的as 类型构造函数参数Iterable。

回答by Jon Purdy

The kindof ordinary types like Intand Char, whose instances are values, is *. The kind of unary type constructors like Maybeis * -> *; binary type constructors like Eitherhave (curried) kind * -> * -> *, and so on. You can view types like Maybeand Eitheras type-level functions: they take one or more types, and return a type.

该种普通类型，如Int和Char，其实例是价值观，是*。像这样的一元类型构造函数Maybe是* -> *; 二进制类型构造函数，如Eitherhave ( curried) kind* -> * -> *等。您可以将类型视为Maybe和Either类型级函数：它们采用一种或多种类型，并返回一种类型。

A function is higher-orderif it has an ordergreater than 1, where the order is (informally) the nesting depth, to the left, of function arrows:

如果函数的阶数大于 1，则该函数是高阶函数，其中阶数（非正式地）是函数箭头左侧的嵌套深度：

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

• 订单 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

So, long story short, a higher-kindedtype is just a type-level higher-order function.

因此，长话短说，高级类型只是类型级别的高阶函数。

• Order 0: Int :: *
• Order 1: Maybe :: * -> *
• Order 2: Functor :: (* -> *) -> Constraint—higher-kinded: converts unary type constructors to typeclass constraints

• 订单 0： Int :: *
• 订单 1： Maybe :: * -> *
• 顺序 2：-- Functor :: (* -> *) -> Constrainthigher-kinded：将一元类型构造函数转换为类型类约束

回答by Landei

I would say: A higher kinded type abstracts overa type constructor. E.g. consider

我会说：一个更高级的类型抽象了一个类型构造函数。例如考虑

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

Here Functoris a "higher kinded type" (as used in the "Generics of a Higher Kind" paper). It is not a concrete ("first-order") type constructor like List(which abstracts over proper types only). It abstracts over all unary ("first-order") type constructors (as denoted with F[_]).

这Functor是一个“高级类型”（如“高级类型的泛型”论文中使用的那样）。它不是一个具体的（“一阶”）类型构造函数List（它仅对正确类型进行抽象）。它抽象了所有一元（“一阶”）类型构造函数（用 表示F[_]）。

Or to put it in another way: In Java, we have clearly type constructors (e.g. List<T>), but we have no "higher kinded types", because we can't abstract over them (e.g. we can't write the Functorinterface defined above - at least not directly).

或者换句话说：在 Java 中，我们有明确的类型构造函数（例如List<T>），但我们没有“高级类型”，因为我们无法对它们进行抽象（例如，我们无法编写Functor上面定义的接口）至少不是直接的）。

The term "higher order (type constructor) polymorphism" is used to describe systems that support "higher kinded types".

术语“高阶（类型构造函数）多态性”用于描述支持“高级类型”的系统。