Execute a function until a certain condition is met

Question

I want to reapply some function to some state until the condition is met.

The f function takes state, changes it, and returns. Apply f again to the returned state, etc.

I think it will work.

(first (filter pred (iterate fx))) 

But it's a little ugly. Plus, memory consumption is not ideal, since the iterator will be forced to evaluate and save intermediate states until the state to which pred is true is returned, and at that moment the intermediate states should be garbage collected.

I know that you can write a simple recursive function:

 (loop [fxp] (if (px) x (recur f (fx) p)) 

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

Answer 1

What you really need 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 desired result may be to turn your function into something that trampoline will consume, namely a function that will either return the final result, or another function that will perform the next step. Here is the code:

 (defn iterable [f] ; wraps your function (fn step [pred x] ; returns a new function which will accept the predicate (let [y (fx)] ; 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 

Iterative execution will look like this:

 (trampoline (iterable dec) pos? 10) 

Answer 2

Not sure what you mean by iterator - you use it as if iterate , and I just want to be sure what you mean. Anyway, your decision looks good to me and not at all ugly. And memory is also not a problem: iterate can freely discard intermediate results when it is convenient, because you do not store any references to them, just calling the filter on it in a "streaming" way.

Answer 3

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

 (defn do-until [fxp] (if (px) x (recur f (fx) p))) (do-until inc 0 #(> % 10)) ; => 11 

Answer 4

How about drop-while

 (first (drop-while (comp not pred) (iterate fx)) 

Answer 5

I do not think that there is a basic function that does this accurately and efficiently. Therefore, I would do this with loop / recur as follows:

 (loop [x initial-value] (if (pred x) x (recur (fx)))) 

Loop / recur is very efficient because it does not require additional storage and is implemented as a simple loop in the JVM.

If you are going to do this a lot, then you can always encapsulate the template in a macro.

Answer 6

Looks like you want a while macro.

http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/while

Usage: (while test and body) Repeats the body, while the test expression is true. suggesting some side effect will cause the test to become false / zero. Returns nil

In a slightly different use case, the for macro supports: when and: while options.

http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/for

Usage: (for seq-exprs body-expr) List comprehension. Accepts the vector of one or more anchor-form / collection-expr pairs, followed by zero or more modifiers, and gives a lazy sequence of expr evaluations. Collections are repeated in a nested manner, the fastest, fastest, and nested coll-exprs can reference the bindings created previously by the binding form. Supported modifiers :: let [binding-form expr ...] ,: while test ,: during testing.

(accept 100 (for [x (range 100000000) y (range 1000000): while (<yx)] [xy]))