实现尾递归列表操作

Question

我担心我错过了一些东西 "standard" 但我确实尝试过，老实说！

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

注意：我是从算法理论的角度来研究这个的，我对"use the prebuilt library, it's already worked this out"不感兴趣:)

所以，如果我执行一个简单的过滤器实现来作用于列表：

  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) 并且可能比 "catch it backwards and reverse it" 选项涉及更少的工作？我错过了什么吗（这对我来说很正常，我担心 :( )

Answer 1

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

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

Answer 2

不，你没有遗漏任何东西。积累一些成绩，最后reverse是完全正常的。如果您不喜欢它，那么您可以尝试通过一些标准操作的组合来表达您的计算，例如 foldLeft、map、flatMap、filter 等

话虽这么说...如果您忘记 private 修饰符和不变性，那么您实际上可以编写尾递归 filter，但是真的不好看:

import scala.annotation.tailrec

def filter[T](l: List[T])(f: T => Boolean): List[T] = {

  val tailField = classOf[::[_]].getDeclaredField("tl")
  tailField.setAccessible(true)

  /* Appends a value in constant time by 
   * force-overriding the tail element of the first cons 
   * of the list `as`. If `as` is `Nil`, returns a new cons.
   *
   * @return the last cons of the new list
   */
  def forceAppend[A](as: List[A], lastCons: List[A], a: A): (List[A], List[A]) = as match {
    case Nil => {
      val newCons = a :: Nil
      (newCons, newCons) // not the same as (a :: Nil, a :: Nil) in this case!!!
    }
    case _ => {
      val newLast = a :: Nil
      tailField.set(lastCons, newLast)
      (as, newLast)
    }
  }

  @tailrec
  def filterAcc[T](l: List[T], f: T => Boolean, acc: List[T], lastCons: List[T]): List[T] = {
    l match {
      case List() => acc
      case h :: t => if (f(h)) {
        val (nextAcc, nextLastCons) = forceAppend(acc, lastCons, h) 
        filterAcc(t, f, nextAcc, nextLastCons)
      } else {
        filterAcc(t, f, acc, lastCons)
      }
    }
  }
  filterAcc(l, f, Nil, Nil)
}

val list = List("hello", "world", "blah", "foo", "bar", "baz")
val filtered = filter(list)(_.contains('o'))

println(filtered)

这里发生的事情是：我们只是假装我们正在 C 中编写代码，并且我们想直接使用构建数据结构的引用。这允许我们保留对列表最后一个 cons 的引用，然后覆盖指向下一个 cons 的指针，而不是在头部添加.这暂时打破了不变性，但在这种情况下或多或少是可以的，因为在我们构建时蓄能器不会泄漏到外面。

我非常怀疑这是否比直接实施更快。恰恰相反：它实际上可能更慢，因为代码更复杂，编译器更难优化。

Answer 3

也许可以使用 :+ 语法来附加头部。

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

filterAcc(l, f, List())

}

实现尾递归列表操作

Implement tail-recursive List operations

algorithm

scala

recursion

tail-recursion