views:

132

answers:

1

Is it possible to implement a bi-directional tree in a case class. This seems like it should be easy, but I'm getting stumped

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

I want to add a child (and get a new root) -- something like

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

But that won't work because the "parent" in the child will no longer refer to the Node which lists the child as a child. Is this possible with immutable lists and case classes?

Based on answer given below

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
  }
}
+3  A: 

I asked the same question to @jamesiry on Twitter recently :-).

His answer:

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
}
Eric
I converted his code to my use case and pasted it above
Jim
You really should paste the code in the answer, instead of redirecting to another site.
Daniel
Yes sorry that was sloppy as I was in hurry :-(. Thanks to Missing Faktor for editing the answer.
Eric