对重复 flatMap 的抽象

Question

我正在尝试概括重复的、嵌套的 flatMap 但不确定是否存在。

下面的代码会产生n choose 3, :

的所有组合

def choose3flatMap(n: Int, r: Int = 3) =
  (0 to n - r)
    .flatMap(i => (i + 1 to n - (r - 1))
      .flatMap(j => (j + 1 to n - (r - 2))
        .map(k => Seq(i, j, k))))

重复flatMap操作，我们可以得到n的所有组合选择5， :

def choose5flatMap(n: Int, r: Int = 5) =
  (0 to n - r)
    .flatMap(i => (i + 1 to n - (r - 1))
      .flatMap(j => (j + 1 to n - (r - 2))
        .flatMap(k => (k + 1 to n - (r - 3))
          .flatMap(l => (l + 1 to n - (r - 4))
            .map(m => Seq(i, j, k, l, m)))))

显然这里有一个模式。我想利用这种相似性来获得 n choose r、的通用解决方案。有没有一种简单的方法可以做到这一点。也许是某种高阶函数？

我尝试过的：

Scala 让我用 for 表达式重写 map/flatMap。这读起来更清晰，但选择的数量仍然是硬编码的。

def choose3Loop(n: Int, r: Int = 3) =
  for {
    i <- 0 to n - r
    j <- i + 1 to n - (r - 1)
    k <- j + 1 to n - (r - 2)
  } yield Seq(i, j, k)

我可以直接使用 flatMap 或利用 for 表达式的糖来编写递归解决方案：

def combinationsRecursive(n: Int, r: Int, i: Int = 0): Seq[Seq[Int]] =
  if (r == 1) (i until n).map(Seq(_))
  else {
    (i to n - r).flatMap(
      i => combinationsRecursive(n, r - 1, i + 1).map(j => i +: j))
  }

def combinationsRecursiveLoop(n: Int, r: Int, i: Int = 0): Seq[Seq[Int]] =
  if (r == 1) (i until n).map(Seq(_))
  else
    for {
      i <- i to n - r
      j <- combinationsRecursiveLoop(n, r - 1, i + 1)
    } yield i +: j

虽然这些是一般问题的解决方案，但我想知道是否有我在这里遗漏的更高级别的抽象可能也适用于其他问题。我认识到对于这个特定的应用程序，我可以 (0 to n).combinations(r) 使用库提供的计算组合实现。

虽然上面的代码是 Scala，但在这种情况下，我感兴趣的是它的函数式编程方面，而不是语言功能。如果有解决方案但 Scala 不支持，我对此很感兴趣。

编辑：他是一个示例调用者，根据请求生成的输出：

scala> combinationsRecursiveLoop(5, 3)

res0: Seq[Seq[Int]] = Vector(List(0, 1, 2), List(0, 1, 3), List(0, 1, 4), List(0, 2, 3), List(0, 2, 4), List(0, 3, 4), List(1, 2, 3), List(1, 2, 4), List(1, 3, 4), List(2, 3, 4))

scala> combinationsRecursiveLoop(5, 3).map("("+_.mkString(", ")+")").mkString(" ")

res1: String = (0, 1, 2) (0, 1, 3) (0, 1, 4) (0, 2, 3) (0, 2, 4) (0, 3, 4) (1, 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4)

它仅提供从零开始包含 n 元素的整数集的所有 r 元素子集。 More information on combinations can be found on Wikipedia.

Answer 1

这是我想出的一种看待这个问题的方法。

您可以将链中的一个阶段提取为函数 f: List[Int] => List[List[Int]]，它采用 List 组合的开头，并在其前面添加所有可能的下一个元素。

例如在 choose(5, 3) 中，f(List(2, 0)) 将导致 List(List(3, 2, 0), List(4, 2, 0))。

以下是此类函数的可能实现，其中添加了对初始情况的一些处理：

val f: List[Int] => List[List[Int]] = l =>
  (l.headOption.map(_ + 1).getOrElse(0) to n - (r - l.size))
    .map(_ :: l).toList

现在，这样的函数是 Kleisli arrow Kleisli[List, List[Int], List[Int]]，它是自同态的（具有相同的参数和 return 类型）。

有一个内胚 kleisli 箭头的实例，其中幺半群 "addition" 表示 flatMap 操作（或在伪代码中，f1 |+| f2 == a => f1(a).flatMap(f2)）。因此，要替换 flatMap 链，您需要 "add" r 这个 f 函数的实例，或者换句话说，将 f 函数乘以 r.

这个想法直接转化为 Scalaz 代码：

import scalaz._, Scalaz._

def choose(n: Int, r: Int) = {
  val f: List[Int] => List[List[Int]] = l =>
    (l.headOption.map(_ + 1).getOrElse(0) to n - (r - l.size))
      .map(_ :: l).toList
  Endomorphic.endoKleisli(f).multiply(r).run(Nil)
}

这里是一个例子运行宁它：

scala> choose(4, 3)
res1: List[List[Int]] = List(List(2, 1, 0), List(3, 1, 0), List(3, 2, 0), List(3, 2, 1))

组合是相反的，但应该可以制作一个版本，以递增顺序生成元素组合（或只是运行 choose(n, r).map(_.reverse)）。

另一个改进是制作一个懒惰的版本，即 returns Stream[List[Int]]（或者更好的是 scalaz.EphemeralStream[List[Int]]：您不想将所有组合都缓存在内存），但这留作 reader.

的练习

对重复 flatMap 的抽象

Abstract over repeated flatMap

functional-programming

scala

higher-order-functions

我尝试过的：