Geek asks and answers

How to make this recursive method tail recursive in Scala?

I found a function to create a Cartesian product from a list of lists in Scala. However, it is not recursive and will not work with large lists. Unfortunately, during development I won’t know how many lists I need to combine, so I believe that a recursive function is needed. I try my best to make it tail recursive, so it can be optimized by the compiler:

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
}
+3
source share
1 answer

, , , , , , , .

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

More articles:


All Articles