Saturday, August 27, 2011

More lazy stuff

Nice lazy functions

Last time I explained lazy-when functionand how it helps me in solving euler problems. Now I`ll introduce additional similar functions, and then as always, I`m gonna use them in a couple of euler problems.

First, consider all the times when you need lazy functions that check if the number has more then one property. I wanted to re-write lazy-when to accept a collection of predicates and check the number on all of them:
(defn all? [pred-coll]
  (if (coll? pred-coll) (fn [n] (every? #(% n) pred-coll)) pred-coll))

(defn lazy-when
  ([pred s] (lazy-when pred s inc))
  ([pred n next-n]
    (let [pred-f (all? pred)]
      (if-not (pred-f n)
        (recur pred-f (next-n n) next-n)
        (lazy-seq (cons n (lazy-when pred-f (next-n n) next-n)))))))
I used all?  to transform predicate function. It checks if pred is a collection. If not, it returns pred, but if it is then it returns another function that checks the number on all predicates. The rest of the function is pretty-much same.

Quite often, I need the first number from the lazy seq after some other number:

(defn lazy-next [pred s & next]
  (let [next (if (nil? next) inc (first next))]
    (let [s (if ((all? pred) s) (next s) s)]
      (first (lazy-when pred s next)))))

With next I did the same thing as in lazy-when.  S transformation, however, is interesting. If pred returns true for s, then lazy-next would return that value too. And if you have a loop where you recur on each number from a lazy function, that loop would become infinite, and you usualy don't want that. So s is transformed to the next value that would otherwise be checked only if pred returns false for s.

This function will not serve for prime numbers. If I offer s 2 and next step #(+ % 2), then it would check even numbers and never return. However, if I offer inc for the next step, then my lazy-next becomes much slower. That`s why I created next-prime, as the special case of lazy-next when predicate is prime?
(defn next-prime [prime]
  (if (= prime 2) 3 (lazy-next prime? prime #(+ % 2))))
Finally, euler usually looks for the sum of this-and-that numbers under x. For that reason, I wrote the following functions:

(defn lazy-top [pred s end until? & next]
   (let [next (if (nil? next) inc (first next))]
     (take-while #(until? % end) (lazy-when pred s next))))

(defn lazy-sum [pred s  end until? & next] 
  (let [next (if (nil? next) inc (first next))]
    (reduce + (lazy-top pred s end until? next))))

Little more than one-liners, but the pattern is there often enought so why not have it as a function?

Now, with those, to solve the problem from the last post all it takes is:

(time (println (+ 2 (lazy-sum prime? 3 (reduce * 2 (repeat 6 10)) < #(+ 2 %) ))))

Lets try something else. Problem 046 I only need to discover if the number can be written as the sum of a prime and twice a square, and I have it all:

(defn goldbach? [n]
  (loop [prime 2 root 1]
    (let [goldbach (+ prime (* 2 root root))]
      (cond (= n goldbach) true
            (> prime (dec n)) false
            (> goldbach n) (recur (next-prime prime) 1)
            :else (recur prime (inc root))))))

(time (println (lazy-next [#(not (prime? %)) #(not (goldbach? %))] 33 #(+ % 2))))