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.

Thanks for any input!

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)
}
``````
Source (Stackoverflow)