Scala的List分区方式的尾递归实现

Question

出于练习目的，我一直在尝试以函数式方式实现几个 Scala 的 List 方法，其中之一是 partition。假定以下签名：

def partition[T](l: List[T], f: T => Boolean): (List[T], List[T])

它 return 是一个由两个列表组成的元组 - 第一个包含 l 中满足传递的谓词 f 的所有元素，另一个包含所有其他元素.

我提出了以下递归解决方案，不幸的是它不是尾递归的：

  def partition[T](l: List[T], f: T => Boolean): (List[T], List[T]) = {
    l match {
      case Nil => (Nil, Nil)
      case head :: rest => {
        val (left, right) = partition(rest, f)
        if (f(head))
          (head :: left, right)
        else
          (left, head :: right)
      }
    }
  }

在此堆栈溢出问题 (Can all recursive functions be re-written as tail-recursions?) 中明确指出在某些情况下可以使用累加器。在给定的一个中，我会声称这是不可能的，因为它会 return 以相反的方式列出最终列表。

你能给我一个尾递归的解决方案吗？也许即使继续通过（我还没有真正理解它是如何工作的以及如何应用它）？

Answer 1

您需要保留两个累加器，一个用于 left，一个用于 right。完成输入列表后，只需 return 两个累加器（反转它们以返回原始顺序）：

def partition[T](l: List[T], f: T => Boolean): (List[T], List[T]) = {
  @annotation.tailrec
  def aux(tl: List[T], left: List[T], right: List[T]): (List[T], List[T]) = tl match {
    case Nil => (left.reverse, right.reverse)
    case head :: rest => {
      if (f(head))
        aux(rest, head :: left, right)
      else
        aux(rest, left, head :: right)
    }
  }

  aux(l, List(), List())
}

使用它：

scala> def partition[T](l: List[T], f: T => Boolean): (List[T], List[T]) = {
     |   @annotation.tailrec
     |   def aux(tl: List[T], left: List[T], right: List[T]): (List[T], List[T]) = tl match {
     |     case Nil => (left.reverse, right.reverse)
     |     case head :: rest => {
     |       if (f(head))
     |         aux(rest, head :: left, right)
     |       else
     |         aux(rest, left, head :: right)
     |     }
     |   }
     | 
     |   aux(l, List(), List())
     | } 
partition: [T](l: List[T], f: T => Boolean)(List[T], List[T])

scala> partition(List(1, 2, 3, 4, 5), (i: Int) => i%2 == 0)
res1: (List[Int], List[Int]) = (List(2, 4),List(1, 3, 5))

Answer 2

你可以保留一个元组作为累加器，并确保在返回列表之前反转列表：

def partition[T](l: List[T])(f: T => Boolean): (List[T], List[T]) = {
  @tailrec
  def partitionInternal(l: List[T])(acc: (List[T], List[T])): (List[T], List[T]) = {
    l match {
      case Nil => acc
      case head :: tail =>
        if (f(head)) partitionInternal(tail)(head :: acc._1, acc._2)
        else partitionInternal(tail)(acc._1, head :: acc._2)
    }
  }

  val (lf, r) = partitionInternal(l)((List.empty[T], List.empty[T]))
  (lf.reverse, r.reverse)
}

另一种解决方案是追加 (:+) 而不是在前面添加 (::)，但这样你就需要为每个条目支付 O(n) 的代价。

另一个想法是使用 ListBuffer[T] 而不是 List[T] 用于具有恒定时间追加的内部递归实现。您需要做的就是在最后调用 .toList:

def partition[T](l: List[T])(f: T => Boolean): (List[T], List[T]) = {
  @tailrec
  def partitionInternal(l: List[T])(acc: (ListBuffer[T], ListBuffer[T])): (ListBuffer[T], ListBuffer[T])  = {
    l match {
      case Nil => acc
      case head :: tail =>
        val (leftAcc, rightAcc) = acc
        if (f(head)) partitionInternal(tail)((leftAcc += head, rightAcc))
        else partitionInternal(tail)((leftAcc, rightAcc += head))
    }
  }

  val (lf, r) = partitionInternal(l)((ListBuffer.empty[T], ListBuffer.empty[T]))
  (lf.toList, r.toList)
}

此外，请注意我为 List[T] 和 T => Boolean 中的函数创建了一个单独的参数列表。这是为了帮助编译器在应用该方法时推断出正确的类型参数，因为类型推断在参数列表之间流动。

Scala的List分区方式的尾递归实现

Tail-recursive Implementation of Scala's List partition method

scala

recursion

functional-programming

tail-recursion