Laziness is good for you

Clojure has a nice little type called LazySeq which supports the ISeq interface, and which is accessed using the lazy-seq function in core.clj.
(defmacro lazy-seq
  "Takes a body of expressions that returns an ISeq or nil, and yields
  a Seqable object that will invoke the body only the first time seq
  is called, and will cache the result and return it on all subsequent
  seq calls." 
  [& body]
  (list ‘new ‘clojure.lang.LazySeq (list* ‘#^{:once true} fn* [] body)))

The LazySeq type contains only two fields.
private IFn fn;
private ISeq s;

When we construct the instance we provide the generator function, and this function is used by the seq method:
final synchronized public ISeq seq(){
    if(fn != null)
        {
        try
            {
            s = RT.seq(fn.invoke());
            fn = null;
            }
        catch(Exception e)
            {
            throw new RuntimeException(e);
            }
        }
    return s;
}

to generate a sequence when it is needed in the implementation of the ISeq methods. For example, next,
public ISeq next(){
    seq();
    if(s == null)
        return null;
    return s.next();   
}

Note that the seq method is synchronized, so it is thread safe, and if the method is successful, the generator is guaranteed to only be called once.

My favourite use for such a function, is to implement a sequence of all of the primes.
(def primes
     (letfn [(filter-by [seq divisors]
         (let [next (first seq)]
            (if (some #(= (rem next %) 0) divisors)
               (recur (rest seq) divisors)
              (lazy-seq
                 (cons next (filter-by (rest seq) (cons next divisors)))))))]
        (filter-by (iterate (partial + 1) 2) nil)))

user=> (take 10 primes)
(2 3 5 7 11 13 17 19 23 29)
user=> (take 50 primes)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229)

By the way lazy-seq is implemented, the above function effectively caches the calculations that it has done so far. The trick for seeing this, is to add a print statement within the body. This caching improves the performance, but the overhead in memory could be too much for some scenarios.
(def primes
     (letfn [(filter-by [seq divisors]
         (print "called")
         (let [next (first seq)]
            (if (some #(= (rem next %) 0) divisors)
               (recur (rest seq) divisors)
              (lazy-seq
                 (cons next (filter-by (rest seq) (cons next divisors)))))))]
        (filter-by (iterate (partial + 1) 2) nil)))

user=> (take 10 primes)
(calledcalledcalled2 calledcalled3 calledcalledcalledcalled5 calledcalled7 calledcalledcalledcalled11 calledcalled13 calledcalledcalledcalled17 calledcalledcall
edcalledcalledcalled19 calledcalled23 29)
user=> (take 10 primes)
(2 3 5 7 11 13 17 19 23 29)
user=> (take 12 primes)
(2 3 5 7 11 13 17 19 23 calledcalledcalledcalledcalledcalled29 calledcalledcalledcalled31 37)
user=> (take 12 primes)
(2 3 5 7 11 13 17 19 23 29 31 37)

There’s another type of object, Delay, that has the same kind of properties. A Delay, constructed using the delay macro, wraps a form and evaluates the form the first time the Delay is forced, either by calling the force function or by dereferencing it. Subsequent calls of these functions return the cached value.
user=> (def a (delay (do (print "called") 30)))
#’user/a
user=> @a
called30
user=> @a
30
user=> (def a (delay (do (print "called") 30)))
#’user/a
user=> (force a)
called30
user=> (force a)
30

Advertisements
This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s