如何使這個Scala函數（一個「flatMap」變體）尾遞歸？

Question

我在看看下面的代碼

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

我得到一個的StackOverflowError大型值大概是因爲功能不是尾遞歸。有沒有辦法將函數轉換爲適應大數字？

Answer 1

這絕對不是尾遞歸。 f(sublist) :::正在修改遞歸調用的結果，使其成爲普通舊式堆棧遞歸而不是尾遞歸。

確保您的函數是尾遞歸的一種方法是將@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] 

一個簡單的戴夫的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 

凡方法flatMapSublistsTR被實現爲：

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