Lazy infinite sequences in Clojure and Python


Question

Here are the best implementations I could find for lazy infinite sequences of Fibonacci numbers in both Clojure and Python:

Clojure:

(def fib-seq (lazy-cat [0 1]
 (map + fib-seq (rest fib-seq))))

sample usage:

 (take 5 fib-seq)

Python:

def fib():
 a = b = 1
 while True:
  yield a
  a,b = b,a+b

sample usage:

for i in fib():
  if i > 100:
    break
  else:
    print i

Obviously the Python code is much more intuitive.

My question is: Is there a better (more intuitive and simple) implementation in Clojure ?

Edit

I'm opening a follow up question at Clojure Prime Numbers

1
15
5/23/2017 11:44:16 AM

Accepted Answer

I like:

(def fibs 
  (map first 
       (iterate 
           (fn [[ a, b       ]]  
                [ b, (+ a b) ]) 
           [0, 1])))     

Which seems to have some similarities to the python/generator version.

14
8/23/2010 12:25:30 PM

I agree with Pavel, what is intuitive is subjective. Because I'm (slowly) starting to grok Haskell, I can tell what the Clojure code does, even though I've never written a line of Clojure in my life. So I would consider the Clojure line fairly intuitive, because I've seen it before and I'm adapting to a more functional mindset.

Let's consider the mathematical definition, shall we?

       { 0                   if x = 0 }
F(x) = { 1                   if x = 1 }
       { F(x - 1) + F(x - 2) if x > 1 }

This is less than ideal, formatting wise - those three brackets lined up should be one giant bracket - but who's counting? This is a pretty clear definition of the Fibonacci sequence to most people with a mathematical background. Let's look at the same thing in Haskell, because I know it better than Clojure:

fib 0 = 0
fib 1 = 1
fib n = fibs (n - 1) + fibs (n - 2)

This is a function, fib, that returns the nth Fibonacci number. Not exactly what we had in Python or Clojure, so let's fix that:

fibs = map fib [0..]

This makes fibs an infinite list of Fibonacci numbers. fibs !! 1 is 1, fibs !! 2 is 1, fibs !! 10 is 55, and so on. However, this is probably quite inefficient, even in a language that relies on heavily optimized recursion such as Haskell. Let's look at the Clojure definition in Haskell:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

The first couple of characters are pretty simple: 0 : 1 : makes a list with elements 0 and 1, and then some more. But what's all the rest of that? Well, fibs is the list we've already got, and tail fibs calls the tail function on our list so far, which returns the list starting at the 2nd element (sort of like in Python saying fibs[1:]). So we take these two lists - fibs and tail fibs - and we zip them together with the + function (operator) - that is, we add the matching elements of each. Let's look:

fibs       = 0 : 1 : ...
tail fibs  = 1 : ...
zip result = 1 : ...

So our next element is 1! But then we add that back onto our fibs list, and look what we get:

fibs       = 0 : 1 : 1 : ...
tail fibs  = 1 : 1 : ...
zip result = 1 : 2 : ...

What we have here is a recursive list definition. As we add more elements to the end of fibs with our zipWith (+) fibs (tail fibs) bit, more elements become avaliable for us to work with when adding elements. Note that Haskell by default is lazy, so just making an infinite list like that won't crash anything (just don't try to print it).

So while this is perhaps theoretically the same as our mathematical definition before, it saves the results in our fibs list (sort of an auto-memoization) and we rarely have the problems that might be experienced in a naive solution. For completeness, let's define our fib function in terms of our new fibs list:

fib n = fibs !! n

If I didn't lose you yet, that's good, because that means you understand the Clojure code. Look:

(def fib-seq (lazy-cat [0 1]
 (map + fib-seq (rest fib-seq))))

We make a list, fib-seq. It starts with two elements, [0 1], just like our Haskell example. We do a lazy concatenation of these two initial elements with (map + fib-seq (rest fib-seq)) - assuming rest does the same thing that tail does in Haskell, we're just combining our list with itself at a lower offset, and then combining these two lists with the + operator/function.

After working this through your head a few times, and exploring some other examples, this method of generating fibonacci series becomes at least semi-intuitive. It's at least intuitive enough for me to spot it in a language I don't know.


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon