Function-local, self-referential, lazy fibonacci sequence

Question

I would like to create a function that returns a lazily extended infinite sequence of Fibonacci numbers.

Right now, I can make my sequence available in the top-level namespace like this:

(def fibonacci-numbers
  (lazy-cat [0 1] (map + fibonacci-numbers (rest fibonacci-numbers))))

However, this means that if I start consuming a lot of them, I lose control over the garbage collection.

I am looking to do something like:

(defn fibonacci-numbers-fn []
  (lazy-cat [0 1] (map + (fibonacci-numbers-fn) (rest (fibonacci-numbers-fn)))))

This clearly will not work because I will end up creating O(2^n) sequences. I think I am asking how to create a self-referential lazy sequence in a function-local namespace. What should I do?

EDIT: Although I like the popular solution posted by amalloy and found all over the internet defn fibs [] (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1]))), I'm interested in a version similar to the canonical Haskell way:

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

This is what I was trying to accomplish with my original function. To me, the map-iterate solution reads like "add the previous two elements to create a new one" and the lazy-cat solution reads like "join a stream with its first lag". How can I "join a stream with its first lag" without having the sequence in the top-level namespace?

Answer 1

(take 10 (map first (iterate (fn [[a b]]
                               [b (+ a b)])
                             [0 1])))

;; (0 1 1 2 3 5 8 13 21 34)

Or if you're set on doing it with lazy-seq by hand:

(letfn [(fibs
          ([]
             (fibs 0 1))
          ([a b]
             (lazy-seq
               (cons a (fibs b (+ a b))))))]
  (take 10 (fibs)))

;; (0 1 1 2 3 5 8 13 21 34)

Answer 2

Functions defined by the fn form can be recursive if you put an optional name before the []. (in this example the name used is this)

user> (defn fibonacci-numbers []
        ((fn this [a b] (lazy-seq (cons a (this b (+ a b))))) 0 1))

user> (take 10 (fibonacci-numbers))
(0 1 1 2 3 5 8 13 21 34)

The actual function producing the sequence is the anonymous function which only produces the next element each time it is called. No chance of a stack or heap overflow (unless you hold the return value of the enclosing function in a var somewhere)

Answer 3

I had a very similar issue, and eventually opted for the following macro (which is basically some sugar over amalloy's answer involving promises):

(defmacro rec-seq [name expr]
   `(let [p# (promise)
           s# (lazy-seq (let [~name @p#] ~expr))]
       (deliver p# s#)
        s#))

This then lets you write:

(defn  fibonacci-numbers-fn []
   (rec-seq fibs (lazy-cat [0 1] (map +' fibs (rest fibs)))))

which is almost what you wanted to write.

PS: rec-seq is meant to be short for recursive-seq.

Answer 4

You can use a promise to tie the knot, doing manually what haskell does automatically:

(defn fibs []
  (let [fibs (promise)]
    @(doto fibs
       (deliver (list* 0 1 (lazy-seq (map +' @fibs (rest @fibs))))))))

Answer 5

Perhaps letfn is what you are looking for?

(def fibo-nums
  (letfn [(fibo-num-fn []
            (lazy-cat [0 1]
              (map + (fibo-num-fn) (rest (fibo-num-fn)))))]
    fibo-num-fn))