Scala中样例类能否包含自身值？Tree自引用节点及编译保证探讨

问题描述 #

给定Scala中Tree枚举的定义如下：

enum Tree
  case Node(left: Tree, right:Tree)
  case Leaf

核心问题包括：

• 是否可以创建一个Node类型的值n，使得n.left == n 或 n.right == n？已知val n:Node = Node(n,n)无法正常工作。
• 是否存在编译时保证，此类循环引用的节点绝对无法创建？
• 对于所有样例类A，是否存在通用保证——即不存在任何a:A使得a.a == a成立？

补充背景：提问者需要判断一组Tree实例是否构成结构良好的单树，曾希望检查该集合中是否存在指向自身的Node节点。

回答 #

1. 循环引用的Node实例是可以创建的 #

直接写val n:Node = Node(n,n)不行是因为初始化顺序问题——n还没创建完成就被当作参数传给Node构造器，会触发未初始化错误。但通过惰性初始化或者先声明后赋值的方式，完全可以创建出循环引用的节点：

// 方式1：使用lazy val延迟初始化
lazy val n: Tree.Node = Tree.Node(n, Tree.Leaf)
// 此时n.left == n 成立

// 方式2：使用var先占位再赋值
var n: Tree.Node = null
n = Tree.Node(n, Tree.Leaf)
// 同样满足n.left == n

2. 不存在编译时禁止此类值的保证 #

Scala的类型系统不做运行时循环引用的检查，编译阶段只会验证语法合法性，不会识别你是否会在运行时构造出循环引用的实例。也就是说，编译时允许你写出能产生循环引用的代码，只要语法正确。

3. 所有样例类都没有这种通用保证 #

任何样例类都可以通过类似的方式创建循环引用的实例：

case class A(a: A)
// 用lazy val创建循环引用的实例
lazy val a: A = A(a)
// 此时a.a == a 成立

场景建议 #

如果你要验证Tree实例是否为结构良好的单树（无循环、无共享子树），必须在运行时做循环检测——比如采用深度优先遍历（DFS），维护一个已访问节点的集合，遍历过程中如果遇到已存在的节点，就说明存在循环引用。

内容的提问来源于stack exchange，提问作者rau