scala - 在 Scala 中编写代数数据类型

Question

在 Haskell 中，我可以定义一个 Tree :

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

我怎么能用 Scala 写这个？

我不确定如何保留类型参数 [A]在 Scala 中为 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 作品，关于 List .

在 ADT 上操作

要使用新的 ADT，在 Scala 中定义使用 match 的递归函数是很常见的。关键字来解构它。看:

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

Scala 的特点是为开发人员提供了一系列令人眼花缭乱的选项，供他们选择如何组织在 ADT 上运行的功能。我可以想到四种基本方法。

1)您可以使其成为特征外部的独立函数:

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))
  }
}

如果您希望您的 API 感觉比面向对象更具功能性，或者您的操作可能会从其他数据中生成您的 ADT 实例，这可能会很好。 companion object通常是放置此类方法的自然场所。

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

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]

如果您的操作可以纯粹根据 trait 的其他方法定义，这将特别有用。 ，在这种情况下，您可能不会明确使用 match .

3)您可以通过子类型中的具体实现使其成为特征的抽象方法(无需使用 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 的低级操作时，我感觉很自然。 ，根据 trait 中的这些操作定义了更丰富的功能本身。当使用不是 sealed 的特征时，它也是最合适的。 .

4) 或者，如果您想将方法添加到源在项目外部的 ADT，您可以使用隐式转换到具有该方法的新类型:

// 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)
  }
}

这是一种特别方便的方法，可以增强在您无法控制的代码中定义的类型，将辅助行为从您的类型中剔除，以便它们可以专注于核心行为，或促进 ad hoc polymorphism .

方法 1 是一个函数，它采用 Tree和第一个例子一样工作。方法 2-4 都是对 Tree 的操作。 :

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