Способен ли генератор карт из онлайн-курса EPFL создать все возможные карты?

Короче говоря, ваш анализ и вывод неверны.

Я подозреваю, что корень недоразумения заключается в интерпретации for как цикла (это не так в общем и в частности не так в этом контексте (при работе с вещами, которые более явно являются коллекциями, for достаточно близко, я думаю)).

Объясню сверху вниз.

oneOf, учитывая, что 1 или более генераторов создадут генератор, который, когда его попросят сгенерировать значение, будет зависеть от одного из заданных генераторов путем случайного выбора. Так

oneOf(
  const(Map.empty[Int, Int]),
  k: Gen[Map[Int, Int]]  // i.e. some generator for Map[Int, Int]
)

Выход может быть

someMapFromK, Map.empty, someMapFromK, someMapFromK, Map.empty, Map.empty...

В этом случае наш k

for {
  k <- arbitrary[Int]
  v <- arbitrary[Int]
  m <- oneOf(const(Map.empty[Int, Int]), genMap)  // genMap being the name the outermost generator will be bound to
} yield m.updated(k)

for — это синтаксический сахар для вызовов flatMap и map:

arbitrary[Int].flatMap { k =>
  arbitrary[Int].flatMap { v =>
    oneOf(const(Map.empty[Int, Int]), genMap).map { m =>
      m.updated(k, v)
    }
  }
}

Для чего-то вроде List, map и flatMap используется вся коллекция. Gen ленивее:

• flatMap в основном означает создание значения и передача этого значения функции, которая приводит к Gen
• map в основном означает генерировать значение и преобразовывать его

Если бы мы представили метод на Gen с именем sample, который дал бы нам «следующее» сгенерированное значение (для этой цели мы скажем, что для Gen[T] это приведет к T и никогда не выдаст исключение и т. д.), genMap в точности аналогичен :

trait SimpleGen[T] { def sample: T }

lazy val genMap: SimpleGen[Map[Int, Int]] = new SimpleGen[Map[Int, Int]] {
  def sample: Map[Int, Int] =
    if (scala.util.Random.nextBoolean) Map.empty
    else {
      val k = arbitrary[Int].sample
      val v = arbitrary[Int].sample
      val m =
        if (scala.util.Random.nextBoolean) Map.empty
        else genMap.sample // Since genMap is lazy, we can recurse
      m.updated(k, v)
    }
  }

Что касается третьего вопроса, в исходном определении дополнительный oneOf служит для ограничения глубины рекурсии, чтобы предотвратить взрыв стека. Для этого определения существует 1/4 шанса стать рекурсивным, в то время как замена внутреннего oneOf на genMap будет иметь 1/2 шанса стать рекурсивным. Таким образом (без учета вероятности столкновения в ks), для первого:

• 50% шанс пустого (50% шанс 1+)
• 37,5% вероятность размера 1 (12,5% вероятность 2+)
• 9,375% вероятность размера 2 (3,125% вероятность 3+)
• 2,34375 шанс размера 3 (0,78125% шанс 4+)...

Пока для второго:

• 50% шанс пустого
• 25% вероятность размера 1
• 12,5% вероятность размера 2
• 6,25% вероятность размера 3...

Технически возможность переполнения стека подразумевает, что в зависимости от того, сколько рекурсий вы можете сделать, максимальное количество k -> v пар в Map вы можете сгенерировать, поэтому почти наверняка есть Map, которые не могут быть сгенерированы.