scala - Scala中的定点

Question

以下代码段是否有快捷方式？

while (true) {
  val newClusters = this.iterate(instances, clusters)

  if (newClusters == clusters) {
    return clusters
  }

  clusters = newClusters
}

我想计算固定点，即执行一个函数，使其结果稳定。您是否知道任何适合我目的的高阶函数？

Answer 1

改编自 Martin Odersky 的Scala By Example的定点计算示例（第 5.3 节“一流函数”章节），

val instances = ...  // from question statement 

def isApproxFeasible(x: Clusters, y: Clusters) = some_distance_x_y < threshold

def fixedPoint(f: Clusters => Clusters)(initApprox: Clusters) = {
  def iterate(approx: Clusters): Clusters = {
    val newClusters = f(approx)
    if (isCloseEnough(approx, newClusters)) newClusters
    else iterate(newClusters)
  }
  iterate(initApprox)
}

其中函数f: Clusters => Clusters提供新的候选集群，并initApprox对应于固定点上的第一个初始猜测。函数isApproxFeasible有助于确保先验阈值的终止。

Answer 2

另一种方法是结合著名的单线斐波那契数计算 ( https://stackoverflow.com/a/9864521/788207 ) 和takeWhile：

val reductions = Stream.iterate(clusters)(this.iterate(instances, _))
(reductions, reductions.tail).zipped.takeWhile { case (p, n) => p != n }.last._1

另一种不需要在内存中构造流对象的方法是使用迭代器：

Iterator.iterate(clusters)(this.iterate(instances, _))
  .sliding(2)
  .dropWhile { case prev +: next +: _ => prev != next }
  .next()
  .head

尽管命令式解决方案可能会更有效，因为它是一个没有流构造或闭包调用的简单循环。