How to append to Rose Trees in Scala

Question

I'm in need of a Rose Tree data structure like scalaz.Tree or the following:

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

However I'm having a hard time understanding how to write a function for appending nodes. In general, I understand that appending a node involves rebuilding the tree, and doing that with immutable data structures requires recursive functions, but I just haven't been able to put it all together. I did see Scala: Tree Insert Tail Recursion With Complex Structure but since that involves binary trees, I didn't quite grasp how to implement it for a multi-way tree.

Traditionally, I would implement this mutably using Array or such. Is there some book or resource that I should read to understand functional data structures more? Or is there some example code that could be recommended for me to read over?

Answer 1

It isn't obvious what are your requirements for "appending nodes". You can do it in the trivial way, inserting the second node as a first child:

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

If that's not what you want, can you provide an example?

Is there some book or resource that I should read to understand functional data structures more? Or is there some example code that could be recommended for me to read over?

The standard recommendation is Structure and Interpretation of Computer Programs. The code examples aren't in Scala, but it should be easy enough to translate the knowledge.