3

甚至在到达 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 结束。

但是在这里，我不明白我们如何不在无限递归中？以及为什么有效。

有人可以让我对此感到困惑吗？或者，如果有任何文档、博客或任何可以解释其工作原理或实现的东西。

4

3 回答 3

4

我认为您的问题是由于对该术语的含义recursive type以及kind,type和class.

让我们先解决recursive type. 有时人们误用recursive type实际上意味着这type对应于递归包含自身的数据结构。

以下Tree是 arecursive data strcuture但不是 a 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]

然而，像 follow 这样的东西不是 arecursive 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并保留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 中的数据结构与此非常相似。而且我们不喜欢nulland mutability。

这在 Scala 中是可能的，仅由于支持type parameter variance和特殊的bottom type称为Nothing.

现在，让我们谈谈kind和。typeclass

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的，但是有对应的类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]]）。

但是， inval 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是，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

但是，如果我们删除 make that Ainvariant 那么这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]

在这里，kindofFruit是F[A <: iw$Fruit[A]]。我们正在添加一个上限A，表示A必须是sub-type（Fruit[A]这是一个F）。这就是名字的F-Bound由来。

以下是F-Bound和recursive。

trait Fruit[+A <: Fruit[A]]

class Apple extends Fruit[Apple]

在这里，kindofFruit是F[+A <: iw$Fruit[A]]。

现在，我可以Apple在许多递归深度指定 any 的类型。

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。

现在，我们终于可以解决您在考虑无限循环的问题了。

就像我们之前说的，atype可以被认为就像 alabel用来指代某个合同。所以，这eager looping实际上并没有发生。

（我认为）Scala 编译器使用implicit evidences( =:=,<:<约束) 进行类型比较。这些evidences是由编译器使用type boundson延迟生成的type parameters。因此，compiler具有递归生成这些evidencesfortype of any depth的能力recursive types。

所以，如果你有代码

val f: Fruit[Fruit[Fruit[Fruit[Apple]]]] = new Apple

只有这样，编译器才会需要“思考”这种类型Fruit[Fruit[Fruit[Fruit[Apple]]]]，并将其与 type 进行比较Apple。

然后它将能够Apple <:< Fruit[Fruit[Fruit[Fruit[Apple]]]]通过使用类型关系Apple <: Fruit[Apple]（由继承提供）和Fruit[T2] <: Fruit[T1]任何（由in kindT2 <: T1的协方差提供）来生成证据。因此上面的代码将成功。AFruit[A]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 编译器在隐式常量搜索中找到循环时，它会选择该约束并避免进入无限循环。

于 2021-09-18T22:50:46.343 回答
1

与其从递归的角度思考，也许纯粹从量化和界限的角度来看它可能会有所帮助。例如让我们解释

trait Container[A]

话说

trait Container[A >: Nothing <: Any]

也就是说，类型构造函数Container接受所有类型A作为参数。既然它接受所有类型，那么它也会接受我们尚未定义的类型，因为无论我们定义什么，它都必须在 andContained之间的某个位置结束，因此，不考虑递归，我们可以承认以下是合法的NothingAny

trait Contained extends Container[Contained]

接下来，让我们收紧其中一个边界，使得

trait Container[A <: Container[A]]

被解释为

trait Container[A >: Nothing <: Container[A]]

也就是说，类型构造函数Container接受 和 之间的所有类型作为A参数。现在我们尚未定义的类型确实最终会成为的子类型，因为这是我们明确告诉编译器的NothingContainer[A]A = ContainedContainer[A]

trait Contained extends Container[Contained]

因此，无需过多考虑递归，我们就可以承认上面是合法的。

作为旁注，关于术语“递归类型”，与计算机科学中的许多术语一样，我怀疑它的确切含义是否存在普遍接受的定义。例如，论文F-Bounded Polymorphism for Object-Oriented Programming calls

class Point(val x: Double, val y: Double) {
  def move(t: (Double, Double)): Point
  def equal(p: Point): Boolean
}

“递归类型”，因为Point声明了接受和返回Point值的计算。

于 2021-09-19T19:16:37.130 回答
0

我是这样看的：

  1. 首先，您要创建一个Container[_]可以应用于任何类型的类型函数A。请注意，A和Container[A]是两种不同的类型。

  2. 接下来，您将创建一个新类型Contained。此时Contained只是一个标签。

  3. 最后，您告诉 ScalaContained将扩展另一种类型：Container[Contained].

使用extends有几个后果，例如：

  • Contained => Container[Contained]您可以免费获得自动转换
于 2021-09-21T20:55:27.237 回答