再帰的呼び出しを伴うscalaの理解のため

Question

私はcourseraコース "scalaの関数型プログラミング"のための最後のプロジェクトに取り組んでいます。私は、文字の出現のリストを取り、可能なすべての文字の出現を出力する、combinationという関数を実装する必要があります。一例として、出現リストList(('a', 2), ('b', 2))のサブセットは、次のとおり

List(
    List(), 
    List(('a', 1)), 
    List(('a', 2)), 
    List(('b', 1)), 
    List(('a', 1), ('b', 1)), 
    List(('a', 2), ('b', 1)), 
    List(('b', 2)), 
    List(('a', 1), ('b', 2)), 
    List(('a', 2), ('b', 2)) 
) 

この問題への私のアプローチは、（例えば、「A」という）の各文字をループであり、そして0から2まで（その可能な出現回数を取ります）、現在のサブセットにこれをプリペンドします。それから、次の文字に進み、リストの終わりに当たるまで繰り返します。これは、ベースケースによって捕捉されます。私は以下のように理解のためにこれを実装：

type Occurrences = List[(Char, Int)] 

def combinations(occurrences: Occurrences): List[Occurrences] = 
    if (occurrences == List()) List() // base case 
    else 
    for { 
     (c, n) <- occurrences 
     subc <- combinations((occurrences.toMap - c).toList) 
     i <- 0 to n 
    } yield { 
     if (i == 0) subc // not including c in the subset 
     else (c, i) :: subc // including c in the subset 
    } 

私はcombinations(List(('a', 2), ('b', 2))を呼び出すときに、この機能は常に私に空のリストを提供します。これがなぜそのようなのでしょうか？

Answer 1

予期せぬ出力する理由はここにある：これは、最終的には、ベースケースList()を返すまで、スタックフレームをロードし、再帰ます

subc <- combinations((occurrences.toMap - c).toList) 

。 forの理解では、発電機（<-）はmapまたはflatMapで実装され、空のコレクションにマップすると完了したことに注意してください。したがって、次の発電機、i <- 0 to nは、呼び出されません

List[Int]().map(_ + 1).foreach(_ => println("got it")) // no output 

は、yieldには何もありませんし、空のList()は返すために唯一のものです。あなたFOR-を膝腱、これはList()に評価されるだけで基本ケース上記の呼び出しで

subc <- combinations((occurrences.toMap - c).toList) 

：そして、スタックフレームのポップは、空のList()等、

Answer 2

を受けている問題は、ラインです読解：

あなたは空のリストにあなたがで List()を得る理由ですコールスタックを、すべての道を戻ってきていることを意味し、その上でそのコールのリターン List()を行い、

scala> for {a <- 0 to 3; b <- List()} yield a 
res0: scala.collection.immutable.IndexedSeq[Int] = Vector() 

トップ。