Combinations with replacement

Question

I am still new to Scala and wrote a small snippet to find all the combinations with replacement of a sequence (e.g. cwr(ab, 3) should give aaa, aab, abb, bbb). The slow way would be to generate all permutations, sort them, and throw out duplicates. I'd like to know if this code is idiomatic Scala style, and if I'm making any bad performance mistakes.

def sortedRanges(lo: Int, hi: Int, reps: Int) : List[List[Int]] =
    if (reps == 0) List(Nil) else (
    List.range(lo,hi).flatMap( 
        (x:Int) => (sortedRanges(x,hi,reps-1).map((xs:List[Int]) => x :: xs ))
    )
)

def combinations_with_replacement[T](stuff: List[T], reps: Int) : List[List[T]] = 
  sortedRanges(0,stuff.length, reps).map( (xs:List[Int]) => xs.map(stuff(_)))

Answer 1

Here are the changes I would make to your code in terms of both style and efficiency:

    def sortedRanges(lo: Int, hi: Int, reps: Int): List[List[Int]] = reps match {
        case 0 => Nil :: Nil
        case _ => 
          List.range(lo, hi) flatMap (x =>
            sortedRanges(x, hi, reps - 1) map (xs =>
              x :: xs))
      }

    def combinationsWithReplacement(stuff: Vector[T], reps: Int): List[List[T]] =
      sortedRanges(0, stuff.length, reps) map (xs =>
        xs map (x => 
          stuff(x)))

Style Comments

Methods which take functions as parameters (flatMap and map in this case) should be invoked using infix notation. That is, if there were a god of Idiomatic Scala Style he would prefer xs map (...) to xs.map(...)

Defined functions should use camel case, e.g. combWithRep over comb_with_rep.

In general, and you will get a feel for this the more you use Scala, pattern matching is preferred over if-statements. You will notice that in your function sortedRanges I've swapped your if-else statement for a pattern match on the value reps.

The last style tip I have for you is to break a chain of higher order functions over several lines. This last one can be fudged in some cases, but in general I find that it improves readability.

Efficiency Comment

The one change that I made in the name of efficiency was to change the container type of stuff from List[T] to Vector[T]. The reason I made this change is that accessing an item in a List takes linear time on the length of the list, whereas accessing an item in a Vector is almost constant. And as you know, you are accessing elements of stuff by index is in the last line of combinationsWithReplacement.