Execute function until certain condition holds

Question

I want to repeatedly apply some function to some state until a condition holds true.

Function f takes a state, modifies it and returns it. Apply f again to the returned state and so on.

I think this would work.

(first (filter pred (iterate f x)))

But it's a bit ugly. Plus memory consumption is not ideal since iterator would be forced to evaluate and keep intermediate states until the state on which pred holds true is returned, at which point intermediate states should be garbage collected.

I know you can write a simple recursive function:

(loop [f x p] (if (p x) x (recur f (f x) p))

But I'm looking for a core library function (or some combination of functions) that does the same thing with the same memory efficiency.

Answer 1

What you really want is take-while:

take-while
function

Usage: (take-while pred coll)
Returns a lazy sequence of successive items from coll while
(pred item) returns true. pred must be free of side-effects.

EDIT

A way to use higher order functions to achieve the result you want might be to wrap your function into something to be consumed by trampoline, namely a function that will either return the final result or another function which will execute the next step. Here's the code:

(defn iterable [f]            ; wraps your function
  (fn step [pred x]           ; returns a new function which will accept the predicate
    (let [y (f x)]            ; calculate the current step result
      (if (pred y)            ; recursion stop condition
        (fn [] (step pred y)) ; then: return a new fn for trampoline, operates on y
        y))))                 ; else: return a value to exit the trampoline

The iterative execution would go as follows:

(trampoline (iterable dec) pos? 10)

Answer 2

Not sure what you mean by iterator - you're using it as if it were iterate, and I just want to be sure that's what you mean. At any rate, your solution looks fine to me and not at all ugly. And memory is not an issue either: iterate is free to throw away intermediate results whenever it's convenient because you aren't keeping any references to them, just calling filter on it in a "streaming" way.

Answer 3

I think you should just make your loop a simple recursive function:

(defn do-until [f x p]
  (if (p x) x (recur f (f x) p)))

(do-until inc 0 #(> % 10)) ; => 11

Answer 4

How about drop-while

(first (drop-while (comp not pred) (iterate f x))