How to make this recursive method tail recursive in Scala?

Question

I found a function for creating a cartesian product from a list of lists in Scala. However, it isn't tail recursive and won't work well with large lists. Unfortunately I won't know at design time how many lists I will need to combine, so I believe a recursive function is necessary. I'm struggling 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
}

dhg · Accepted Answer · 2012-04-24T00:58:45.073

5

This approach is similar to your original method except that instead of starting and the front and recursively descending until you get to the end and appending back up, I've introduced an accumulator to that I can just march through the list backwards, accumulating as I go.

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

Then:

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

edited Apr 24 '12 at 00:58

answered Apr 24 '12 at 00:51

dhg

52,383
8
123
144

@Nathan I wrote an answer to another question that goes over the general idea of introducing accumulators to make functions tail-recursive here: http://stackoverflow.com/a/6977068/450128 That question was in the context of Python, but if you need a bit more of a look at the idea of accumulators, it may help. – Ben Apr 24 '12 at 01:54
So to be honest I don't think I could have come up with that solution using my own powers of reasoning (even after reading Ben's fine answer from the other question). So, is this a kind of thinking that one cultivates over time while working in a functional style, or am I just plain old out of my league? :) – Nathan Apr 24 '12 at 04:21
@Nathan, This was a slightly tricky use of an accumulator. But basically, like everything in programming, you have to A) know the tricks (here, know to use an accumulator to pass intermediate results), and B) practice. – dhg Apr 24 '12 at 04:24

How to make this recursive method tail recursive in Scala?

1 Answers1