CODEWITHSUNDEEP
clojure
Mars
Mars

Reputation: 8854

Iteratively apply function to its result without generating a seq

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?

Upvotes: 3

Views: 1408

Answers (4)

A. Webb
A. Webb

Reputation: 26446

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)))

Upvotes: 7

Thumbnail
Thumbnail

Reputation: 13473

To us benighted imperative programmers, a more general pattern is known as a while statement. We can capture it in a macro: 

(defmacro while [bv ; binding vector
                 tf ; test form
                 recf ; recur form
                 retf ; return form
                 ]
  `(loop ~bv (if ~tf (recur ~@recf) ~retf)))

... in your case

(while [x 0, n 3] (pos? n)
  [(inc x) (dec n)]
  x)
; 3
  • I was hoping to type-hint the n, but it's illegal. Maybe it's inferred.
  • Forgive me (re)using while.
  • This isn't quite right: it doesn't allow for computation prior to the recur-form.

We can adapt the macro to do things prior to the recur: 

(defmacro while [bv ; binding vector
                 tf ; test form
                 bodyf ; body form
                 retf ; return form
                 ]
  (let [bodyf (vec bodyf)
        recf (peek bodyf)
        bodyf (seq (conj (pop bodyf) (cons `recur recf)))]
    `(loop ~bv (if ~tf ~bodyf ~retf))))

For example 

(while [x 0, n 3] (pos? n)
  (let [x- (inc x) n- (dec n)] [x- n-])
  x)
; 3

I find this quite expressive. YMMV.

Upvotes: 1

pete23
pete23

Reputation: 2280

Hmmm. I note that Ankur's version is around 10x slower than your original - possibly not the intent, no matter how idiomatic? :-)

Type hinting fn-pow-1 simply for the counter yields substantially faster results for me - around 3x faster.

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

This is around twice as slow as a version which uses inc directly, losing the variability (not hinting x to keep to the spirit of the test)...

(defn inc-pow [x ^long n]
    (if (> n 0)
       (recur (inc x) (dec n))
        x))

I think that for any nontrivial f that fn-pow-3 is probably the best solution.

I haven't found a particularly "idiomatic" way of doing this as it does not feel like common use case outside of micro benchmarks (although would love to be contradicted).

Would be intrigued to hear of a real world example, if you have one?

Upvotes: 2

Ankur
Ankur

Reputation: 33637

That sounds just like composing functions n times.

(defn fn-pow [f p t]
    ((apply comp (repeat t f)) p))

Upvotes: 3

Related Questions