EPFL 在线课程中的地图生成器是否能够生成所有可能的地图？

Question

https://www.coursera.org/learn/progfun2 第 1 周的作业显示，例如，Map[Int, Int]:

类型地图的生成器

lazy val genMap: Gen[Map[Int,Int]] = oneOf(
  const(Map.empty[Int,Int]),
  for {
    k <- arbitrary[Int]
    v <- arbitrary[Int]
    m <- oneOf(const(Map.empty[Int,Int]), genMap)
  } yield m.updated(k, v)
)

我是 Scala 的新手，但我熟悉命令式编程语言中的生成器。我对生成器执行流程的理解如下：

arbitrary[Int] 被调用，它 returns 生成器产生无限的 Int 序列，第一个生成的值被分配给 k
arbitrary[Int]又被调用了，它returns一个新的生成器，第一个生成的值赋值给v
以递归方式创建随机地图，用 k->v 更新，并让给消费者
当请求来自生成器的下一个值时，执行在 m <- ... 定义处恢复，继续进行新的随机 m 和相同 k->v映射
const 和递归 genMap 都不会运行超出值，这意味着 m 的“循环”永远不会终止，因此 [= 的新值16=] 和 k 从未被相应的 arbitrary 生成器请求。

我的结论是，所有生成的映射要么是空的，要么包含在最外层调用的第一次迭代中生成的 k->v 映射，即 genMap 永远不会生成非空映射这样的映射。

Q1：我的分析和结论正确吗？

问题 2：如果是，我如何实现一个生成器，在生成第一张地图后，生成任何种可能的地图的机会不为零？

问题 3：如果我将 for 表达式中的最后一个定义简化为 m <- genMap，这会以任何方式改变生成器的行为吗？

Answer 1

总之，你的分析和结论是不正确的。

我怀疑误解的根源在于将 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% chance of empty (50% chance of 1+)
37.5% 的几率是 1 号（12.5% 的几率是 2+）
9.375% 的几率是 2 号（3.125% 的几率是 3+）
2.34375 大小 3 的机会（0.78125% 大小 4+ 的机会）...

第二个：

50% 的几率为空
尺寸 1 有 25% 的几率
12.5% 的机会是尺寸 2
6.25% 的几率是尺寸 3...

从技术上讲，堆栈溢出的可能性意味着根据您可以进行的递归次数，您可以生成的 Map 中的最大数量 k -> v 对，因此几乎可以肯定有 Map无法生成。

EPFL 在线课程中的地图生成器是否能够生成所有可能的地图？

Is the map generator from the EPFL online course able to generate every possible map?

scala

generator