fibonacci sequence using lazy-cat

[swaroop belur]

Hello all,

Just started learning clojure recently - initial examples were easy to
understand, until I found this example

fibonacci sequence using lazy-cat :
(def fibs (lazy-cat [0 1] (map + fibs (rest fibs))))

I am trying to understand how this works ..not sure i fully comprehend
it.

Can anyone please explain how clojure evaluates this.
1. so if we call (take 5 fibs) for example, what does fibs initially
refer to?
2. how does lazy-cat exactly work over here?

Apologize if this has already been asked earlier.

Thanks
swaroop

[Lauri Pesonen]

Hi swaroop,

2009/7/29 swaroop belur <swaroo...@gmail.com>:

>
> fibonacci sequence using lazy-cat :
> (def fibs (lazy-cat [0 1]   (map + fibs (rest fibs))))
>
> I am trying to understand how this works ..not sure i fully comprehend
> it.
>
> Can anyone please explain how clojure evaluates this.

I'll do my best, but I might get some details wrong.

> 1. so if we call (take 5 fibs) for example, what does fibs initially
> refer to?

Initially fibs will refer to 0, 1, and a function that will return the
rest of the sequence when evaluated. That's what the lazy-cat does: it
combines the first two elements of the sequence [0 1] with the
function for computing the remainder of the sequence.

Se when you ask for the first item in fibs, you'll get 0. When you ask
for the second item in fibs, you'll get 1. When you ask for the third
item in fibs you will get (+ (first fibs) (first (rest fibs))), which
is the same as (+ 0 1). The map form effectively produces this stream
(fixed font):

fibs: 0 1 1 2 3 5...
(rest fibs): 1 1 2 3 5 8...
+: 1 2 3 5 8 13...

which is possible because of lazy evaluation.

> 2. how does lazy-cat exactly work over here?

A lazy sequence is effectively a pair where the first element is a
value (e.g. 0 in fibs) and the second element is a function that when
evaluated returns another pair. That pair will again consist of the
next value in the sequence and a function for producing the rest of
the sequence. As an optimization the lazy sequence will cache the
elements of the sequence when they are evaluated, i.e. when you call
(nth 3 fibs) the third value of the fibs sequence will be cached for
future reference.

So in the fibs example fibs will originally be something like [0, 1,
(map + fibs (rest fibs))] and when you force the evaluation of the
third item fibs will be [0, 1, 1, (map + (rest fibs) (rest (rest
fibs)))], and so on.

Also, lazy-cat is itself lazy, so it will produce the next element of
the resulting sequence only when needed, which allows the user to call
lazy-cat with a number of lazy sequences without forcing them:

user> (def foo (map #(println "foo:" %) (range 0 10)))
#'user/foo
user> (def bar (map #(println "bar:" %) (range 10 20)))
#'user/bar
user> (def baz (lazy-cat foo bar))
#'user/baz
user> baz
(foo: 0
foo: 1
nil foo: 2
nil foo: 3
nil foo: 4
nil foo: 5
nil foo: 6
nil foo: 7
nil foo: 8
nil foo: 9
nil bar: 10
nil bar: 11
nil bar: 12
nil bar: 13
nil bar: 14
nil bar: 15
nil bar: 16
nil bar: 17
nil bar: 18
nil bar: 19
nil nil)

I.e. the println forms are evaluated only when the baz lazy sequence
is actually forced.

HTH

> swaroop

--
! Lauri

[Baishampayan Ghose]

Swaroop,

Welcome to the fantastic world of Clojure! The implementation of the
fibonacci sequence that you cited above is a really neat example of
recursion over data (or corecursion) and lazy eavaluation.

This is possible because we are generating a lazy sequence using the
macro `lazy-cat'.

What `lazy-cat' actually does is that it first calls `lazy-seq' on all
the forms provided to it and then calls `concat' on all of them together.

So in this example, it eventually becomes something like this -

(def fibs (concat (lazy-seq [0 1]) (lazy-seq (map + fibs (rest fibs)))))

Now, how does this work?

Let's take an example.

When you do a (take 1 fibs) it doesn't need to run the `map' function as
the first two elements of `fibs' is already provided in the first lazy-seq.

Ditto for (take 2 fibs).

Now what if you do (take 3 fibs)? We need the third fibonacci number and
for that, we need to execute the map function which runs like this -

(map + [0 1] [1])

Why? you say. Well this is Corecursion :) The value of fibs which is
known till then is [0 1] and that's the value which is used inside the
map function, and with every call of map the value is changed to the
latest known value of fibs.

In case of (take 5 fibs), these are the steps in which the values are
calculated:

[0 1] -> [0 1]
[0 1] + (map + [0 1] [1]) -> [0 1 1]
[0 1] + (map + [0 1 1] [1 1]) -> [0 1 1 2]
[0 1] + (map + [0 1 1 2] [1 1 2]) -> [0 1 1 2 3]

And so on.

This is really cool, isn't it?

Regards,
BG

--
Baishampayan Ghose <b.g...@ocricket.com>
oCricket.com

[swaroop belur]

cool - thanks guys for the detailed reply. crystal clear now -:)

Thx
swaroop

[Stuart Halloway]

While fibs is a nice small example, it is not idiomatic Clojure.
Pointing the fibs var to the head of the list keeps the whole list in
memory as it realizes. Better is to expose fibs as a *function* return
the sequence, so the head is not retained.

(defn fibo []
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

This and several inferior examples are demonstrated in the sample code
for the book [1].

Cheers,
Stu

[1] http://bit.ly/Ew6It