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

Answer 1

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.

Answer 2

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.

Answer 3

If you didn't know any imperative languages, would this be intuitive for you?

a = a + 5

WTF? a clearly isn't the same as a + 5.

if a = a + 5, is a + 5 = a?

Why doesn't this work???

if (a = 5) { // should be == in most programming languages
    // do something
}

There are a lot of things that aren't clear unless you've seen it before somewhere else and understood its purpose. For a long time I haven't known the yield keyword and in effect I couldn't figure out what it did.

You think the imperative approach is more legible because you are used to it.

Answer 4

The Clojure code is intuitive to me (because I know Clojure). If you want something that might look more like something you're familiar with, you can try this, an efficient and overly-verbose recursive version:

(use 'clojure.contrib.def)   ; SO's syntax-highlighting still sucks
(defn-memo fib [n]
  (cond (= n 0) 0
        (= n 1) 1
        :else   (+ (fib (- n 1))
                   (fib (- n 2)))))

(def natural-numbers (iterate inc 0))

(def all-fibs
  (for [n natural-numbers]
    (fib n)))

But to someone who doesn't know what recursion or memoization are, that isn't going to be intuitive either. The very idea of "infinite lazy sequences" probably isn't intuitive to the majority of programmers. I can't guess what's in your brain so I don't know what a more intuitive Clojure function would look like to you, other than "looks more like Python".

To someone who doesn't know programming, all of this stuff is going to look like gibberish. What's a loop? What's a function? What is this yield thing? That's where we all start. Intuitiveness is a function of what you've learned so far. Non-intuitive code is code you aren't familiar with yet. Extrapolating from "I know this" to "It's inherently more intuitive" is wrong.