Riferimento bidirezionale con classi di casi

Question

È possibile implementare un albero bidirezionale in una classe di casi. Questo sembra che dovrebbe essere facile, ma sto ottenendo perplesso

case class Node(name:String, parent:Option[Node], children:List[Node]) 

voglio aggiungere un bambino (e ottenere una nuova radice) - qualcosa come

def addChild(n:String):Node = { 
    Node(name, parent, Node(n, Some(this), Nil)::children) 
} 

ma che non lavoro perché il "genitore" nel bambino non farà più riferimento al Nodo che elenca il bambino da bambino. È possibile con elenchi e classificazioni di casi immutabili?

in base alla risposta data al di sotto

case class Node(name: String, parent:() => Option[Node], children: List[Node]) { 
    def makeChild(name: String) = { 
    lazy val newParent:Node = Node(this.name, this.parent, kid :: this.children) 
    lazy val kid:Node = Node(name,() => Some(newParent), Nil) 
    newParent 
    } 
} 

Answer 1

ho chiesto la stessa domanda a @jamesiry su Twitter di recente :-).

La sua risposta:

sealed abstract class Tree[T] 
case class Node[T](left : Tree[T], right : Tree[T]) extends Tree[T] 
case class Leaf[T](value : T, parent :() => Tree[T]) extends Tree[T] 

def make = { 
    lazy val root = Node(left, right) 
    lazy val left : Leaf[Int] = Leaf(1,() => root) 
    lazy val right : Leaf[Int] = Leaf(2,() => root) 
    root 
} 

Answer 2

Solo una nota: che se classi case sono una buona opzione per voi per rappresentare un albero.

Poiché le classi caso sono tipi di valore, l'unico modo per restituire il genitore è restituire una copia del genitore, inclusa una copia della sottostruttura completa. Quindi se ad esempio enumerate i suoi figli, otterrete nuovamente copie dei sottoalberi completi.

Se si desidera eseguire sostituzioni nell'albero, ad es. sostituire un nodo ad un livello più profondo, l'unico modo è di fare una copia dell'albero completo e gettare via il vecchio albero.

Questo sembra tutto un po 'maldestro, ma ad esempio lift-json utilizza case classes per rappresentare JSON AST, quindi potrebbe non essere un grosso problema. Non sono sicuro di quanto sia bravo Scala quando condivide la condivisione. Forse qualcuno può commentare?

Se si desidera utilizzare le classi dei casi, la risposta sopra con valutazione lenta è corretta.