Fixed point in Scala

Question

Is there a shortcut for the following code snippet?

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

  if (newClusters == clusters) {
    return clusters
  }

  clusters = newClusters
}

I would like to calculate the fixed point, i.e. execute a function such that its result is stable. Are you aware of any higher-order functions that would suit my purposes?

elm · Answer 1 · 2014-03-06T11:02:42.367

1

An adaptation from a fixpoint calculation example from Scala By Example by Martin Odersky (Chapter 'First-Class functions', Section 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)
}

where function f: Clusters => Clusters delivers new candidate clusters, and initApprox corresponds to the first, initial guess on a fixpoint. Function isApproxFeasible helps ensuring termination for a priori threshold.

edited Mar 06 '14 at 11:02

answered Mar 06 '14 at 10:32

elm

20,117
14
67
113

Sorry, but I do not see any difference to my approach apart from the fact that you're using recursion. Unfortunately, it does not make my code any shorter or more readable. – user3267915 Mar 06 '14 at 11:33
No worries, misinterpreted "higher-level functions" by "first-class functions" :) Perhaps library/package functions may be another naming that conveys the enquiry :) – elm Mar 06 '14 at 11:38

score 0 · Answer 2 · answered Oct 02 '18 at 17:23

An alternative approach would be to combine the famous one-line Fibonacci numbers computation (https://stackoverflow.com/a/9864521/788207) and takeWhile:

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

Another approach, which would not require constructing a stream object in memory, is to use iterators:

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

Although the imperative solution will likely be more efficient because it is a simple loop without stream construction or closures invocation.

Fixed point in Scala

2 Answers2