Functional-local, self-referential, lazy fibonacci sequence

Question

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

Now I can make my sequence available in the top-level namespace as follows:

(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 will lose control over garbage collection.

I want to do something like:

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

This obviously won't work, because I will create O (2 ^ n) sequences. I think I'm asking how to create a self-referential lazy sequence in a function 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 [[ab]] [b (+ ab)]) [0 1]))) , I'm interested in the version similar to the canonical Haskell path:

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

This is what I tried to accomplish using my original function. For me, the solution with the naming of cards reads as "add the two previous elements to create a new one", and the solution "lazy cat" reads as "attach the stream with its first delay." How can I “join a stream with its first delay” without having a sequence in the top-level namespace?

Answer 1

Functions defined by fn can be recursive if you put an optional name in front of []. (this example uses the name this )

 user> (defn fibonacci-numbers [] ((fn this [ab] (lazy-seq (cons a (this b (+ ab))))) 0 1)) user> (take 10 (fibonacci-numbers)) (0 1 1 2 3 5 8 13 21 34) 

The actual function that creates the sequence is an anonymous function that only returns the next element on each call. Lack of probability or heap (unless you store the return value of the wrapper function in var somewhere)

Answer 2

 (take 10 (map first (iterate (fn [[ab]] [b (+ ab)]) [0 1]))) ;; (0 1 1 2 3 5 8 13 21 34) 

Or, if you are configured for this using lazy-seq manually:

 (letfn [(fibs ([] (fibs 0 1)) ([ab] (lazy-seq (cons a (fibs b (+ ab))))))] (take 10 (fibs))) ;; (0 1 1 2 3 5 8 13 21 34) 

Answer 3

I had a very similar problem, and in the end I chose the following macro (mostly it’s sugar over the amaline answer with promises):

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

Then you can write:

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

which is what you wanted to write.

PS: rec-seq should be concise for recursive seq.

Answer 4

You can use promise to bind the node manually using 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))