Scala中的书面代数数据类型

Question

在Haskell中，我可以定义Tree：

data Tree a = Empty | Node a (Tree a) (Tree a)

我该如何在Scala中编写此内容？

我不确定如何在Scala中将类型参数[A]保留为Node以匹配Tree的类型a。

Answer 1

定义ADT

在Scala的“对象功能”模型中，定义一个trait来代表ADT及其所有参数。然后为每种情况定义case class或case object。类型和值参数被视为类构造函数的参数。通常，您将特征设为sealed，以便当前文件之外的任何内容都无法添加大小写。

sealed trait Tree[A]
case class Empty[A]() extends Tree[A]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

然后您可以做：

scala> Node("foo", Node("bar", Empty(), Empty()), Empty())
res2: Node[String] = Node(foo,Node(bar,Empty(),Empty()),Empty())

这很烦人，当该类不携带数据时，我们必须创建一堆新的Empty实例。在Scala中，通常的做法是将case class之类的零参数Empty替换为case object，尽管在这种情况下，这有点棘手，因为case object是单例，但是我们需要一个Empty用于每种类型的树。

[幸运的是（或不取决于您询问的人），使用协方差注释，您可以让一个case object Empty充当类型为Tree的空Nothing，这是Scala的通用子类型。由于协方差，对于所有可能的Empty，此Tree[A]现在是A的子类型：

sealed trait Tree[+A]
case object Empty extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

然后您将获得更简洁的语法：

scala> Node("foo", Node("bar", Empty, Empty), Empty)
res4: Node[String] = Node(foo,Node(bar,Empty,Empty),Empty)

事实上，这是Scala的标准库Nil关于Nil的工作方式。

在ADT上操作

要使用新的ADT，在Scala中很常见的是定义使用List关键字对其进行解构的递归函数。参见：

List

Scala通常为开发人员提供了一系列令人困惑的选项，以供您选择如何组织在ADT上运行的功能。我可以想到四种基本方法。

1）可以使其成为特征之外的独立函数：

match

如果您希望自己的API比面向对象的功能更强大，或者您的操作可能会从其他数据中产生ADT的实例，那么可能会很好。

scala> :paste
// Entering paste mode (ctrl-D to finish)

import scala.math.max
def depth[A](tree: Tree[A]): Int = tree match {
  case Empty => 0
  case Node(_, left, right) => 1 + max(depth(left), depth(right))
}

// Exiting paste mode, now interpreting.

import scala.math.max
depth: [A](tree: Tree[A])Int

scala> depth(Node("foo", Node("bar", Empty, Empty), Empty))
res5: Int = 2

通常是放置此类方法的自然场所。

2）您可以使其成为特征本身的具体方法：

sealed trait Tree[+A]
case object Empty extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

object Tree {
  def depth[A](tree: Tree[A]): Int = tree match {
    case Empty => 0
    case Node(_, left, right) => 1 + max(depth(left), depth(right))
  }
}

如果仅根据companion object的其他方法来定义您的操作，这将特别有用，在这种情况下，您可能不会明确使用

sealed trait Tree[+A] {
  def depth: Int = this match {
    case Empty => 0
    case Node(_, left, right) => 1 + max(left.depth, right.depth)
  }
}
case object Empty extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

。

3）可以使其成为特征的抽象方法，并在子类型中进行具体实现（无需使用trait）：

match

这与传统的面向对象多态性的方法最相似。在定义match的低级操作时，对我来说很自然，因为根据

sealed trait Tree[+A] {
  def depth: Int
}
case object Empty extends Tree[Nothing] {
  val depth = 0
} 
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] {
  def depth = 1 + max(left.depth, right.depth)
}

本身的这些操作定义了更丰富的功能。使用非trait的特征时，这也是最合适的。

4）或者，如果要向源于项目外部的ADT中添加方法，则可以使用隐式转换为具有该方法的新类型：

trait
这是一种特别方便的方法，用于增强您无法控制的代码中定义的类型，将辅助行为排除在类型之外，以便它们可以专注于核心行为或促进sealed。

方法1是采用

// assuming Tree defined elsewhere
implicit class TreeWithDepth[A](tree: Tree[A]) {
  def depth: Int = tree match {
    case Empty => 0
    case Node(_, left, right) => 1 + max(left.depth, right.depth)
  }
}

的函数，其作用类似于第一个示例。方法2-4是对ad hoc polymorphism的所有操作：

Tree