Wie eine Baumdatenstruktur zu definieren, die Kantentyp hat

Question

Ich möchte einen Baum Datenstruktur definieren, die ein Etikett für seine Kanten hat, hier mein erster Gedanke ist:

sealed trait Tree[+N,+E] 
case class Branch[N,E](value:N, children:Map[E, Tree[N,E]]) extends Tree[N,E] 
case class Leaf[N](value:N) extends Tree[N, Unit] 

Wie Sie sich vorstellen können, wenn ich machen Eine Bauminstanz wie folgt, der Typ der Instanz wäre Tree[Int, Any]. Ich möchte auch keinen kontravarianten Typ für E haben.

val tree = 
    Branch(0, 
     Map(
     "a" -> Leaf(1), 
     "b" -> Branch(2, 
      Map(
      "c" -> Leaf(4)))) 
    ) 

Ich möchte wissen, was wäre eine bessere Möglichkeit, diese Tre zu implementieren. Ich habe von Fix-Typ-Klassen und Rekursionssystemen gehört, aber ich weiß nicht, ob sie hier nützlich sein können.

Answer 1

Haben Leaf verlängern Tree[N, Nothing], nicht Tree[N, Unit]. Nothing ist ein Bottom-Typ, so dass Leaf[N] ein Subtyp von Tree[N, E] für jede E sein wird, da Sie es kovariant haben.

case class Leaf[N](value:N) extends Tree[N, Nothing] 

Mit dieser Änderung funktioniert Ihre Beispielbaumdefinition einwandfrei.

Fixpunkttypen sind komplizierter, aber nicht immer notwendig. Aber Sie könnten dies sicherlich ändern, um sie zu nutzen. Wenn Sie diesen Weg gehen wollen, ist es vielleicht besser, sie als eine andere spezifischere Frage zu stellen.