在不断增长的scala.collections.mutable.Queue上有一种优雅的foldLeft方式吗？

Question

我有一个递归函数,我试图@tailrec通过内部递归part(countR3)向队列添加元素(agenda是a scala.collections.mutable.Queue).我的想法是将功能的外部部分放在议程上并总结结果.

注意:这是一个家庭作业问题,因此我不想发布整个代码; 然而,使实现尾递归不是功课的一部分.

以下是与我的问题相关的代码部分:

import scala.collection.mutable.Queue

val agenda: Queue[Tuple2[Int, List[Int]]] = Queue()

@tailrec
def countR3(y: Int, x: List[Int]): Int = {
  if (y == 0) 1
  else if (x.isEmpty) 0
  else if …
  else {
    agenda.enqueue((y - x.head, x))
    countR3(y, x.tail)
  }
}
?
agenda.enqueue((4, List(1, 2)))
val count = agenda.foldLeft(0) {
  (count, pair) => {
    val mohr = countR3(pair._1, pair._2)
    println("count=" + count + " countR3=" + mohr)
    count + mohr
  }
}
println(agenda.mkString(" + "))
count

这几乎似乎有效......问题在于它不会迭代添加到议程中的所有项目,但它确实处理了其中的一些项目.您可以在下面的输出中看到:

count=0 countR3=0
count=0 countR3=0
count=0 countR3=0
(4,List(1, 2)) + (3,List(1, 2)) + (2,List(2)) + (2,List(1, 2)) + (1,List(2)) + (0,List(2))

[在最后议程上的六个项目中,只处理了前三个项目.]

我一般都很清楚,当你在Java中迭代一个集合时,它会有变异的危险.但是队列是一种不同颜色的马.当然,我知道我可以简单地编写一个命令式循环,如下所示:

var count = 0
while (!agenda.isEmpty) {
  val pair = agenda.dequeue()
  count += countR3(pair._1, pair._2)
}

这非常有效,但这是Scala,我正在探索是否有更多功能优雅的方式.

有什么建议？

Answer 1

尽管可能不完全惯用，但您可以尝试以下操作：

Stream.continually({ if (agenda.isEmpty) None else Some(agenda.dequeue()) }).
    takeWhile(_.isDefined).flatten.
    map({ case (x, y) => countR3(x, y) }).
    toList.sum

• Stream.continually({ if (agenda.isEmpty) None else Some(agenda.dequeue()) })为您提供了包装在 中的无限队列项目流Option[Tuple2[Int, List[Int]]]。
• 然后，takeWhile(_.isDefined)一旦None遇到第一个项目，即当队列耗尽时，就切断序列。
• 由于之前的调用仍然会产生一系列Options，因此我们需要使用 来解开它们flatten。
• map({ case (x, y) => countR3(x, y) })基本上将您的功能应用于每个项目。
• 最后，toList强制评估流（这就是我们正在使用的），然后sum计算列表项的总和。

我认为问题agenda.foldLeft（它只处理“一些”排队项目）是我猜测它需要当前排队项目的（可能不可变的）列表，因此不受计算期间添加的项目的影响。