2

scalaz.Tree次のようなRose Treeデータ構造が必要です。

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

ただし、ノードを追加するための関数を作成する方法を理解するのに苦労しています。一般に、ノードを追加するにはツリーを再構築する必要があり、不変のデータ構造でそれを行うには再帰関数が必要であることは理解していますが、すべてをまとめることができていません。Scala: Tree Insert Tail Recursion With Complex Structureを見ましたが、これには二分木が含まれているため、多方向木に実装する方法がよくわかりませんでした。

伝統的に、これは Array などを使用して変更可能に実装します。機能的なデータ構造をより理解するために読むべき本やリソースはありますか? または、私が読むことをお勧めできるサンプルコードはありますか?

4

1 に答える 1

1

「ノードの追加」の要件が何であるかは明らかではありません。2 番目のノードを最初の子として挿入することで、簡単な方法でそれを行うことができます。

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

それがあなたの望むものではない場合、例を挙げていただけますか?

機能的なデータ構造をより理解するために読むべき本やリソースはありますか? または、私が読むことをお勧めできるサンプルコードはありますか?

標準的な推奨事項は、コンピュータ プログラムの構造と解釈です。コード例は Scala ではありませんが、知識を翻訳するのは簡単です。

于 2013-10-06T12:28:32.920 に答える