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

Question

我有一个递归函数，我正在尝试创建 @tailrec通过让内部递归部分( countR3 )将元素添加到队列( agenda 是 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 中迭代集合时改变集合的危险。但是 Queue 是一种不同颜色的马。当然，我知道我可以简单地编写一个命令式循环，如下所示:

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立即切断序列遇到项目，即当队列耗尽时。

由于之前的调用仍然产生了 Option 的序列s，我们需要用 flatten 解开它们.

map({ case (x, y) => countR3(x, y) })基本上将您的功能应用于每个项目。

最后，toList强制评估流(这就是我们正在使用的)然后 sum计算列表项的总和。

我认为 agenda.foldLeft 的问题(它只处理“一些”排队的项目)我猜它需要一个(可能不可变的)当前排队项目的列表，因此不受计算过程中添加的项目的影响。