Tham chiếu hai chiều với các kiểu chữ hoa

Question

Có thể thực hiện một cây hai chiều trong một lớp vỏ. Điều này có vẻ như nó phải là dễ dàng, nhưng tôi bị bối rối

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

Tôi muốn thêm một đứa trẻ (và có được một gốc mới) - một cái gì đó giống như

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

Nhưng điều đó sẽ không làm việc vì "cha mẹ" trong đứa trẻ sẽ không còn tham chiếu đến Nút liệt kê đứa trẻ khi còn nhỏ. Điều này có thể xảy ra với các danh sách bất biến và các lớp chữ hoa chữ thường không?

Dựa trên câu trả lời đưa ra dưới đây

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

Tôi hỏi cùng một câu hỏi để @jamesiry trên Twitter gần đây :-).

câu trả lời của ông:

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

Chỉ cần một lưu ý: nghĩ rằng nếu lớp vỏ máy là một lựa chọn tốt cho bạn để đại diện cho một cái cây.

Vì các kiểu chữ hoa là các kiểu giá trị, cách duy nhất để trả về cha mẹ là trả lại một bản sao của phụ huynh, bao gồm một bản sao của toàn bộ cây con. Sau đó, nếu bạn ví dụ liệt kê trẻ em của nó, bạn sẽ lại nhận được bản sao của các subtrees đầy đủ.

Nếu bạn muốn thực hiện một số thay thế trong cây, ví dụ: thay thế một nút trên một số cấp độ sâu hơn, cách duy nhất một lần nữa là tạo một bản sao của cây đầy đủ và vứt bỏ cây cũ.

Tất cả điều này có vẻ hơi vụng về, nhưng ví dụ: lift-json sử dụng các lớp vỏ để đại diện cho AST AST, vì vậy nó có thể không phải là vấn đề lớn. Bạn không chắc chắn cách Scala tốt khi chia sẻ tham chiếu khi sao chép. Có lẽ ai đó có thể bình luận?

Nếu bạn muốn sử dụng các lớp chữ hoa, câu trả lời ở trên với đánh giá lười là chính xác.