在Scala中编写代数数据类型

Question

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

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

我怎么能在Scala中写这个？

我不确定如何将[A]Scala中的type参数保持Node匹配Tree的类型a.

Answer 1

定义ADT

在Scala的"对象功能"模型中,您定义了一个trait表示ADT及其所有参数的模型.然后,对于每个案例,您可以定义a case class或a 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实例,那么这可能会很好.在同伴的对象往往是把这些方法的天然场所.

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

这是一种特别方便的方法来增强您无法控制的代码中定义的类型,将辅助行为从您的类型中分解出来,以便它们可以专注于核心行为,或促进特殊的多态性.

方法1是一个函数,它采用Tree和第一个例子一样工作.方法2-4是对a的所有操作Tree:

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