Scala: Tail Recursion and ListBuffer

3
votes

I am learning Scala and in the course of doing so I follow the 15 exercises of Brien (http://www.knowing.net/index.php/2006/06/16/15-exercises-to-know-a-programming-language-part-1/) In the second exercise I should implement a Haar transformation. I implemented most of it but struggled several hours with the return value of the tail recursion. As the compiler doesn't compile ++ - or more exactly the line haar(averages) ++ haar(averagesD).

  • What I am doing wrong in the recursive function?
  • Can you give me other feedback on my code?

Code:

import scala.collection.mutable.ListBuffer
import scala.annotation.tailrec

object haarWavelet2 {

  def avg(tpl:Tuple2[Double, Double]):Double = (tpl._1 + tpl._2) / 2.
  def avgD(tpl:Tuple2[Double, Double]):Double = (tpl._1 - tpl._2) / 2
  def total_avg(nums:ListBuffer[Double]):Double = nums.sum / nums.length

  @tailrec 
  def haar(nums:ListBuffer[Double]):ListBuffer[Double] = {

    if (nums.length == 1) {return nums}

    val buffer = new ListBuffer[Tuple2[Double, Double]]
    for (i <- 0 to nums.length-1 by 2) buffer.append((nums(i), nums(i+1)))

    val averages = for(tpl <- buffer) yield avg(tpl)
    val averagesD = for(tpl <- buffer) yield avgD(tpl)

    haar(averages) ++ haar(averagesD) // does not compile
    }

  def main(args: Array[String]): Unit = {
          print(haar(ListBuffer(8., 5., 6., 2.)))
  }
}
2
scalatail-recursion
What I am doing wrong in the recursive function? You are enforcing tail recursion. By definition tail recursive call has to be the last one statement to be evaluated, but in your case the last statement is ++ (make recursive call, in fact two of them and only then process results) - om-nom-nom
Any reason you're using a mutable ListBuffer here? Recursive functions scream "immutable" to me. Vector has a very good append speed. - KChaloux

2 Answers

5
votes

Tail recursion has the following form:

def func(x..., value){
  if(condition) return value
  else func(y..., value')
}

If you look at this form, what you see is that in order to evaluate func all I need is func itself but with a different set of arguments. Therefore, there is only one item to be placed on the stack and it can easily be transformed into an iterative algorithm.

What you've implemented looks like this:

def func(x...){
  if(condition) return value
  else func(y...) + func(z...)

Notice that in order to evaluate func that you must first evaluate func, an operator + and then 'func' again. So that's 3 items that need to be placed on the stack with a very real order of evaluation which is not amenable to tail call optimization.

2
votes

Following @wheaties structure above, the tail recursive function would look like this,

@tailrec 
def haar(nums:ListBuffer[Double]): ListBuffer[Double] = {

    def haarAcc (nums:ListBuffer[Double], acc:ListBuffer[Double]): ListBuffer[Double] = {
      if (nums.length == 1) return acc

      // val nums_updated ...

      haarAcc(nums_updated, averages ++ averagesD) 
    }

    haarAcc(nums, ListBuffer())
}