I am trying to make a function that transverse an object with a tree like structure in a tail recursive way, but so far I can't write a code that does it.
My tree like object is:
case class Node(lex: String,
position: Int,
posTag: String,
var dependency: Int = -1,
var left: Vector[Node],
var right: Vector[Node])
So far I've tried the simplest form:
def matchNodes(goldSentence: LabeledSentence): Int = {
def condition(n: Node): Boolean = ???
@tailrec
def match0(acc: Int, n: Seq[Node]): Int =
(n: @switch) match {
case head :: tail => {
if (condition(head)) {
match0(acc + 1, tail)
} else {
acc
}
}
case _ => acc
}
match0(0, left) + match0(0, right)
}
The above code is tailrec, but its not transversing the whole tree, only the first level.
Other way would be:
def matchNodes(goldSentence: LabeledSentence): Int = {
@inline def condition(n: Node): Boolean = ???
def sumAcc(nodes: Vector[Node]): Vector[Node] = nodes match {
case head +: tail => sumAcc(head.left ++ head.right ++ tail)
case _ => nodes
}
@tailrec
def match0(acc: Int, n: Seq[Node]): Int =
(n: @switch) match {
case head :: tail => {
if (condition(head)) {
match0(acc + 1, tail)
} else {
acc
}
}
case _ => acc
}
val flatTree = sumAcc(right ++ left)
match0(0, flatTree)
}
Here I've tried to flat all the nodes into a single Vector[Node]
, but for some reason the expected result after processing the tree is not correct.
The last code I've tried isn't tail recursive, but it is the only one that compute the correct result:
def matchNodes(goldSentence: LabeledSentence): Int = {
var correctRoots = 0
val position:Int = this.position
val dep:Int = dependency
val tag = goldSentence.tags(position)
if (goldSentence.dep(position) == dep || Constants.punctuationTags.contains(tag))
correctRoots += 1
if (right.nonEmpty)
for (r <- right)
correctRoots += r.matchNodes(goldSentence)
if (left.nonEmpty)
for (l <- left)
correctRoots += l.matchNodes(goldSentence)
correctRoots
}
Is there a way in which I could make this function tail recursive?
I Finally wrote a tail recursive method to transverse the whole tree, here it is as an alternative to @badcook answer:
def matchNodes(goldSentence: LabeledSentence): Int = {
@inline def condition(n: Node): Boolean = ???
@tailrec
def match0(acc:Int, n: Node)(queue:Seq[Node]): Int = {
val count = if (condition(n)) acc + 1 else acc
(queue: @switch) match {
case head +: tail =>
match0(count, head)(head.left ++ head.right ++ tail)
case Nil =>
count
}
}
match0(0, this)(left ++ right)
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With