在Scala中的固定点

Question

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

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

  if (newClusters == clusters) {
    return clusters
  }

  clusters = newClusters
}

我希望计算一个固定点，也就是执行一个函数使其结果稳定。你知道有哪些高阶函数适合我的目的吗？

- user3267915

Answer 1

这是一篇从Martin Odersky的《Scala By Example》（第五章“一等函数”第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有助于确保先验阈值的终止。

- elm

---

抱歉，但我并没有看到任何与我的方法不同之处，除了你使用了递归。不幸的是，这并没有使我的代码更短或更易读。 - user3267915

没关系，我把“higher-level functions”误解为“first-class functions”了 :) 或许“library/package functions”是另一个能传达这个问题的名称 :) - elm

Answer 2

另一种方法是将著名的一行斐波那契数计算（https://dev59.com/-Wkw5IYBdhLWcg3wfKdA#9864521）和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

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

- Vladimir Matveev