使用尾递归过滤列表

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

Answer 2

@Brian 的回答很好，但它颠倒了输入列表。这通常不是预期的行为。

@jwvh 的建议是将第 3 个参数中的累加器传递给函数，但这会将私有 API 泄漏到 public API.

这两种解决方案都需要在返回答案之前反转累加器——有效地迭代你的输入列表两次。这是一个疯狂的实现，特别是考虑到您正在尝试实现它以促进大型列表。

考虑这个尾递归实现，它不公开私有 API 并且不需要在过滤后反转累加器。

disclaimer: this is the first scala procedure I have ever written. Feedback on any implementation style or detail is welcomed.

def filter(n: Int, xs: List[Int]): List[Int] = {
  @scala.annotation.tailrec
  def aux(k: List[Int] => List[Int], xs: List[Int]): List[Int] = xs match {
    case Nil => k(Nil)
    case x :: xs if (x < n) => aux(k, xs)
    case x :: xs            => aux((rest: List[Int]) => k(x :: rest), xs)
  }
  aux(identity, xs)
}

filter(5, List(1,2,3,4,5,6,7,8,9,0)))
// => List(5, 6, 7, 8, 9)

使用尾递归过滤列表

Filter a list using tail recursion

scala

tail-recursion