このスカラ関数（ "flatMap"バリアント）を再帰的にするにはどうすればよいですか？

Question

私は関数が末尾再帰ではないと思われるので、私は大きな値のためにStackOverflowErrorを取得しています次のコード

http://aperiodic.net/phil/scala/s-99/p26.scala

具体的

def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match { 
     case Nil => Nil 
     case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f) 
    } 

を見てみたんです。大量に対応するために関数を変換する方法はありますか？

Answer 1

間違いなく再帰的なテールはありません。 f(sublist) :::は再帰呼び出しの結果を修正しているため、末尾再帰の代わりに単純なスタック吹き戻し再帰が行われます。

機能がテール再帰的であることを確実にする1つの方法は、テール再帰と思われる関数に@annotation.tailrecを入れることです。テールコールの最適化を実行できない場合、コンパイラはエラーを報告します。私にはすぐに明らかでない理由から

def flatMapSublistsTR[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = { 
    @annotation.tailrec 
    def helper(r: List[B], ls: List[A]): List[B] = { 
    ls match { 
     case Nil => r 
     case sublist@(_ :: tail) => helper(r ::: f(sublist), tail) 
    } 
    } 
    helper(Nil, ls) 
} 

が、結果は元の関数とは異なる順序で出てくる：

このために、私は実際には末尾再帰だ小さなヘルパー関数を追加します。しかし、それは動作します:-)のように見えます 修正されました。

Answer 2

def flatMapSublists2[A,B](ls: List[A], result: List[B] = Nil)(f: (List[A]) => List[B]): List[B] = 
    ls match { 
     case Nil => result 
     case sublist@(_ :: tail) => flatMapSublists2(tail, result ++ f(sublist))(f) 
    } 

あなたは、一般的に、単にリストへの最後を追加するのではなく、最後に一回の反復から次へと運ぶため、結果の結果パラメータを追加し、結果を吐き出すする必要があります。

はまたそのconfusting sublist@事がオフトピック

case _ :: tail => flatMapSublists2(tail, result ++ f(ls))(f)

に簡素化することができます：ここで私は上記のようなヘルパーメソッドを必要とせずに、問題26を解く方法です。これを尾を再帰的にすることができるなら、金星を持ってください。ここで

def combinations[A](n: Int, lst: List[A]): List[List[A]] = n match { 
    case 1 => lst.map(List(_)) 
    case _ => lst.flatMap(i => combinations (n - 1, lst.dropWhile(_ != i).tail) map (i :: _)) 
    } 

Answer 3

は、機能を実装するための別の方法である：

scala> def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    | List.iterate(ls, ls.size)(_.tail).flatMap(f) 
flatMapSublists: [A, B](ls: List[A])(f: List[A] => List[B])List[B] 

A単にDaveのflatMapSublistsTRと私との間の比較：

メソッドflatMapSublistsTRは次のように実装されて

scala> def time(count: Int)(call : => Unit):Long = { 
    | val start = System.currentTimeMillis 
    | var cnt = count 
    | while(cnt > 0) { 
    |  cnt -= 1 
    |  call 
    | } 
    | System.currentTimeMillis - start 
    | } 
time: (count: Int)(call: => Unit)Long 

scala> val xs = List.range(0,100) 

scala> val fn = identity[List[Int]] _ 
fn: List[Int] => List[Int] = <function1> 

scala> time(10000){ flatMapSublists(xs)(fn) } 
res1: Long = 5732 

scala> time(10000){ flatMapSublistsTR(xs)(fn) } 
res2: Long = 347232 

：

def flatMapSublistsTR[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = { 
    @annotation.tailrec 
    def helper(r: List[B], ls: List[A]): List[B] = { 
    ls match { 
     case Nil => r 
     case sublist@(_ :: tail) => helper(r ::: f(sublist), tail) 
    } 
    } 
    helper(Nil, ls) 
}