Scala Tree/Graph Implementierung

Question

Ich habe ein Problem mit einer "Kundeneinladung", bei der eine Person eine andere Person einladen kann und die Einladung nur gültig ist, wenn die eingeladene Person jemanden einlädt.

Um dieses Problem zu lösen, dachte ich daran, einen Tree-Algorithmus anstelle eines Graph-Algorithmus zu schreiben.

Ich versuche, diese Baumstruktur in Scala zu schreiben und hier ist, wie ich angefangen habe:

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) 
     */ 
    } 

} 

Der Eingang so etwas wie sein:

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

Ich möchte arbeiten mit Option [List [MyNode]], da children Option ist und wenn der Knoten eingeladen wurde, würde ich stattdessen eine leere Liste als Wert setzen.

Baum ist die beste Struktur, um mein Problem zu lösen, oder sollte ich zu Graph oder so etwas gehen (ein Knoten in einem Diagramm kann mehrere Kinder haben?)? Und die andere Frage ... Was ist der Unterschied in diesen Zeilen (h :: t) und (h ::: t)?

Der folgende Code hat einen Compiler-Fehler:

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

Wie kann ich mit der Option [Liste] arbeiten? Sollte

Answer 1

sein

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) 
    */} 

Sie sind Match Option Objekt nicht Tupels. Dieses Spiel ist nicht erschöpfend, da Sie vermissen

case Some(Nil) => .... 

Ich finde es besser, nur Liste ohne Optional zu verwenden. Hier geht es hauptsächlich um Semantik. Optional bedeutet, dass etwas leer ist. Wir haben einen Wert für eine leere Liste (Nil), so dass wir kein zusätzliches Objekt verwenden müssen, um eine solche Situation zu markieren. Leere Liste sollte genug sein

::: Funktion fügt die Elemente einer gegebenen Liste vor Ihrer Liste hinzu. Einfach diese Funktion wird verwendet, um zwei Liste
:: ist Funktion, die Element am Anfang der Liste hinzufügen.
Auch in Scala :: ist eine Fallklasse, die Kopf und Schwanz haben. Wenn Sie mehr über List Implementierung wissen möchten, empfehle ich Ihnen, https://www.amazon.com/Functional-Programming-Scala-Paul-Chiusano/dp/1617290653