Scala 中的协变树

Question

查看 scalaz.Tree[A]，它在 A 中是不变的。我正在寻找一个多路树，我可以在

中转储层次结构的值

例如如果我的 ADT 为

trait MyThing
case object Thing1 extends MyThing
case object Thing2 extends MyThing

我想要一棵 MyThing 的树，我不能在不对 scalaz 中的 MyThing 进行强制转换的情况下使用它；

import scalaz.{Scalaz, Tree}
import Scalaz._
val tree = Thing1.asInstanceOf[MyThing].
               node(Thing2.asInstanceOf[MyThing].leaf)

这有点痛苦。

树有协变[+A]版本吗？
为什么树首先是不变的？

Answer 1

首先，我想赞同 Huw 的建议，即使用类型归属而不是使用 asInstanceOf 进行向下转换。正如 Huw 所说，如果类型层次结构中的某些内容发生变化导致强制转换无效，则使用类型归属将在编译时而不是运行时失败。对于 any upcasts 避免 asInstanceOf 也是一个好习惯。您可以使用 asInstanceOf 进行向上转型或向下转型，但仅将其用于向下转型可以轻松识别代码中的不安全转型。

回答你的两个问题——不，Scalaz 中没有协变树类型，原因在上面 Huw 链接的 pull request 中有详细讨论。起初这似乎是一个巨大的不便，但在 Scalaz 中避免非不变结构的决定与类似的设计决策有关——避免在 ADT 中使用子类型——这使得不变树等不那么痛苦。

在其他对 ADT 支持良好的语言中（例如 Haskell 和 OCaml），ADT 的叶子不是 ADT 类型的子类型，Scala 的基于子类型的实现有些不寻常使类型推断变得混乱。以下是此问题的常见示例：

scala> List(1, 2, 3).foldLeft(None)((_, i) => Some(i))
<console>:14: error: type mismatch;
 found   : Some[Int]
 required: None.type
              List(1, 2, 3).foldLeft(None)((_, i) => Some(i))
                                                     ^

因为累加器的类型是从 foldLeft 的第一个参数推断出来的，它最终是 None.type，这几乎没有用。您必须提供类型归属（或 foldLeft 的显式类型参数），这可能非常不方便。

Scalaz 试图通过推广使用不是 return ADT 叶的最具体子类型的 ADT 构造函数来解决这个问题。例如，它包括 none[A] 和 some[A](a: A) 构造函数，用于 Option return 和 Option[A].

（有关这些问题的更多讨论，请参阅我的回答here and this related question）。

对于您的情况，实施此方法可能就像编写以下内容一样简单：

val thing1: MyThing = Thing1
val thing2: MyThing = Thing2

这允许你写 thing1.node(thing2.leaf)。如果你想在这条路上走得更远，我强烈建议你看看 Argonaut's Json ADT 作为 ADT 设计的一个很好的例子，它淡化了子类型的作用。

Scala 中的协变树

Covariant Trees in Scala

scala

data-structures

tree

scalaz