スカラツリー/グラフ実装

Question

私は、ある人が他の人を招待することができ、招待された人が招待された場合にのみ招待が有効な「顧客招待」については問題があります。

この問題を解決するために、グラフアルゴリズムではなくツリーアルゴリズムを書くことを考えていました。

私はScalaで、このツリー構造を書き込もうとし、ここで私が始めた方法ですよ

：

case class MyNode(key:Int, children:Option[List[MyNode]] = None) 

class MyNodeManager { 

    def find(key: Int, tree: Option[List[MyNode]]) = tree match { 
    case None => None 
    case (h :: t) => 
     println("aa") 
    /*if(h.key == key) 
     Option(h) 
     else 
     find(h ::: t) 
     */ 
    } 

} 

入力のようなものになります：私は働きたい

val invites = List((1, 2), (1, 3), (3, 6)) 

オプションの[List [MyNode]]は子供がオプションなので、ノードが招待されている場合は、代わりに空のリストに値を設定したいと思います。

ツリーは私の問題を解決するのに最適な構造ですか、グラフなどに行きましょうか（グラフ内のノードには複数の子供がいますか？）そして、もう一つの質問は...それらの線（h :: t）と（h ::: t）の違いは何ですか？

次のコードはコンパイルエラーがあります。

Error:(16, 13) constructor cannot be instantiated to expected type; 
    found : scala.collection.immutable.::[B] 
    required: Option[List[MyNode]] 
    case (h :: t) => 
     ^

私はオプション[リスト]で動作することができますどのように？

Answer 1

は、あなたがマッチOptionオブジェクトではないタプルです

def find(key: Int, tree: Option[List[MyNode]]) = tree match { 
case None => None 
case Some(h :: t) => 
    println("aa") 
/*if(h.key == key) 
    Option(h) 
    else 
    find(h ::: t) 
    */} 

であるべき。 この試合では、

case Some(Nil) => .... 

が不足しているので、私はオプションなしでリストのみを使用する方がよいでしょう見つける網羅しているわけではありません。これは主に意味論に関するものです。オプションは何かが空であることを意味します。私たちは空リスト（Nil）の価値があるので、そのような状況を示すために追加のオブジェクトを使う必要はありません。空リストは十分なはずです

:::関数は、指定されたリストの要素をリストの前に追加します。単にこの関数を使用して2つのリストを連結します。
::は、リストの募集に要素を追加する機能です。
Scalaでも::は、頭と尾を持つケースクラスです。リストの実装についてもっと知りたい場合は、お読みになることをお勧めします。https://www.amazon.com/Functional-Programming-Scala-Paul-Chiusano/dp/1617290653