CODEWITHSUNDEEP
clojurefunctional-programming
yalis
yalis

Reputation: 1518

Execute function until certain condition holds

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.

Upvotes: 12

Views: 5344

Answers (6)

skuro
skuro

Reputation: 13514

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)

Upvotes: 7

user1980317
user1980317

Reputation: 51

How about drop-while 

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

Upvotes: 3

dbyrne
dbyrne

Reputation: 61011

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

Upvotes: 4

mikera
mikera

Reputation: 106351

I don't think there is a core function that does this exactly and efficiently. Hence I would do this with loop/recur as follows:

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

Loop/recur is very efficient since it requires no additional storage and is implemented as a simple loop in the JVM.

If you're going to do this a lot, then you can always encapsulate the pattern in a macro.

Upvotes: 2

Alex Stoddard
Alex Stoddard

Reputation: 8344

Sounds like you want the while macro.

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

Usage: (while test & body) Repeatedly executes body while test expression is true. Presumes some side-effect will cause test to become false/nil. Returns nil

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

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

Usage: (for seq-exprs body-expr) List comprehension. Takes a vector of one or more binding-form/collection-expr pairs, each followed by zero or more modifiers, and yields a lazy sequence of evaluations of expr. Collections are iterated in a nested fashion, rightmost fastest, and nested coll-exprs can refer to bindings created in prior binding-forms. Supported modifiers are: :let [binding-form expr ...], :while test, :when test.

(take 100 (for [x (range 100000000) y (range 1000000) :while (< y x)] [x y]))

Upvotes: 0

amalloy
amalloy

Reputation: 91857

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.

Upvotes: 4

Related Questions