摘要重复flatMap
我试图概括重复，嵌套的flatMap但不知道是否存在。
以下代码将产生n的所有组合选择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)))))
显然这里有一个模式。 我想利用这种相似性来得到一个选择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> combinationsRecursiveLoop（5，3）
res0：Seq [Seq [Int]] =向量（List（0,1,2），List（0,1,3），List（0,1,4），List（0,2,3），List（ （1,2,3,4），列表（1,2,3），列表（1,2,4），列表（1,3,4），列表（2,3,4），列表））
scala> combinationsRecursiveLoop（5，3）.map（“（”+ _。mkString（“，”）+“）”）。mkString（“”）
（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元素子集。 更多关于组合的信息可以在Wikipedia上找到。
这是看待这个问题的一种方式，我已经提出了。
你可以在你的链中抽取一个阶段作为一个函数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箭头Kleisli[List, List[Int], List[Int]] ，它是自同态的（具有相同的参数和返回类型）。
有一个自同态kleisli箭头的monoid实例，monoid“addition”意味着flatMap操作（或伪代码， f1 |+| f2 == a => f1(a).flatMap(f2) ）。 因此，要替换flatMap的链，你需要“添加”这个f函数的r实例，换句话说就是用r乘以f函数。
这个想法可以直接转换成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) ）。
另一个改进是制作一个懒惰的版本，它会返回Stream[List[Int]] （或者更好的是scalaz.EphemeralStream[List[Int]] ：你不想让所有的组合缓存在内存中），但这是作为练习留给读者的。