scala - 使用尾递归过滤列表

Question

我在尾递归方面遇到了真正的困难......

我当前的函数从列表“l”中过滤掉小于“n”的值

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

当使用大列表时，这会导致堆栈溢出。

谁能帮我理解如何将其转换为尾递归函数？

感谢任何输入!

Answer 1

这通常是通过一个累加结果的辅助函数来完成的。 filterR 有一个附加参数 acc，我们将大于 n 的值添加到该参数。

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

根据@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)
}