« back

Project Euler Problem 2 - It Pays to be Lazy

06 Nov 2012

Yet Another Spoiler Alert - Project Euler problem 2 solution revealed.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

When working in Clojure using recursion, it is important that you use lazy sequences in order to not have a stack overflow. Consider this taken from Programming Clojure by Stuart Halloway and Aaron Bedra. "Clojure function calls are designated as stack-consuming because they allocate stack frames that use up stack space. In Clojure, you should almost always avoid stack-consuming recursion." There is a foot note that says "For more on how the JVM manages its stack, see "Runtime Data Areas" at here. Feel free to check it out if you are interested in reading the specifics about the JVM, but I will opt to take my own advice, keep a lid on that black box, and just trust that when they say "you should almost always avoid stack consuming recursion", you should. So what should you do instead? Meet Lazy Sequencing.

Lazy sequences invoke their bodies only when needed and cache the result for subsequent calls. This helps to minimize stack consumption. To create them you use lazy-seq.

Let's walk through the Fibonacci sequence generation.

1  
2         (defn lazy-seq-fibo
3             ([]
4                 (concat [0 1] (lazy-seq-fibo 0 1)))
5             ([a b]
6                 (let [n (+ a b)]
7                     (lazy-seq
8                         (cons n (lazy-seq-fibo b n))))))
9     

In the first part, we define a function called lazy-seq-fibo. Something that may look odd and that may be new to you is the fact that I am creating the function with no arguments but then after calling concat [0 1], I am calling the function with arguments. This has to do with Clojure functions enforcing their arity. (their expected number of arguments) To get around this, you can allow your functions to take multiple argument lists and method bodies. I think of it as a conditional.(although it is not) It says that if you pass an argument that looks like this, do this thing. If the argument looks this other way, execute this other code. Of course, all of the ifs are just a way to think of it the code does not use that syntax at all when you are defining the multiple argument lists and bodies.

Whew! Moving on. So after all of that, you should be able to make out that [] and the line after it is referring to what to do if the function is called with no arguments and that [a b] and the section after it is what to do if the function is called with 2 arguments. Let's take a closer look at what is going on with the lines after the argument lists.

1         (defn lazy-seq-fibo
2             ([]
3                 (concat [0 1] (lazy-seq-fibo 0 1)))
4     

This line is saying, "Hey! If you call me with no arguments, I am going to Return a lazy seq with 0 and 1 in it and then keep going with but this time with the arguments of 0 and 1."

Which directs you to this code.

1  
2          ([a b]
3                 (let [n (+ a b)]
4                     (lazy-seq
5                         (cons n (lazy-seq-fibo b n))))))
6     

It says "Hey, when you pass me two arguments, I am going to set them to a and b. Then I am going to take a and b and add them together and assign the value to n. (That is what let [n (+ a b)] does. Then I am going to create a lazy sequence which will add the value of n to the font(cons adds the value to the front of lazy-seq-fibo with the values of b and n." This then recurses. Now something that confused me about the laziness of these sequences was the way that I was used to thinking of recursion in Ruby and the way that ruby values will bubble back up to construct something when the recursion stops. I was thinking of it visually like this...

 1  
 2         (lazy-seq
 3             (cons 1 (lazy-seq-fibo 1 1))))))
 4 
 5             (lazy-seq
 6                 (cons 2 (lazy-seq-fibo 1 2))))))
 7 
 8                 (lazy-seq
 9                     (cons 3 (lazy-seq-fibo b n))))))
10     

and then thinking of the values bubbling up. That, however, is not the lazy way to think about it. While talking to Doug about it, he showed me a way to think about it that made it click. That way was this...

1         (lazy-seq
2             (0 1  (lazy-seq-fibo 0 1))))))
3 
4             (lazy-seq
5                 (0 1 1 (lazy-seq-fibo 1 1))))))
6 
7                 (lazy-seq
8                     (01 1 2 (lazy-seq-fibo 1 2))))))
9     

I found that to be a good way to visualize the recursion and the laziness. I hope this helps you too!

comments powered by Disqus