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
> 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
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
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> (def bar (map #(println "bar:" %) (range 10 20)))
user> (def baz (lazy-cat foo bar))
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
I.e. the println forms are evaluated only when the baz lazy sequence
is actually forced.
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
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] )
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
[0 1] -> [0 1]
[0 1] + (map + [0 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?
Baishampayan Ghose <b.g...@ocricket.com>