Tuesday, February 17, 2015

Tweaking the Power Limit

After posting the power-limit function earlier I found myself thinking about the inelegance of the expression. I like the approach, but the code seems much more verbose than should be required. In particular, the (partial apply not=) expression seemed too long for something so simple.

As a reminder, here is my last iteration on the function:

(defn power-limit [f a]
  (let [s (iterate f a)]
    (ffirst
      (drop-while (partial apply not=)
                  (map vector s (rest s))))))
The first thing that occurred to me here is the use of vector to pair up the values. It's this pairing that makes the predicate for drop-while more complex. Perhaps I should avoid the pair?

The reason for this pair is so that they can be compared for equality in the next step. So why not just compare them straight away? But that would leave me with a true/false value, when I need to get the values being compared when they are equal. What I really needed was a false/value result, and this reminded me of how a set lookup works. For instance (#{2} 1) returns nil, while (#{2} 2) returns 2. This is what I need, so why not try it?
(defn power-limit [f a]
  (let [s (iterate f a)]
    (first
      (drop-while not
                  (map #(#{%1} %2) s (rest s))))))
The anonymous function in the map looks a little like line noise, but it's not too bad.

Now that the result of map is a value and not a pair, we only need first and not ffirst. The drop-while predicate also gets simpler, just needing a not, but it's still verbose. However, the drop-while is just removing the leading nils from the results of the map, so let's move to keep instead:
(defn power-limit [f a]
  (let [s (iterate f a)]
    (first
      (keep #(#{%1} %2) s (rest s)))))
So does this work?
=> (power-limit has-fixpoint 0)
ArityException Wrong number of args (3) passed to: core/keep clojure.lang.AFn.throwArity (AFn.java:429)

Doh! It turns out that keep only has a single arity and does not accept multiple collections like map does. So I'm stuck doing a (drop-while not ...) or (filter identity ...) or (remove nil? ...) to wrap the map operation.

The fact that I can remove all the leading nils, or all the nils (since all the nils are at the head here), made me take a step back again to think about what I'm doing. Once all the nils are out of the picture, I'm just looking for the first item in the resulting list. That's when I remembered some which tests all the items in a list according to its predicate, returning truthy/falsey, but the way it does this is to just return the first non-falsey value its predicate gives. So I still need to wrap the map operation, but I can drop the call to first.
(defn power-limit [f a]
  (let [s (iterate f a)]
    (some identity (map #(#{%1} %2) s (rest s)))))
Not as pretty as the very first implementation (which used loop/recur) but now it's not so verbose, so I'm feeling happier about it.

6 comments:

Jens said...

Hi, here is my swiss army function for fixedpoint computations:

(defn fixedpoint [F guess eq?]
(let [guess' (F guess)]
(if (eq? guess' guess)
guess
(recur F guess' eq?))))

It is parameterized to also take a function that decides whether the fixed point was reached. So you can also use it for real numbers, sets, ...

Paul G said...

I called it fixed-point at my REPL too, but the final form was called power-limit to match the APL stuff.

Your function is the same as my first attempt, though I do like the parameterization of the equality test. I'd make it multiple arity though...

(defn fixed-point
 ([F guess] (fixed-point F guess =))
 ([F guess eq?]
  (let [guess' (F guess)]
   (if (eq? guess' guess)
    guess
    (recur F guess' eq?)))))

Thanks.

web lol said...

KUL POST

servis printer said...

OMG, i'am not understand sir

Steve said...

I have a similar fixed-point function. My tweak is to add a limit to avoid infinite recursion.

(defn fixed-point
([f] (fixed-point f 0))
([f guess] (fixed-point f guess 1000))
([f guess limit] (fixed-point f guess limit =))
([f guess limit eq?]
(when (pos? limit)
(let [guess' (f guess)]
(if (eq? guess' guess)
guess
(recur f guess' (dec limit) eq?))))))

David Smith said...

Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a Java developer learn from Java Training in Chennai. or learn thru Java Online Training in India . Nowadays Java has tons of job opportunities on various vertical industry.