在斯卡拉

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