在 Scala 中对循环影响的顺序

Question

我是Scala的新手。我对 foor 循环中的顺序有疑问。

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
}

如果我更改 for 循环中的顺序，那将是错误的

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
}

我找不到原因

Answer 1

默认情况下，for(x <- xs; y <- ys; ...) yield f(x, y, ...) 的类型构造函数与 xs 相同。现在combinations的返回类型是List[Occurrences]，那么预期的类型构造函数是List[_]，而1 to n的类型构造函数是Seq[_]。

以下代码有效：

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
}

这也行得通：

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

在深度上，for(x <- xs; y <- ys; ...) yield f(...)相当于xs.flatMap(...)，List#flatMap的完整签名如下：

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

您可以看到flatMap的返回类型是默认List[B]的魔术That，您可以查看Scala 2.8 CanBuildFrom以获取更多信息。