Maa*_*mon 4 scala 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的。kindtypeclass
让我们首先解决recursive type. 有时人们误用recursive type为实际上意味着这type对应于递归包含自身的数据结构。
以下Tree是 arecursive data strcuture但不是 a recursive type,
trait Tree[+A]\n\ncase class NonEmptyNode[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]\ncase object EmptyNode extends Tree[Nothing]\n然而，像下面这样的东西不是 arecursive data strcuture而是 it\'s a recursive type。
trait Mergeable[+A]\n\nclass A(val i: Int) extends Mergeable[A]\n有趣的是，这也与许多现代语言的一些有争议的特征的“重要性”有关 -null和mutability。
因此，假设您是 Java 语言的设计者之一（早在 2000 年代初），并且希望通过添加对泛型编程的支持来增强用户的能力。
\n您希望您的用户能够为其类定义通用契约。例如，可合并类的合同。
\npublic abstract class Mergable<A> {\n public A merge(A other)\n}\n这完全没问题。但是，这也为以下内容打开了大门
\npublic abstract class HasBrother<A> {\n public A brother;\n}\n\npublic class Human extends HasBrother<Human> {\n public Human brother;\n\n public Human(Human brother) {\n this.brother = brother;\n }\n}\n这就是问题开始的地方。您将如何创建 的实例Human？
但他们有一个“很棒的”解决方案。只需使用null并保留brother mutable（不要使用final）。
Human h1 = new Human(null);\nHuman h2 = new Human(null);\n\nh1.brother = h2;\nh2.brother = h1;\n但是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为例，
public abstract class Mergable<A> {\n public A merge(A other)\n}\n注意::我故意不使用case object或case class避免伴随对象引起的混乱。
这里，
\nkind对于MyList是F[+A].
kind对于MyCons是F[+A].
kind对于MyNil是A.
MyList没有对应的type，但是有对应的类MyList。
MyCons没有对应的type，但是有对应的类MyCons。
MyNil有相应的type MyNil和相应的类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]\n\nclass Abc extends Mergeable[Abc]\n但说上面是递归类型有点错误。更准确的说法是，Mergeable它kind可以产生recursive类型。
val abc: Abc = new Abc\n// type - Abc; class - Abc (Class[_ <: Abc])\n\nval abc: Mergeable[Abc] = new Abc\n// type - Mergeable[Abc]; class - Abc (Class[_ <: Mergeable[Abc]])\n\nval abc: Mergeable[Mergeable[Abc]] = new Abc\n// type - Mergeable[Mergeable[Abc]]; class - Abc (Class[_ <: Mergeable[Mergeable[Abc]]])\n\n// ... and so on to Infinity\n但是，如果我们删除 make 那个A不变式，那么这kind不会导致recursive types。
trait Mergeable[A]\n\nclass Abc extends Mergeable[Abc]\n\nval abc: Abc = new Abc\n// type - Abc; class - Abc (Class[_ <: Abc])\n\nval abc: Mergeable[Abc] = new Abc\n// type - Mergeable[Abc]; class - Abc (Class[_ <: Abc])\n\nval abc: Mergeable[Mergeable[Abc]] = new Abc\n// ^\n// error: type mismatch;\n// found : Abc\n// required: Mergeable[Mergeable[Abc]]\n// Note: Abc <: Mergeable[Abc] (and Abc <: Mergeable[Abc]), but trait Mergeable is invariant in type A.\n// You may wish to define A as +A instead. (SLS 4.5)\n\n这些recursive types不同于F-Bound polymorphism.
以下是F-Bound但不是recursive
public abstract class HasBrother<A> {\n public A brother;\n}\n\npublic class Human extends HasBrother<Human> {\n public Human brother;\n\n public Human(Human brother) {\n this.brother = brother;\n }\n}\n这里，kindofFruit是F[A <: iw$Fruit[A]]。我们添加了一个上限，A表示A必须是sub-type（Fruit[A]这是一个F）。这就是名字的F-Bound由来。
以下是F-Bound和recursive。
Human h1 = new Human(null);\nHuman h2 = new Human(null);\n\nh1.brother = h2;\nh2.brother = h1;\n这里，kindofFruit是F[+A <: iw$Fruit[A]]。
现在，我可以指定任意多个递归深度的类型Apple。
val f: Apple = new Apple\n// type - Apple; class - Apple (Class[_ <: Apple])\n\nval f: Fruit[Apple] = new Apple\n// type - Fruit[Apple]; class - Apple (Class[_ <: Fruit[Apple]])\n\nval f: Fruit[Fruit[Apple]] = new Apple\n// type - Fruit[Fruit[Apple]]; class - Apple (Class[_ <: Fruite[Fruit[Apple]]])\n\n// ... and so on to Infinity\n任何不支持的语言都higher kinds不能有F-bound types。
现在，我们终于可以解答您对无限循环的疑问了。
\n就像我们之前说过的，atype可以被认为是像 alabel一样用来指代某个合约。所以，这eager looping实际上并没有发生。
（我认为）Scala 编译器使用implicit evidences( =:=,<:<约束) 进行类型比较。这些evidences是由编译器使用type boundson延迟生成的type parameters。因此， the具有递归生成其中的forcompiler的能力evidencestype of any depthrecursive types。
所以，如果你有代码
\nval f: Fruit[Fruit[Fruit[Fruit[Apple]]]] = new Apple\n只有这样，编译器才需要“思考”此类型Fruit[Fruit[Fruit[Fruit[Apple]]]]及其与 type 的比较Apple。
然后，它将能够Apple <:< Fruit[Fruit[Fruit[Fruit[Apple]]]]通过使用类型关系Apple <: Fruit[Apple]（由继承提供）和Fruit[T2] <: Fruit[T1]for any （由in kindT2 <: T1的协方差提供）来生成证据。这样上面的代码就会成功。AFruit[A]type-check
万一，如果这implicit evidence generation以某种方式遇到循环，它实际上不会成为问题，因为这已经在隐式解析/生成规则中得到了处理。
如果您查看https://www.scala-lang.org/files/archive/spec/2.13/07-implicits.html上的隐式解析规则，您会发现以下内容
\n\n\n为了防止无限扩展，例如上面的神奇示例，编译器跟踪当前正在搜索隐式参数的 \xe2\x80\x9copen 隐式类型\xe2\x80\x9d 的堆栈。每当搜索类型 TT 的隐式参数时，TT 都会添加到与生成它的隐式定义配对的堆栈中，以及是否需要它满足按名称隐式参数。一旦搜索隐式参数肯定失败或成功，该类型就会从堆栈中删除。每次将类型添加到堆栈时，都会根据相同隐式定义生成的现有条目进行检查，然后，
\n\n
\n- 如果它相当于堆栈中已经存在的某种类型，并且该条目和堆栈顶部之间有一个按名称参数。在这种情况下，对该类型的搜索立即成功，并且隐式参数被编译为对找到的参数的递归引用。如果尚未添加该参数，则将其作为条目添加到合成隐式字典中。
\n- 否则，如果该类型的核心支配了堆栈上已有类型的核心，则隐式扩展被称为发散，并且对该类型的搜索立即失败。
\n- 否则它会被添加到与生成它的隐式定义配对的堆栈中。隐式解析继续使用该定义的隐式参数（如果有）。
\n这里，TT 的核心类型是扩展了别名的 TT，删除了顶级类型注释和细化，并用其上限替换了顶级存在绑定变量的出现。
\n如果 TT 等价于 UU，或者如果 TT 和 UU 的顶级类型构造函数具有共同元素并且 TT 比 UU 更复杂并且 TT 和 UU 的覆盖集相等，则核心类型 TT 支配类型 UU。
\n
因此，当 Scala 编译器在隐式约束搜索中发现循环时，它将选择该约束并避免进入无限循环。
\n