repeat-until-stable

[bo-tato]

This is a utility function to consider adding to serapeum. It repeatedly applies a function to an argument until the output is the same as the input: (repeat-until-stable #'f x) will call (f x) then (f (f x)) then (f (f (f x))) etc until the result is unchanging. Every year I use it in a couple advent of code problems, and occasionally outside of advent of code. Here is prior art of people making the same utility function in clojure and haskell. I chose the name repeat-until-stable as it seems people either call it repeat-until-stable or iterate-until-stable and iterate names are used by the iterate package and the only related function I find in any lisp library is repeat-function from agutil, so it seemed a better fit for existing CL names.

Here is a simple tail-recursive implementation:

(defun repeat-until-stable (f x &key (test #'eql))
  "Repeatedly call (f x), then (f (f x)), etc until the result doesn't change
according to TEST."
  (let ((next (funcall f x)))
    (if (funcall test next x)
        x
        (repeat-until-stable f next :test test))))

sbcl at least on default settings optimizes the tail recursion, but maybe to be safe on all implementations here is a non-recursive version:

(defun repeat-until-stable (f x &key (test #'eql))
  "Repeatedly call (f x), then (f (f x)), etc until the result doesn't change
according to TEST."
  (loop for previous = current
        for current = x then (funcall f current)
        when (funcall test previous current)
          return current))

If you'd like to add this utility function to reduce your workload a little I can submit a PR adding this and some unit tests and documentation to reference.md and whatever else is needed.

[ruricolist]

This looks like a good idea. It might also be a good use case for defloop.

One possible enhancement I would like to see is the ability to specify a maximum recursion depth as a keyword argument.

[bo-tato]

Interesting I didn't know about defloop/nlet for guaranteeing tail recursion. Here's an implementation using defloop and accepting a keyword argument with maximum recursion depth:

(defloop repeat-until-stable (f x &key (test #'eql) max-depth)
  "Repeatedly call (f x), then (f (f x)), etc until the result doesn't change
according to TEST. If MAX-DEPTH is specified, stop after calling F MAX-DEPTH times."
  (if (eql 0 max-depth)
      x
      (let ((next (funcall f x)))
        (if (funcall test next x)
            x
            (repeat-until-stable f next :test test
                                        :max-depth (when max-depth
                                                     (1- max-depth)))))))

[ruricolist]

This looks good if you'd like to make a pull request.