Laziness in clojure. Or "Why didn't I see it was just induction?"

Ever have one of those "A-ha!" moments of clarity?  One of those, "ohh, so that's what Eureka means" events of enlightenment?

So people who have been doing functional programming for awhile, and those more astute than I will probably go, "well, yeah...duh", but I just had a great realization that creating lazy sequences is really just the inverse of recursion.  And what's the inverse of recursion?  Induction.

So, I'm not going to go into what induction is exactly (whether it be mathematically speaking from a weak or strong perspective).

I decided to use a function I've written recursively several times that is of practical benefit (kinda) and turn it into a lazy sequence instead.  Basically this is an interest calculator, given a certain starting principal, an amount that is saved (per year), and an interest.  For my recursive solution, I also give a number of years, and in this case, I walk up to the number of years (starting with year 1).  But for a lazy sequence, this isn't necessary.  This is because, like induction, you don't try to hit the base case.

First, let's look at the recursive solution, then compare it to the lazy one.

(defn savings
  [ base saving interest years ]
  (loop [ b base
          y years ]
    (if (= y 0)
      b
      (do
        (println "year =" y "base = " b)
        (recur (* (+ b saving) interest) (dec y))))))

I did add a little print here so you can see how the interest rate accumulates.  But this is your basic tail-call recursive solution to a problem like this.  You would call it like this:

(savings 0 4000 1.07 10)


Which would calculate how much you would save in 10 years with a starting principal of 0 dollars, saving 4000 a year, and at a 1.07% total interest (yeah, pretty good I admit) for a total of 10 years.

But what about a lazy sequence solution?  And why would you want a lazy solution anyway?  Let's look at the lazy solution first.  In some ways, it is easier.

(defn lazy-savings
  [ base savings interest ]
  (let [acc (* (+ savings base) interest)
        b (+ base acc savings) ]
    (lazy-seq
     (cons b (lazy-savings b savings interest)))))

Notice the call to lazy-seq at the last line from the bottom.  This is what replaces the recursive (in this case implicit recursion...notice I didn't use recur here) call with a lazy one.  Without the recursion being wrapped in lazy-seq, there would be an eager evaluation, meaning that lazy-savings would be called again.  And since there is no base-case as there is with the savings function above, it would eventually blow the call stack.

But why is this solution nicer?  Because it allows you to do more interesting things with it.  Whereas the function savings only returns a single value, lazy-savings returns a seq of values.  Let's call it with the following:


user=> (take 10 (lazy-savings 0 4000 0.07))

You should get this:

(notice the interest rate is only .07 rather than 1.07)

See how you get all the values?  If you wanted the final value, you could have called it with last.

(last (take 10 (lazy-savings 0 4000 0.07)))

Or if you wanted the 5th year, you could have either used (last (take 5 (lazy-savings 0 4000 0.07))) or you could have have done (nth (lazy-savings 0 4000 0.07) 5 ).  In other words, having a lazily generated sequence is more powerful than the recursive version.


So the takeaway is two parts:
1) prefer laziness when possible
2) wrap the recursive part in lazy-seq, and don't worry about ending at the base case

Perhaps the last part bears a little more discussion.  Recursion and induction are really two ways of looking at the same problem.  Both involve a base case...a known condition.  Generally, in an induction, you start with the base case and move forward, showing that if F(n-1) is true, then F(n) is also true (apologies to the math purists, as I can't recall if this is weak or strong induction).  With recursion, you normally "walk backwards" to the base case.  If for example you know that F(0) = 1, and you are solving for F(10), then you apply F(n-1) until you hit F(0) combining all the intermediate results.