在理解 F-Bounded Polymorphism 的道路上
On the road to understanding F-Bounded Polymorphism
在谈到 F 有界多态性之前，有一个支撑它的结构，我已经很难理解了。
trait Container[A]
trait Contained extends Container[Contained]
java中也存在的面向对象的构造似乎是一件微不足道的事情，这已经让我有些困惑了。
问题是，当我看到这个 trait Contained extends Container[Contained] 时，我觉得它就像一个无限类型的递归。
当我们定义类型 List 时，即使我们有 Cons[A](a:A, tail:List[A])，我们也有 case object Nil。所以递归可以以Nil结束。
但是在这里，我不明白我们怎么不在无限递归中？为什么有效。
有人可以帮我解惑吗？或者是否有任何文档、博客或任何可以解释其工作原理或实现方式的内容。
我认为您的问题是由于混淆了术语 recursive type 的含义以及 kind、type 和 class 之间的区别。
让我们首先解决 recursive type。有时人们误用 recursive type 实际上意味着这个 type 对应于递归包含自身的数据结构。
Tree 之后是 recursive data strcuture 但不是 recursive type、
trait Tree[+A]
case class NonEmptyNode[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]
case object EmptyNode extends Tree[Nothing]
而下面的内容不是 recursive data strcuture，而是 recursive type。
trait Mergeable[+A]
class A(val i: Int) extends Mergeable[A]
有趣的是，这也与许多现代语言的一些有争议的特征的“重要性”有关 - null 和 mutability。
因此，假设您是 Java 语言的设计者之一（早在 2000 年代初），并且希望通过添加对通用编程的支持来增强您的用户的能力。
您希望您的用户能够为其 classes 定义通用合同。例如，可合并 classes.
的合约
public abstract class Mergable<A> {
public A merge(A other)
}
非常好。但是，这也为以下内容打开了大门
public abstract class HasBrother<A> {
public A brother;
}
public class Human extends HasBrother<Human> {
public Human brother;
public Human(Human brother) {
this.brother = brother;
}
}
这就是问题开始的地方。您将如何创建 Human 的实例？
但是他们有一个“很棒”的解决方案。只需使用 null 并保留 brother mutable（不要使用 final）。
Human h1 = new Human(null);
Human h2 = new Human(null);
h1.brother = h2;
h2.brother = h1;
但是 scala.collection.immutable.List（以及上面创建的 Tree）Scala 中的数据结构与此非常相似。我们不喜欢 null 和 mutability.
这在 Scala 中是可能的，只是因为支持 type parameter variance 和特殊的 bottom type 称为 Nothing。
现在，让我们谈谈 kind、type 和 class。
type 可以认为是定义的 contract.
class可以认为是上述contract.
的运行次实现
kind 实际上是一个 type 构造函数。它需要一个 type parameter 来构建 type.
下面以List为例，
trait MyList[+A]
class MyNil extends MyList[Nothing]
class MyCons[A](val value: A, val tail: MyList[A]) extends MyList[A]
注意 :: 我有意不使用 case object 或 case class 以避免伴随对象引起的混淆。
这里，
kind 对于 MyList 是 F[+A].
kind 对于 MyCons 是 F[+A].
kind 对于 MyNil 是 A.
MyList没有对应的type，但是有对应的class MyList.
MyCons没有对应的type，但是有对应的class MyCons.
MyNil有一个对应的typeMyNil和一个对应的classMyNil.
这些对应的 type（在大多数语言中仅在编译时可用）和 class（在 运行 时存在）绑定到 variables 时它们已创建。
在 val l: MyCons[Int] = new MyCons(1, new MyNil) 中，l 将具有类型 MyCons[Int] 和 运行time class MyCons（这将是 Class[_ <: MyCons[Int]]).
但是，在 val l: MyList[Int] = new MyCons(1, new MyNil) 中，l 将具有类型 MyList[Int] 和 运行-时间 class MyCons（这将是一个Class[_ <: MyList[Int]]).
的实例
现在，让我们谈谈实际的 recursive types？我们之前说过递归类型如下所示，
trait Mergeable[+A]
class Abc extends Mergeable[Abc]
但是说上面是递归类型有点不对。更准确地说，Mergeable 是一个 kind，它可以产生 recursive 类型。
val abc: Abc = new Abc
// type - Abc; class - Abc (Class[_ <: Abc])
val abc: Mergeable[Abc] = new Abc
// type - Mergeable[Abc]; class - Abc (Class[_ <: Mergeable[Abc]])
val abc: Mergeable[Mergeable[Abc]] = new Abc
// type - Mergeable[Mergeable[Abc]]; class - Abc (Class[_ <: Mergeable[Mergeable[Abc]]])
// ... and so on to Infinity
但是，如果我们删除 A 不变量，那么 kind 就不会导致 recursive types.
trait Mergeable[A]
class Abc extends Mergeable[Abc]
val abc: Abc = new Abc
// type - Abc; class - Abc (Class[_ <: Abc])
val abc: Mergeable[Abc] = new Abc
// type - Mergeable[Abc]; class - Abc (Class[_ <: Abc])
val abc: Mergeable[Mergeable[Abc]] = new Abc
// ^
// error: type mismatch;
// found : Abc
// required: Mergeable[Mergeable[Abc]]
// Note: Abc <: Mergeable[Abc] (and Abc <: Mergeable[Abc]), but trait Mergeable is invariant in type A.
// You may wish to define A as +A instead. (SLS 4.5)
这些recursive types不同于F-Bound polymorphism。
以下是F-Bound但不是recursive
trait Fruit[A <: Fruit[A]]
class Apple extends Fruit[Apple]
这里，Fruit的kind是F[A <: iw$Fruit[A]]。我们在 A 上添加了一个上限，表示 A 必须是 Fruit[A] 的 sub-type（这是一个 F）。这就是名称 F-Bound 的来源。
以下是F-Bound和recursive。
trait Fruit[+A <: Fruit[A]]
class Apple extends Fruit[Apple]
这里，Fruit的kind是F[+A <: iw$Fruit[A]]。
现在，我可以在许多递归深度指定任何 Apple 的类型。
val f: Apple = new Apple
// type - Apple; class - Apple (Class[_ <: Apple])
val f: Fruit[Apple] = new Apple
// type - Fruit[Apple]; class - Apple (Class[_ <: Fruit[Apple]])
val f: Fruit[Fruit[Apple]] = new Apple
// type - Fruit[Fruit[Apple]]; class - Apple (Class[_ <: Fruite[Fruit[Apple]]])
// ... and so on to Infinity
任何不支持higher kinds的语言都不能有F-bound types.
现在，我们终于可以解决您对无限循环的疑惑了。
正如我们之前所说，一个type可以被认为是一个label，用来指代某个合约。所以，eager looping 实际上并没有发生。
（我认为）Scala 编译器使用 implicit evidences（=:=、<:< 约束）进行类型比较。这些 evidences 是由编译器使用 type parameters 上的 type bounds 延迟生成的。因此，compiler 具有为 type of any depth 在这些 recursive types.
中递归生成 evidences 的能力
所以，如果你有代码
val f: Fruit[Fruit[Fruit[Fruit[Apple]]]] = new Apple
只有这样编译器才会要求“考虑”这个类型 Fruit[Fruit[Fruit[Fruit[Apple]]]] 并且它与类型 Apple.
的比较
然后它将能够通过使用类型关系 Apple <: Fruit[Apple]（由继承提供）和 Fruit[T2] <: Fruit[T1] 为任何 T2 <: T1（由 co 提供）生成证据 Apple <:< Fruit[Fruit[Fruit[Fruit[Apple]]]] -实物 A 的差异 Fruit[A])。因此上面的代码将成功 type-check.
万一 implicit evidence generation 以某种方式遇到循环，这实际上不会成为问题，因为这已经在隐式 resolution/generation 规则中得到处理。
如果您查看 https://www.scala-lang.org/files/archive/spec/2.13/07-implicits.html 处的隐式解析规则，您会发现以下内容
To prevent infinite expansions, such as the magic example above, the compiler keeps track of a stack of “open implicit types” for which implicit arguments are currently being searched. Whenever an implicit argument for type TT is searched, TT is added to the stack paired with the implicit definition which produces it, and whether it was required to satisfy a by-name implicit argument or not. The type is removed from the stack once the search for the implicit argument either definitely fails or succeeds. Everytime a type is about to be added to the stack, it is checked against existing entries which were produced by the same implicit definition and then,
- if it is equivalent to some type which is already on the stack and there is a by-name argument between that entry and the top of the stack. In this case the search for that type succeeds immediately and the implicit argument is compiled as a recursive reference to the found argument. That argument is added as an entry in the synthesized implicit dictionary if it has not already been added.
- otherwise if the core of the type dominates the core of a type already on the stack, then the implicit expansion is said to diverge and the search for that type fails immediately.
- otherwise it is added to the stack paired with the implicit definition which produces it. Implicit resolution continues with the implicit arguments of that definition (if any).
Here, the core type of TT is TT with aliases expanded, top-level type annotations and refinements removed, and occurrences of top-level existentially bound variables replaced by their upper bounds.
A core type TT dominates a type UU if TT is equivalent to UU, or if the top-level type constructors of TT and UU have a common element and TT is more complex than UU and the covering sets of TT and UU are equal.
因此，当 Scala 编译器在隐式约束搜索中发现循环时，它将选择该约束并避免进入无限循环。
与其从递归的角度思考，也许纯粹从量化和边界的角度来看它可能会有所帮助。例如让我们解释
trait Container[A]
俗话说
trait Container[A >: Nothing <: Any]
也就是说，类型构造函数 Container 接受所有类型 A 作为参数。由于它采用 所有 类型，因此它也将采用我们尚未定义的类型 Contained，因为无论我们定义什么，它都必须在 [=20= 之间的某处结束] 和 Any，因此，不考虑递归，我们可以承认以下是合法的
trait Contained extends Container[Contained]
接下来让我们收紧其中一个界限，这样
trait Container[A <: Container[A]]
被解释为
trait Container[A >: Nothing <: Container[A]]
也就是说，类型构造函数 Container 接受 Nothing 和 Container[A] 之间的所有类型 A 作为参数。现在我们尚未定义的类型 A = Contained 最终确实会成为 Container[A] 的子类型，因为这是我们用
明确告诉编译器的内容
trait Contained extends Container[Contained]
所以不用过多考虑递归我们可以承认上面是合法的。
作为旁注，关于术语“递归类型”，与计算机科学中的许多术语一样，我怀疑是否存在普遍接受的定义究竟意味着什么。例如论文F-Bounded Polymorphism for Object-Oriented Programming调用
class Point(val x: Double, val y: Double) {
def move(t: (Double, Double)): Point
def equal(p: Point): Boolean
}
“递归类型”，因为 Point 声明采用 return Point 值的计算。
我是这样看的：
首先，您要创建一个类型函数 Container[_]，它可以应用于任何类型 A。请注意 A 和 Container[A] 是两种不同的类型。
接下来您将创建一个新类型 Contained。此时Contained只是一个标签。
最后，您要告诉 Scala Contained 将扩展另一种类型：Container[Contained].
使用 extends 有几个后果，例如：
- 您可以免费获得一次自动转换
Contained => Container[Contained]
在谈到 F 有界多态性之前，有一个支撑它的结构，我已经很难理解了。
trait Container[A]
trait Contained extends Container[Contained]
java中也存在的面向对象的构造似乎是一件微不足道的事情，这已经让我有些困惑了。
问题是，当我看到这个 trait Contained extends Container[Contained] 时，我觉得它就像一个无限类型的递归。
当我们定义类型 List 时，即使我们有 Cons[A](a:A, tail:List[A])，我们也有 case object Nil。所以递归可以以Nil结束。
但是在这里，我不明白我们怎么不在无限递归中？为什么有效。
有人可以帮我解惑吗？或者是否有任何文档、博客或任何可以解释其工作原理或实现方式的内容。
我认为您的问题是由于混淆了术语 recursive type 的含义以及 kind、type 和 class 之间的区别。
让我们首先解决 recursive type。有时人们误用 recursive type 实际上意味着这个 type 对应于递归包含自身的数据结构。
Tree 之后是 recursive data strcuture 但不是 recursive type、
trait Tree[+A]
case class NonEmptyNode[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]
case object EmptyNode extends Tree[Nothing]
而下面的内容不是 recursive data strcuture，而是 recursive type。
trait Mergeable[+A]
class A(val i: Int) extends Mergeable[A]
有趣的是，这也与许多现代语言的一些有争议的特征的“重要性”有关 - null 和 mutability。
因此，假设您是 Java 语言的设计者之一（早在 2000 年代初），并且希望通过添加对通用编程的支持来增强您的用户的能力。
您希望您的用户能够为其 classes 定义通用合同。例如，可合并 classes.
的合约public abstract class Mergable<A> {
public A merge(A other)
}
非常好。但是，这也为以下内容打开了大门
public abstract class HasBrother<A> {
public A brother;
}
public class Human extends HasBrother<Human> {
public Human brother;
public Human(Human brother) {
this.brother = brother;
}
}
这就是问题开始的地方。您将如何创建 Human 的实例？
但是他们有一个“很棒”的解决方案。只需使用 null 并保留 brother mutable（不要使用 final）。
Human h1 = new Human(null);
Human h2 = new Human(null);
h1.brother = h2;
h2.brother = h1;
但是 scala.collection.immutable.List（以及上面创建的 Tree）Scala 中的数据结构与此非常相似。我们不喜欢 null 和 mutability.
这在 Scala 中是可能的，只是因为支持 type parameter variance 和特殊的 bottom type 称为 Nothing。
现在，让我们谈谈 kind、type 和 class。
type 可以认为是定义的 contract.
class可以认为是上述contract.
kind 实际上是一个 type 构造函数。它需要一个 type parameter 来构建 type.
下面以List为例，
trait MyList[+A]
class MyNil extends MyList[Nothing]
class MyCons[A](val value: A, val tail: MyList[A]) extends MyList[A]
注意 :: 我有意不使用 case object 或 case class 以避免伴随对象引起的混淆。
这里，
kind 对于 MyList 是 F[+A].
kind 对于 MyCons 是 F[+A].
kind 对于 MyNil 是 A.
MyList没有对应的type，但是有对应的class MyList.
MyCons没有对应的type，但是有对应的class MyCons.
MyNil有一个对应的typeMyNil和一个对应的classMyNil.
这些对应的 type（在大多数语言中仅在编译时可用）和 class（在 运行 时存在）绑定到 variables 时它们已创建。
在 val l: MyCons[Int] = new MyCons(1, new MyNil) 中，l 将具有类型 MyCons[Int] 和 运行time class MyCons（这将是 Class[_ <: MyCons[Int]]).
但是，在 val l: MyList[Int] = new MyCons(1, new MyNil) 中，l 将具有类型 MyList[Int] 和 运行-时间 class MyCons（这将是一个Class[_ <: MyList[Int]]).
现在，让我们谈谈实际的 recursive types？我们之前说过递归类型如下所示，
trait Mergeable[+A]
class Abc extends Mergeable[Abc]
但是说上面是递归类型有点不对。更准确地说，Mergeable 是一个 kind，它可以产生 recursive 类型。
val abc: Abc = new Abc
// type - Abc; class - Abc (Class[_ <: Abc])
val abc: Mergeable[Abc] = new Abc
// type - Mergeable[Abc]; class - Abc (Class[_ <: Mergeable[Abc]])
val abc: Mergeable[Mergeable[Abc]] = new Abc
// type - Mergeable[Mergeable[Abc]]; class - Abc (Class[_ <: Mergeable[Mergeable[Abc]]])
// ... and so on to Infinity
但是，如果我们删除 A 不变量，那么 kind 就不会导致 recursive types.
trait Mergeable[A]
class Abc extends Mergeable[Abc]
val abc: Abc = new Abc
// type - Abc; class - Abc (Class[_ <: Abc])
val abc: Mergeable[Abc] = new Abc
// type - Mergeable[Abc]; class - Abc (Class[_ <: Abc])
val abc: Mergeable[Mergeable[Abc]] = new Abc
// ^
// error: type mismatch;
// found : Abc
// required: Mergeable[Mergeable[Abc]]
// Note: Abc <: Mergeable[Abc] (and Abc <: Mergeable[Abc]), but trait Mergeable is invariant in type A.
// You may wish to define A as +A instead. (SLS 4.5)
这些recursive types不同于F-Bound polymorphism。
以下是F-Bound但不是recursive
trait Fruit[A <: Fruit[A]]
class Apple extends Fruit[Apple]
这里，Fruit的kind是F[A <: iw$Fruit[A]]。我们在 A 上添加了一个上限，表示 A 必须是 Fruit[A] 的 sub-type（这是一个 F）。这就是名称 F-Bound 的来源。
以下是F-Bound和recursive。
trait Fruit[+A <: Fruit[A]]
class Apple extends Fruit[Apple]
这里，Fruit的kind是F[+A <: iw$Fruit[A]]。
现在，我可以在许多递归深度指定任何 Apple 的类型。
val f: Apple = new Apple
// type - Apple; class - Apple (Class[_ <: Apple])
val f: Fruit[Apple] = new Apple
// type - Fruit[Apple]; class - Apple (Class[_ <: Fruit[Apple]])
val f: Fruit[Fruit[Apple]] = new Apple
// type - Fruit[Fruit[Apple]]; class - Apple (Class[_ <: Fruite[Fruit[Apple]]])
// ... and so on to Infinity
任何不支持higher kinds的语言都不能有F-bound types.
现在，我们终于可以解决您对无限循环的疑惑了。
正如我们之前所说，一个type可以被认为是一个label，用来指代某个合约。所以，eager looping 实际上并没有发生。
（我认为）Scala 编译器使用 implicit evidences（=:=、<:< 约束）进行类型比较。这些 evidences 是由编译器使用 type parameters 上的 type bounds 延迟生成的。因此，compiler 具有为 type of any depth 在这些 recursive types.
evidences 的能力
所以，如果你有代码
val f: Fruit[Fruit[Fruit[Fruit[Apple]]]] = new Apple
只有这样编译器才会要求“考虑”这个类型 Fruit[Fruit[Fruit[Fruit[Apple]]]] 并且它与类型 Apple.
然后它将能够通过使用类型关系 Apple <: Fruit[Apple]（由继承提供）和 Fruit[T2] <: Fruit[T1] 为任何 T2 <: T1（由 co 提供）生成证据 Apple <:< Fruit[Fruit[Fruit[Fruit[Apple]]]] -实物 A 的差异 Fruit[A])。因此上面的代码将成功 type-check.
万一 implicit evidence generation 以某种方式遇到循环，这实际上不会成为问题，因为这已经在隐式 resolution/generation 规则中得到处理。
如果您查看 https://www.scala-lang.org/files/archive/spec/2.13/07-implicits.html 处的隐式解析规则，您会发现以下内容
To prevent infinite expansions, such as the magic example above, the compiler keeps track of a stack of “open implicit types” for which implicit arguments are currently being searched. Whenever an implicit argument for type TT is searched, TT is added to the stack paired with the implicit definition which produces it, and whether it was required to satisfy a by-name implicit argument or not. The type is removed from the stack once the search for the implicit argument either definitely fails or succeeds. Everytime a type is about to be added to the stack, it is checked against existing entries which were produced by the same implicit definition and then,
- if it is equivalent to some type which is already on the stack and there is a by-name argument between that entry and the top of the stack. In this case the search for that type succeeds immediately and the implicit argument is compiled as a recursive reference to the found argument. That argument is added as an entry in the synthesized implicit dictionary if it has not already been added.
- otherwise if the core of the type dominates the core of a type already on the stack, then the implicit expansion is said to diverge and the search for that type fails immediately.
- otherwise it is added to the stack paired with the implicit definition which produces it. Implicit resolution continues with the implicit arguments of that definition (if any).
Here, the core type of TT is TT with aliases expanded, top-level type annotations and refinements removed, and occurrences of top-level existentially bound variables replaced by their upper bounds.
A core type TT dominates a type UU if TT is equivalent to UU, or if the top-level type constructors of TT and UU have a common element and TT is more complex than UU and the covering sets of TT and UU are equal.
因此，当 Scala 编译器在隐式约束搜索中发现循环时，它将选择该约束并避免进入无限循环。
与其从递归的角度思考，也许纯粹从量化和边界的角度来看它可能会有所帮助。例如让我们解释
trait Container[A]
俗话说
trait Container[A >: Nothing <: Any]
也就是说，类型构造函数 Container 接受所有类型 A 作为参数。由于它采用 所有 类型，因此它也将采用我们尚未定义的类型 Contained，因为无论我们定义什么，它都必须在 [=20= 之间的某处结束] 和 Any，因此，不考虑递归，我们可以承认以下是合法的
trait Contained extends Container[Contained]
接下来让我们收紧其中一个界限，这样
trait Container[A <: Container[A]]
被解释为
trait Container[A >: Nothing <: Container[A]]
也就是说，类型构造函数 Container 接受 Nothing 和 Container[A] 之间的所有类型 A 作为参数。现在我们尚未定义的类型 A = Contained 最终确实会成为 Container[A] 的子类型，因为这是我们用
trait Contained extends Container[Contained]
所以不用过多考虑递归我们可以承认上面是合法的。
作为旁注，关于术语“递归类型”，与计算机科学中的许多术语一样，我怀疑是否存在普遍接受的定义究竟意味着什么。例如论文F-Bounded Polymorphism for Object-Oriented Programming调用
class Point(val x: Double, val y: Double) {
def move(t: (Double, Double)): Point
def equal(p: Point): Boolean
}
“递归类型”，因为 Point 声明采用 return Point 值的计算。
我是这样看的：
首先，您要创建一个类型函数
Container[_]，它可以应用于任何类型A。请注意A和Container[A]是两种不同的类型。接下来您将创建一个新类型
Contained。此时Contained只是一个标签。最后，您要告诉 Scala
Contained将扩展另一种类型：Container[Contained].
使用 extends 有几个后果，例如：
- 您可以免费获得一次自动转换
Contained => Container[Contained]