algorithm - 实现尾递归列表操作

Question

我担心我错过了一些“标准”，但我确实尝试过，老实说!

我一直在努力了解如何在链表上实现高效的尾递归操作。 (我正在用 Scala 编写，但我怀疑这是否真的相关)。

注意:我正在从算法理论的角度研究这个问题，我对“使用预建库，它已经解决了这个问题”不感兴趣:)

因此，如果我执行一个简单的过滤器实现来作用于列表:

  def filter[T](l: List[T])(f: T => Boolean): List[T] = l match {
      case h :: t => if (f(h)) h :: filter(t)(f) else filter(t)(f)
      case _ => List()
  }

这不是尾递归，但它的效率还算可以接受(因为它只将新项目添加到它构造的结果列表中)

然而，我提出的简单尾递归变体:

  def filter[T](l: List[T])(f: T => Boolean): List[T] = {
    @tailrec
    def filterAcc[T](l: List[T], f: T => Boolean, acc: List[T]): List[T] = l match {
      case List() => acc
      case h :: t => if (f(h)) filterAcc(t, f, h :: acc) else filterAcc(t, f, acc)
    }
    filterAcc(l, f, List())
  }

反转项目的顺序。 (当然，这并不奇怪!)

当然，我可以通过将过滤后的项目附加到累加器来修复顺序，但我相信这会使它成为一个 O(n^2) 实现(因为每个附加都会强制构建一个全新的列表，它是对 Scala 不可变列表的 O(n) 操作，对列表中的 n 个元素重复 n 次)

我还可以通过在生成的列表上调用 reverse 来解决这个问题。我很欣赏这将是一个单一的 O(n) 操作，所以整体时间复杂度仍然是 O(n)，但它看起来很难看。

所以，我的问题很简单；有没有一种尾递归的解决方案，和从一开始就以正确的顺序累积，即 O(n) 并且可能比“向后捕获并反转”选项涉及更少的工作？我错过了什么吗(这对我来说很正常，我担心 :( )

Answer 1

你无法避免 reverse 的原因是因为标准库 List 是一个指针指向头部的链表:完全可以实现你自己的指针指向尾部的列表并避免调用 reverse。

但是，因为从算法的角度来看这不会带来任何改进，所以自己编写此列表也没有多大意义，也没有将其包含在标准库中