0

I'm new for Scala. I have a question about the order in the foor loop.

type Occurrences = List[(Char, Int)]

lazy val dictionaryByOccurrences: Map[Occurrences, List[Word]] = dictionary.groupBy(x => wordOccurrences(x))

def wordAnagrams(word: Word): List[Word] = dictionaryByOccurrences.getOrElse(wordOccurrences(word), List())

def combinations(occurrences: Occurrences): List[Occurrences] = occurrences match {
    case List() => List(List())
    case head::tail => {
    for (o <- combinations(tail); x <- 1 to head._2)
    yield (head._1, x) :: o
}

if I change the order in the for loop, it will be wrong

def combinations(occurrences: Occurrences): List[Occurrences] = occurrences match {
    case List() => List(List())
    case head::tail => {
    for (x <- 1 to head._2; o <- combinations(tail))
    yield (head._1, x) :: o
}

I can not find the reason

1 Answer 1

1

The type constructor of for(x <- xs; y <- ys; ...) yield f(x, y, ...) is the same of xs by default. Now the return type of combinations is List[Occurrences], then the expected type constructor is List[_], while the type constructor of 1 to n is Seq[_].

The following codes work:

def combinations(occurrences: Occurrences): List[Occurrences] = occurrences match {
    case List() => List(List())
    case head::tail => {
    for (x <- (1 to head._2).toList; o <- combinations(tail))
    yield (head._1, x) :: o
}

And this would work too:

import collection.breakOut
def combinations(occurrences: Occurrences): List[Occurrences] = occurrences match {
    case List() => List(List())
    case head::tail => {
      (for (x <- 1 to head._2; o <- combinations(tail))
        yield (head._1, x) :: o)(breakOut)
    }
}

In depth, for(x <- xs; y <- ys; ...) yield f(...) is equivalent to xs.flatMap(...), and the full signature of List#flatMap as following:

def flatMap[B, That](f: (A) ⇒ GenTraversableOnce[B])
                    (implicit bf: CanBuildFrom[List[A], B, That]): That

You can see that the return type of flatMap is a magic That which is List[B] by default, you can look into Scala 2.8 CanBuildFrom for more information.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.