algui91 algui91 - 1 month ago 15
Scala Question

Transverse a tree like object in a Tail recursive way in scala

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])


Version 1, tail Recursive (Not working)



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.

Version 2, tail Recursive (Not working)



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.

Version 3, no Tail recursive (Working)



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?

Thanks in advance.

Answer

There's no natural way to convert this to use tail recursion (i.e. you're not going to get an asymptotic improvement in space usage). That is the tree traversal algorithm you're using here requires a stack, whether that be the call stack given by recursion or an explicit stack you maintain. If you don't want to blow your call stack you can use an explicit stack and iterate through. If you really want to stick with tail recursion, you can pass the stack around as an extra accumulator argument.

// Simplified version of your Node; let's ignore the value for now
case class Node(value: Unit, children: List[Node])
var counter = 0
def traverseNodeAccum(node: Node)(acc: List[Node]): Unit = {
  counter += 1
  (node.children, acc) match {
    case (Nil, Nil) => 
      ()
    case (Nil, x :: rest) =>
      traverseNodeAccum(x)(rest)
    case (child :: otherChildren, xs) => 
      traverseNodeAccum(child)(otherChildren ++ xs)
  }
}

If you want to traverse without incurring the cost of a stack at all, you'll have to have a mutable representation of your tree (at least to the best of my knowledge). Your case class treatment unfortunately won't do.