在进入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 年代初)，并希望通过添加对泛型编程的支持来增强用户的能力。
您希望用户能够为其类定义泛型协定。例如，可合并类的协定。
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并保持brothermutable(不要使用final)。
Human h1 = new Human(null);
Human h2 = new Human(null);
h1.brother = h2;
h2.brother = h1;
但是 Scala 中的scala.collection.immutable.List(以及上面创建的Tree)数据结构与此非常相似。我们不喜欢null和mutability.
这在 Scala 中是可能的，因为支持type parameter variance和称为Nothing的特殊bottom type。
现在，让我们谈谈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以避免同伴对象引起的混淆。
这里
MyListkind是F[+A].
MyConskindF[+A].
MyNilkind是A.
MyList没有对应的type，但它有一个对应的类MyList。
MyCons没有对应的type，但它有一个对应的类MyCons。
MyNil有相应的typeMyNil和相应的类MyNil。
这些相应的type(仅在大多数语言的编译时可用)和class(在运行时存在)在创建时绑定到variables。
在val l: MyCons[Int] = new MyCons(1, new MyNil)中，l将具有类型MyCons[Int]和运行时类MyCons(这将是Class[_ <: MyCons[Int]]的实例)。
但是，在val l: MyList[Int] = new MyCons(1, new MyNil)中，l将具有类型MyList[Int]和运行时类MyCons(这将是Class[_ <: MyList[Int]]的一个实例)。
现在，我们来谈谈实际的recursive types？我们之前说过，递归类型如下所示，
trait Mergeable[+A]
class Abc extends Mergeable[Abc]
但是说上面是递归类型是错误的。更准确地说，Mergeable是一种可能导致recursive类型的kind。
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]
在这里，kindFruit是F[A <: iw$Fruit[A]].我们正在A上添加一个上限，即A必须sub-typeFruit[A](这是一个F)。这就是F-Bound这个名字的由来。
以下是F-Bound和recursive。
trait Fruit[+A <: Fruit[A]]
class Apple extends Fruit[Apple]
在这里，Fruitkind是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具有递归生成evidences的能力，以便在这些recursive types中type of any depth。
所以，如果你有代码
val f: Fruit[Fruit[Fruit[Fruit[Apple]]]] = new Apple
只有这样，编译器才需要"思考"这种类型的Fruit[Fruit[Fruit[Fruit[Apple]]]]并将其与类型Apple进行比较。
然后，它将能够使用类型关系Apple <: Fruit[Apple](由继承提供)和任何T2 <: T1的Fruit[T2] <: Fruit[T1](由实物Fruit[A]中A的协方差提供)生成Apple <:< Fruit[Fruit[Fruit[Fruit[Apple]]]]证据。因此，上面的代码将成功type-check.
万一，如果这个implicit evidence generation以某种方式遇到循环，它实际上不会成为问题，因为这已经在隐式解析/生成规则中得到了处理。
如果您查看 https://www.scala-lang.org/files/archive/spec/2.13/07-implicits.html 的隐式解析规则，您会发现以下内容
为了防止无限扩展，例如上面的魔术示例，编译器会跟踪当前正在搜索隐式参数的"开放隐式类型"堆栈。每当搜索 TT 类型的隐式参数时，TT 都会添加到与生成它的隐式定义配对的堆栈中，以及是否需要满足按名称的隐式参数。一旦搜索隐式参数肯定失败或成功，该类型就会从堆栈中删除。每次将类型添加到堆栈时，都会根据由同一隐式定义生成的现有条目进行检查，然后，
- 如果它等效于堆栈上已有的某种类型，并且该条目和堆栈顶部之间有一个按名称参数。在这种情况下，对该类型的搜索将立即成功，并且隐式参数将编译为对找到的参数的递归引用。如果尚未添加该参数，则会将其作为条目添加到合成隐式字典中。
- 否则，如果类型的核心主导堆栈上已有的类型的核心，则说隐式扩展会发散，对该类型的搜索会立即失败。
- 否则，它将被添加到与生成它的隐式定义配对的堆栈中。隐式解决方案继续使用该定义的隐式参数(如果有)。
在这里，TT的核心类型是 TT，扩展了别名，删除了顶级类型注释和细化，并用其上限替换了顶级存在绑定变量。
如果 TT 等价于 UU，或者 TT 和 UU 的顶级类型构造函数具有公共元素且 TT 比 UU 复杂且 TT 和 UU 的覆盖集相等，则核心类型 TT 主导类型 UU。
因此，当 Scala 编译器在隐式构建搜索中找到循环时，它将选择该约束并避免进入无限循环。
与其从递归的角度思考，也许纯粹从量化和边界的角度来看待它可能会有所帮助。例如，让我们解释
trait Container[A]
如说
trait Container[A >: Nothing <: Any]
也就是说，类型构造函数Container接受所有类型A作为参数。由于它采用所有类型，因此它也将采用我们尚未定义的类型Contained，因为无论我们定义什么，它都必须在Nothing和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 有界多态性用于面向对象编程调用
class Point(val x: Double, val y: Double) {
def move(t: (Double, Double)): Point
def equal(p: Point): Boolean
}
"递归类型"，因为Point声明获取和返回Point值的计算。
我是这样看的：
-
首先，您将创建一个类型函数
Container[_]该函数可应用于任何类型的A。请注意，A和Container[A]是两种不同的类型。 -
接下来，您将创建一个新的类型
Contained。在这一点上，Contained只是一个标签。 -
最后，你告诉 Scala，
Contained将扩展另一种类型：Container[Contained]。
使用extends会产生多种后果，例如：
- 您可以免费获得自动转换
Contained => Container[Contained]