Scala列表分区方法的尾递归实现

Question

为了练习目的，我一直试图以功能方式实现一对Scala的List方法，其中之一是partition。假设以下特征：

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

它返回一个包含两个列表的元组 - 第一个包含了所有从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?）则明确表示，蓄能器可能在某些情况下使用。在给定的一个中，我会声称这是不可能的，因为它会以相反的方式返回最终列表。

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

Answer 1

你可以保持一个元组作为累加器，并确保在返回它们之前颠倒列表：

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

Additionaly，通知我创建了List[T]一个单独的参数列表，并从T => Boolean功能。这是为了帮助编译器在应用该方法时推断正确的类型参数，因为类型推断在参数列表之间流动。

Answer 2

您需要保留两个累加器，一个用于left，另一个用于right。当你完成经历的输入列表，只需返回两个累加器（倒车他们回到原来的顺序）：

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