1

如何根据以下特征和案例类实例化树？

sealed trait Tree[+A] 
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

资料来源：Scala 中的函数式编程

示例：我将如何编码以下类型的树String？

           "top"
          /     \
  "middle-left"    "middle-right"
       /          \
  "bottom-left"   "bottom-right"
4

2 回答 2

2

使用您给它的类层次结构，您将无法创建与您想要的示例树非常相似的东西，因为 Branch 只能接受左右子树，而不是值（文本“top”）。

如果您希望分支节点也有一个值，我将修改您的类层次结构，如下所示：

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](value: A, left: Option[Tree[A]] = None, right: Option[Tree[A]] = None) extends Tree[A]

请注意子树的 Option-al 特性，默认值为 None，允许丢失左子树或右子树而不诉诸空值。

然后可以按如下方式生成示例树：

val tree = Branch("top",
                  Some(Branch("middle-left", Some(Leaf("bottom-left")))),
                  Some(Branch("middle-right", right = Some(Leaf("bottom-right")))))
于 2013-08-20T02:53:43.547 回答
2

简短的回答

你不能。您的数据结构的构建方式只能将数据保存在叶子中，而不能保存在内部节点中。

长答案

你这里有一棵单子树。这棵树只能在它的叶子中存储值，但它有一个非常好的属性：当值再次是一棵单子树时（所以你有一棵树中的一棵树），你可以将构造展平，这样你就可以得到一棵树再次。

Haskell 中的“证明”（因为类型类在 Scala 中有点奇怪）是单子的：

data Tree a = Leaf a | Branch (Tree a) (Tree a)

instance Monad Tree where
   return = Leaf
   Leaf a >>= f = f a
   Branch l r >>= f = Branch (l >>= f) (r >>= f)

好的，这不是一个完整的证明，直到我证明 mondic 定律适用于这个类型类。但我认为你可以看到这个想法。

于 2013-08-20T06:48:42.167 回答