scala – 抽象重复flatMap

发布时间：2020-12-16 09:18:03 所属栏目：安全来源：网络整理

导读：我试图泛化重复的嵌套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)))) 重复flatMa

我试图泛化重复的嵌套flatMap,但不知道是否存在.

以下代码将产生n选择3,

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,

n choose 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,k,l,m)))))

显然这里有一种模式.我想利用这种相似性来获得n选择r,

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,k)

我可以使用flatMap直接写一个递归的解决方案,或者使用一个表达式的糖：

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

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

虽然上面的代码是Scala,在这种情况下,我对它的功能编程方面感兴趣,而不是语言能力.如果有一个解决方案,但是Scala不支持这个解决方案,我对此感兴趣.

编辑：他是一个示例调用者,并根据请求生成结果：

scala> combinationsRecursiveLoop(5,3)

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

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

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

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

解决方法

这是一个看待这一点的方法,我已经想出了.

您可以将链中的一个阶段提取为函数f：List [Int] =>列表[列表[Int]],它采用列表与组合的开头,并添加所有可能的下一个元素.

例如在选择(5,3)中,f(List(2,0))将导致List(List(3,0),List(4,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]],它是同义词(具有相同的参数和返回类型).

有一个monoid实例的内生kleisli箭头,其中单个“加法”是指flatMap操作(或伪代码,f1 | | f2 == a => f1(a).flatMap(f2)).所以要替换你的flatMaps链,你需要“添加”这个f函数的r个实例,或换句话说,将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,List(3,1))

这些组合是相反的,但是应该可以制作一个版本,它以增加的顺序生成与元素的组合(或者只是运行choose(n,r).map(_.reverse)).

Stream [List [Int]](甚至更好的一个scalaz.EphemeralStream [List [Int]]：你不想让所有的组合都缓存在内存中),而另一个改进就是做一个懒惰的版本,但是这是给读者留下的一个练习.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!