3

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

1 に答える 1

5

このアプローチは元の方法と似ていますが、開始して先頭に移動し、最後に到達してバックアップを追加するまで再帰的に下降する代わりに、リストを逆方向に移動して、次のように累積できるアキュムレータを導入しました。行く。

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

それで：

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))
于 2012-04-24T00:51:03.313 に答える