Scalaのリストのパーティションメソッドのテール再帰的実装

Question

私はエクササイズ目的のために、機能的に2つのScalaのListメソッドを実装しようとしていました。そのうちの1つはpartitionです。次のシグネチャを想定：

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

これは、2つのリストからなるタプルを返す - 最初のものは、渡された述語fと他のすべての要素を含む別のものを満たすlからすべての要素を含んでいます。

私は残念ながら末尾再帰ではありません、次の再帰的な解決策を考え出した：アキュムレータは、いくつかのケースで使用することができることが明らかにされている。このスタックオーバーフローの問題（Can all recursive functions be re-written as tail-recursions?）で

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

。与えられたものでは、逆の方法で最終的なリストを返すので、これは不可能であると私は主張します。

テール再帰的な解決策を教えてください。たぶん継続的な経過（私はそれがどのように動作し、どのようにそれが適用できるか理解していない）があったとしても？

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）の価格を支払う必要があります。

もう1つの考え方は、一定の時間が追加された内部再帰的実装にList[T]の代わりにListBuffer[T]を使用することです。あなたがする必要があるのは、最後にコール.toListです：

Additionaly

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

、私はT => BooleanからList[T]と機能のための独立した引数リストを作成することに注意してください。これは、型推論がパラメータリスト間を流れるので、コンパイラが正しい型引数を推論するのを助けるためです。

Answer 2

leftとrightの2つのアキュムレータを用意する必要があります。それを使用して

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