scala - 如何在 Scala 中附加到玫瑰树

Question

我需要一个类似scalaz.Tree或以下的玫瑰树数据结构：

case class Tree[A](root: A, children: Stream[Tree[A]])

但是我很难理解如何编写附加节点的函数。一般来说，我知道附加一个节点涉及重建树，并且使用不可变数据结构执行此操作需要递归函数，但我无法将它们放在一起。我确实看到了Scala: Tree Insert Tail Recursion With Complex Structure，但由于它涉及二叉树，我不太了解如何为多路树实现它。

传统上，我会使用 Array 等可变地实现这一点。是否有一些我应该阅读的书或资源来更多地理解函数式数据结构？或者是否有一些示例代码可以推荐给我阅读？

Answer 1

您对“附加节点”的要求并不明显。您可以以简单的方式完成此操作，将第二个节点作为第一个子节点插入：

def append[A](tree1: Tree[A], tree2: Tree[A]) = tree1 match {
  case Tree(root, children) => Tree(root, tree2 #:: children)
}

如果这不是你想要的，你能举个例子吗？

是否有一些我应该阅读的书或资源来更多地理解函数式数据结构？或者是否有一些示例代码可以推荐给我阅读？

标准推荐是计算机程序的结构和解释。代码示例不在 Scala 中，但翻译知识应该很容易。