Iteratively apply function to its result without generating a seq

Question

This is one of those "Is there a built-in/better/idiomatic/clever way to do this?" questions.

I want a function--call it fn-pow--that will apply a function f to the result of applying f to an argument, then apply it to the result of applying it to its result, etc., n times. For example,

(fn-pow inc 0 3)

would be equivalent to

(inc (inc (inc 0)))

It's easy to do this with iterate:

(defn fn-pow-0
  [f x n]
  (nth (iterate f x) n))

but that creates and throws away an unnecessary lazy sequence.

It's not hard to write the function from scratch. Here is one version:

(defn fn-pow-1
  [f x n]
  (if (> n 0) 
    (recur f (f x) (dec n))
    x))

I found this to be almost twice as fast as fn-pow-0, using Criterium on (fn-pow inc 0 10000000).

I don't consider the definition of fn-pow-1 to be unidiomatic, but fn-pow seems like something that might be a standard built-in function, or there may be some simple way to define it with a couple of higher-order functions in a clever arrangement. I haven't succeeded in discovering either. Am I missing something?

Answer 1

The built-in you are looking for is probably dotimes. I'll tell you why in a round-about fashion.

Time

What you are testing in your benchmark is mainly the overhead of a level of indirection. That (nth (iterate ...) n) is only twice as slow as what compiles to a loop when the body is a very fast function is rather surprising/encouraging. If f is a more costly function, the importance of that overhead diminishes. (Of course if your f is low-level and fast, then you should use a low-level loop construct.)

Say your function takes ~ 1 ms instead

(defn my-inc [x] (Thread/sleep 1) (inc x))

Then both of these will take about 1 second -- the difference is around 2% rather than 100%.

(bench (fn-pow-0 my-inc 0 1000))
(bench (fn-pow-1 my-inc 0 1000))

Space

The other concern is that iterate is creating an unnecessary sequence. But, if you are not holding onto the head, just doing an nth, then you aren't really creating a sequence per se but sequentially creating, using, and discarding LazySeq objects. In other words, you are using a constant amount of space, though generating garbage in proportion to n. However, unless your f is primitive or mutating its argument, then it is already producing garbage in proportion to n in producing its own intermediate results.

Reducing Garbage

An interesting compromise between fn-pow-0 and fn-pow-1 would be

(defn fn-pow-2 [f x n] (reduce (fn [x _] (f x)) x (range n)))

Since range objects know how to intelligently reduce themselves, this does not create additional garbage in proportion to n. It boils down to a loop as well. This is the reduce method of range:

public Object reduce(IFn f, Object start) {
    Object ret = f.invoke(start,n);
    for(int x = n+1;x < end;x++)
            ret = f.invoke(ret, x);
    return ret;
}

This was actually the fastest of the three (before adding primitive type-hints on n in the recur version, that is) with the slowed down my-inc.

Mutation

If you are iterating a function potentially expensive in time or space, such as matrix operations, then you may very well be wanting to use (in a contained manner) an f that mutates its argument to eliminate the garbage overhead. Since mutation is a side effect, and you want that side effect n times, dotimes is the natural choice.

For the sake of example, I'll use an atom as a stand-in, but imagine bashing on a mutable matrix instead.

(def my-x (atom 0))

(defn my-inc! [x] (Thread/sleep 1) (swap! x inc))

(defn fn-pow-3! [f! x n] (dotimes [i n] (f! x)))