7

我有一个递归函数，我试图@tailrec通过让内部递归部分 ( countR3) 将元素添加到队列 ( agendais 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，我正在探索是否有一种功能更优雅的方式。

有什么建议么？

4

1 回答 1

2

虽然可能不完全地道，但您可以试试这个：

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（它只处理“一些”排队的项目）是我猜它需要一个（可能不可变的）当前排队项目的列表，因此不受计算期间添加的项目的影响。

于 2013-04-02T12:35:39.577 回答