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

簡潔な答え

できません。データ構造は、内部ノードではなくリーフにのみデータを保持できるように構築されています。

長い答え

ここにモナド木があります。このツリーは値をそのリーフにのみ格納できますが、非常に優れた特性を持っています: 値が再びモナド ツリーである場合 (つまり、ツリーにツリーがある場合)、構成をフラット化できるため、ツリーを取得できます。また。

Haskell の "Proof" (型クラスは 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)

わかりました、これは完全な証明ではありませんが、この型クラスに対してモンドの法則が成り立つことを示すまでは。でも、考え方はわかると思います。

于 2013-08-20T06:48:42.167 に答える
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]

サブツリーのオプションの性質に注意してください。デフォルトは 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 に答える