Scalaでこの再帰的メソッドの尾を再帰的にする方法は？

Question

I found a function Scalaのリストのリストからデカルト積を作成します。しかし、これは末尾再帰的ではなく、大きなリストではうまく機能しません。残念ながら、設計時に結合する必要のあるリストの数がわからないので、再帰関数が必要であると考えています。

def product[T](listOfLists: List[List[T]]): List[List[T]] = listOfLists match { 
    case Nil => List(List()) 
    case xs :: xss => for (y <- xs; ys <- product(xss)) yield y :: ys 
} 

Answer 1

このアプローチではなく、開始とフロントのことを除いて、あなたのオリジナルの方法と同様であり、あなたが最後に到達するまで再帰的に下降：私はそれは、コンパイラによって最適化することができるので、それを末尾再帰を作るのに苦労していますバックアップを追加するために、私はアキュムレータを導入しました。私はリストを逆順に進めて行きます。

import annotation.tailrec 

def product[T](listOfLists: List[List[T]]): List[List[T]] = { 
    @tailrec def innerProduct[T](listOfLists: List[List[T]], accum: List[List[T]]): List[List[T]] = 
    listOfLists match { 
     case Nil => accum 
     case xs :: xss => innerProduct(xss, for (y <- xs; a <- accum) yield y :: a) 
    } 

    innerProduct(listOfLists.reverse, List(Nil)) 
} 

その後：私はここに末尾再帰関数を作るためにアキュムレータを導入する一般的な考え方の上に行く別の質問への答えを書いた@Nathan

scala> product(List(List(1,2),List(3,4))) 
res0: List[List[Int]] = List(List(1, 3), List(1, 4), List(2, 3), List(2, 4))