在Scala中编写代数数据类型 [英] Writing Algebraic Data Type in Scala
问题描述
Tree ：
数据树a =空的|节点a（Tree a）（Tree a）
我如何在Scala中编写它？
我不确定如何在Scala中为 [A]
>节点匹配树的类型， a 。定义一个ADT
模型，您可以定义一个代表ADT及其所有参数的 trait 。然后，针对您的每个案例，您都定义了案例类或密封，这样当前文件之外的任何内容都不会添加个案。
密封特征树[A]
案例类空[A]（）扩展树[A]
案例类节点[A]（值：A，左：树[A]，右：Tree [A]）继承树[A]
然后你可以这样做：
scala> Node（foo，Node（bar，Empty（），Empty（）），Empty（））
res2：Node [String] = Node（foo，Node（bar，Empty（） ）），Empty（））
有点烦人，我们必须创建一大堆新的空实例，当那个类没有数据时。在Scala中，通常的做法是用<$ c $替换一个零参数 case class ，比如 Empty c> case object ，尽管在这种情况下，它有点棘手，因为 case对象是一个单例，但我们需要一个空为每种类型的树。
幸运的是（或者不是，取决于你问的对象）和协方差注释，你可以有一个 case对象Empty 充当类型为 Nothing 的空，现：空现在是树[A] 的子类型。 A
密封特征树[+ A]
案例对象空扩展树[没有]
case class Node [A]（value：A，left：Tree [A]，right：Tree [A]）继承Tree [A]
然后你得到更干净的语法：
scala>节点（foo，Node（bar，Empty，Empty），空）
res4：Node [String] =节点（foo，Node（bar，Empty，Empty） / code> 使用ADT
要使用新的ADT，它在Scala中很常见定义使用 match 关键字解构它的递归函数。见：
scala> ：粘贴
//进入粘贴模式（ctrl-D完成）
导入scala.math.max
def depth [A]（tree：Tree [A]）： Int =树匹配{
case Empty => 0
case节点（_，left，right）=> 1 + max（深度（左），深度（右））
}
//退出粘贴模式，现在解释。
import scala.math.max
depth：[A]（tree：Tree [A]）Int
scala>深度（Node（foo，Node（bar，Empty，Empty），Empty））
res5：Int = 2
Scala的特点是为开发人员提供了一系列令人眼花缭乱的选项，供您选择如何组织在ADT上运行的功能。我可以想到四种基本方法。
1）您可以将它作为该特质外部的独立功能：
密封特征树[+ A]
案例对象空扩展树[无]
案例类节点[A]（值：A，左：树[A ]，right：Tree [A]）扩展树[A]
对象树{
def depth [A]（tree：Tree [A]）：Int =树匹配{
case Empty => 0
case节点（_，left，right）=> 1 + max（深度（左），深度（右））
}
}
如果你希望你的API感觉比面向对象的功能更强大，或者你的操作可能会从其他数据产生一个ADT实例，这可能会很好。 伴侣对象通常是天生的放置这种方法。
2）您可以将其作为特质本身的具体方法：
密封特质树[+ A] {
def depth：Int =此匹配{
case Empty => 0
case节点（_，left，right）=> 1 + max（left.depth，right.depth）
}
}
case对象Empty扩展Tree [Nothing]
case class Node [A]（value：A，left ：Tree [A]，right：Tree [A]）继承Tree [A]
如果你的操作可以完全用 trait 的其他方法来定义，在这种情况下你可能不会明确地使用 match 。
3）你可以使用子类型中的具体实现将它作为特征的抽象方法（避免使用 match
密封特质树[+ A] {
def depth：Int
}
case对象Empty扩展Tree [Nothing] {
val depth = 0
}
case class Node [A]（value：A，left：Tree [A]，right： Tree [A]）扩展Tree [A] {
def depth = 1 + max（left.depth，right.depth）
}
这与传统的面向对象多态的方法最相似。当定义 trait 的低级操作时，我感觉很自然，在 trait 本身。当处理不是密封的特征时也是最合适的。4）或者，如果你想要将方法添加到源代码为项目外部的ADT，可以使用隐式转换为具有以下方法的新类型：
//假设Tree在别处定义
隐式类TreeWithDepth [A]（tree：Tree [A]）{
def depth：Int =树匹配{
case Empty => ; 0
case节点（_，left，right）=> 1 + max（left.depth，right.depth）
}
}
这是一种特别方便的方法，用于增强在您不控制的代码中定义的类型，将辅助行为排除在类型之外，以便它们可以专注于核心行为，或者便于独立多态性。
方法1是一个函数，它需要 Tree 并且像第一个示例一样工作。方法2-4对树中的所有操作：
scala> Node（foo，Node（bar，Empty，Empty），Empty）.depth
res8：Int = 2
In Haskell, I can define a Tree:
data Tree a = Empty | Node a (Tree a) (Tree a)
How could I write this in Scala?
I'm not sure how to keep the type parameter [A] in Scala for Node to match Tree's type, a.
Defining an ADT
In Scala's "object-functional" model, you define a trait that represents the ADT and all of its parameters. Then for each of your cases, you define either a case class or a case object. Type and value parameters are treated as arguments to the class constructor. Typically, you make the trait sealed so that nothing outside the current file can add cases.
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]
Then you can do:
scala> Node("foo", Node("bar", Empty(), Empty()), Empty())
res2: Node[String] = Node(foo,Node(bar,Empty(),Empty()),Empty())
It's kind of annoying that we have to create a whole bunch of new Empty instances, when that class carries no data. In Scala, it's common practice to replace a zero-argument case class, like Empty, with a case object, although in this case, it's a little tricky, because a case object is a singleton, but we need an Empty for every type of tree.
Fortunately (or not, depending on who you ask), with a covariance annotation, you can have one case object Empty act as the empty Tree of type Nothing, which is Scala's universal subtype. Due to covariance, this Empty is now a subtype of Tree[A] for all possible 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]
Then you get the cleaner syntax:
scala> Node("foo", Node("bar", Empty, Empty), Empty)
res4: Node[String] = Node(foo,Node(bar,Empty,Empty),Empty)
This is, in fact, how Scala's standard library Nil works, with respect to List.
Operating on an ADT
To use the new ADT, it's common in Scala to define recursive functions that employ the match keyword to deconstruct it. See:
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 characteristically gives the developer a bewildering array of options to choose from in how to organize functionality that operates on ADTs. I can think of four basic approaches.
1) You can make it a standalone function external to the 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))
}
}
This might be nice if you want your API to feel more functional than object-oriented, or if your operation might product an instance of your ADT from other data. The companion object is often a natural place to put such methods.
2) You can make it a concrete method of the trait itself:
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]
This is particularly useful if your operation can be defined purely in terms of other methods of the trait, in which case you probably won't explicitly use match.
3) You can make it an abstract method of the trait with concrete implementations in the subtypes (obviating the need to use 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)
}
This is most similar to the approach traditional object-oriented polymorphism. It feels natural to me when defining the low-level operations of the trait, with richer functionality defined in terms of these operations in the trait itself. It's also most appropriate when working with traits that aren't sealed.
4) Or, in the case you want to add a method to an ADT whose source is external to your project, you could use an implicit conversion to a new type that has the method:
// 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)
}
}
This is a particularly handy way to enhance types defined in code you don't control, to factor auxiliary behavior out of your types so that they can be focused on core behavior, or to facilitate of ad hoc polymorphism.
Method 1 is a function that takes a Tree and works like the first example. Methods 2-4 are all operations on a Tree:
scala> Node("foo", Node("bar", Empty, Empty), Empty).depth
res8: Int = 2
这篇关于在Scala中编写代数数据类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
