在Scala中编写代数数据类型

Question

在 Haskell 中，我可以定义一棵 Tree：

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

我该如何用Scala编写这段代码？

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

- Kevin Meredith

---

密封的 case 类，参数化为 A。http://docs.scala-lang.org/tutorials/tour/case-classes.html - chi

“case classes” 的本质是“密封的”，我相信：scala> case class Bar(x: Int) extends Foo() <console>:9: error: case class Bar has case ancestor Foo, but case-to-case inheritance is prohibited. - Kevin Meredith

我写了一个关于Scala枚举和替代方案的小概述，你可能会觉得它很有用：pedrorijo.com/blog/scala-enums/ - pedrorijo91

Answer 1

定义抽象数据类型

在Scala的“对象功能”模型中，您需要定义一个 trait 来表示抽象数据类型及其所有参数。然后，对于每个情况，您需要定义一个 case class 或 case object 。类型和值参数被视为类构造函数的参数。通常，您会将trait设置为 sealed ，以便当前文件之外的任何地方都无法添加新的case。

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作为Nothing类型的空Tree，这是Scala的通用子类型。由于协变性，这个Empty现在是所有可能的A类型的Tree[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）你可以将它作为独立函数放在 trait 之外：

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实例，则这可能很好。 通常将此类方法放入伴生对象是很自然的。

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) 您可以将其作为 trait 的抽象方法，并在子类型中进行具体实现（避免使用 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)
  }
}

这是一种特别方便的方式，可以增强在代码中定义但您无法控制的类型，将辅助行为因素从您的类型中分解出来，以便它们可以专注于核心行为，或者促进临时多态性。

方法1是一个函数，接受一个Tree并像第一个示例那样工作。方法2-4都是对Tree的操作：

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

- acjay

Answer 2

从 Scala 3 开始，利用新的联合类型，这将成为可能：

type Tree[A] = Node[A] | Empty.type
case object Empty
case class Node[A](value: A, left: Tree[A], right: Tree[A])

以下是实例化的方法：

val empty: Tree[String] = Empty
val tree:  Tree[String] = Node("foo", Node("bar", Empty, Empty), Empty)

并将其作为具体示例的一部分使用：

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

depth(tree)  // 2
depth(empty) // 0

- Xavier Guihot