Search code examples
clojureiterationfixed-point-iteration

How do I iterate until a fixed point in Clojure?


I'm frequently in the position that my code reads like so:

(iterate improve x)

And I'm looking for the first value that no longer is an improvement over the previous. Neither filter nor take-while lend themselves to an obvious solution. However, I'm hesitant to write out:

(loop [current x
       next (improve x)]
  (if (= current next)
    current
    (recur next (improve next))))

or:

(let [improvements (iterate improve x)]
  (->> (map vector improvements (rest improvements))
    (filter (partial apply =))
    (ffirst)))

Because at some point this is becoming repetitive and surely fixed point iteration is such a basic task that there must be some kind of library support somewhere, right?


Solution

  • You can use reduce and reduced to stop when necessary. reduced wraps the argument in a special object, which reduce is designed to look for and stop processing immediately returning the wrapped value.

    (def vals (iterate improve x))
    
    (reduce #(if (= %1 %2) (reduced %1) %2) vals)