在斯卡拉

Question

在Haskell写作代数数据类型，我可以定义一个Tree：

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

怎么可能我写这篇文章的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 object替换零参数case class（如Empty），尽管在这种情况下，它有点棘手，因为case object是单例，但我们需要Empty用于每种类型的树。

幸运（或没有，这取决于谁你问），与协方差注释，你可以有一个case object Empty充当Nothing类型，这是Scala的普遍亚型的空Tree。由于协方差，这0​​现在是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，这是常见的斯卡拉定义采用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 

斯卡拉典型带给开发人员选项眼花缭乱从如何组织上的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