mir-aclewhip mir-aclewhip - 2 months ago 26
Scala Question

Filter a list using tail recursion

I am having a real tough time with tail recursion...

My current function filters out values less than 'n' from list 'l'

def filter(n: Int, l: List): List = l match {
case Nil => Nil
case hd :: tl => {
if (hd < n) filter(n, tl)
else hd :: filter(n, tl)
}
}


When using large lists, this causes the stack to overflow.

Can someone please help me understand how to convert this to a tail recursive function?

Thanks for any input!

Answer

This is usually done with a helper function that accumulates the results. filterR has an additional parameter acc that we add values that are greater than n to.

def filter(n: Int, l: List[Int]): List[Int] = {
  @scala.annotation.tailrec
  def filterR(n: Int, l: List[Int], acc: List[Int]): List[Int] =  l match {
    case Nil => acc
    case hd :: tl if(hd < n) => filterR(n, tl, acc)
    case hd :: tl            => filterR(n, tl, hd :: acc)
  }
  filterR(n, l, List[Int]())
} 

With the suggestion from @jwvh:

@scala.annotation.tailrec
def filter(n: Int, l: List[Int], acc: List[Int] = List[Int]()): List[Int] =  l match {
   case Nil => acc.reverse
   case hd :: tl if(hd < n) => filter(n, tl, acc)
   case hd :: tl            => filter(n, tl, hd :: acc)
} 
Comments