StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>As you noted, the <code>[0 1]</code> establishes the base cases: The first two values in the sequence are zero, then one. After that, each value is to be the sum of the previous value and the value before that one. Hence, we can't even compute the third value in the sequence without having at least two that come before it. That's why we need two values with which to start off.</p> <p>Now look at the <code>map</code> form. It says to take the head items from two different sequences, combine them with the <code>+</code> function (adding multiple values to produce one sum), and expose the result as the next value in a sequence. The <code>map</code> form is zipping together two sequences — presumably of equal length — into one sequence of the same length.</p> <p>The two sequences fed to <code>map</code> are different views of the same basic sequence, shifted by one element. The first sequence is "all but the first value of the base sequence". The second sequence is the base sequence itself, which, of course, includes the first value. But what should the base sequence be?</p> <p>The definition above said that each new element is the sum of the previous (<em>Z - 1</em>) and the predecessor to the previous element (<em>Z - 2</em>). That means that extending the sequence of values requires access to the previously computed values in the same sequence. We definitely need a two-element <em>shift register</em>, but we can also request access to our previous results instead. That's what the recursive reference to the sequence called <code>fib-seq</code> does here. The symbol <code>fib-seq</code> refers to a sequence that's a concatenation of zero, one, and then the sum of its own <em>Z - 2</em> and <em>Z - 1</em> values.</p> <p>Taking the sequence called <code>fib-seq</code>, drawing the first item yields the first element of the <code>[0 1]</code> vector — zero. Drawing the second item yields the second element of the vector — one. Upon drawing the third item, we consult the <code>map</code> to generate a sequence and use that as the remaining values. The sequence generated by <code>map</code> here starts out with the sum of the first item of "the rest of" <code>[0 1]</code>, which is one, and the first item of <code>[0 1]</code>, which is zero. That sum is one.</p> <p>Drawing the fourth item consults <code>map</code> again, which now must compute the sum of the second item of "the rest of" the base sequence, which is the one generated by <code>map</code>, and the second item of the base sequence, which is the one from the vector <code>[0 1]</code>. That sum is two.</p> <p>Drawing the fifth item consults <code>map</code>, summing the third item of "the rest of" the base sequence — again, the one resulting from summing zero and one — and the third item of the base sequence — which we just found to be two.</p> <p>You can see how this is building up to match the intended definition for the series. What's harder to see is whether drawing each item is recomputing all the preceding values twice — once for each sequence examined by <code>map</code>. It turns out there's no such repetition here.</p> <p>To confirm this, augment the definition of <code>fib-seq</code> like this to instrument the use of function <code>+</code>:</p> <pre><code>(def fib-seq (lazy-cat [0 1] (map (fn [a b] (println (format "Adding %d and %d." a b)) (+ a b)) (rest fib-seq) fib-seq))) </code></pre> <p>Now ask for the first ten items:</p> <pre><code>> (doall (take 10 fib-seq)) Adding 1 and 0. Adding 1 and 1. Adding 2 and 1. Adding 3 and 2. Adding 5 and 3. Adding 8 and 5. Adding 13 and 8. Adding 21 and 13. (0 1 1 2 3 5 8 13 21 34) </code></pre> <p>Notice that there are eight calls to <code>+</code> to generate the first ten values.</p> <hr> <p>Since writing the preceding discussion, I've spent some time studying the implementation of lazy sequences in Clojure — in particular, the file <em>LazySeq.java</em> — and thought this would be a good place to share a few observations.</p> <p>First, note that many of the lazy sequence processing functions in Clojure eventually use <a href="http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/lazy-seq" rel="noreferrer"><code>lazy-seq</code></a> over some other collection. <code>lazy-seq</code> creates an instance of the Java type <code>LazySeq</code>, which models a small state machine. It has several constructors that allow it to start in different states, but the most interesting case is the one that starts with just a reference to a nullary function. Constructed that way, the <code>LazySeq</code> has neither evaluated the function nor found a delegate sequence (type <code>ISeq</code> in Java). The first time one asks the <code>LazySeq</code> for its first element — via <a href="http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/first" rel="noreferrer"><code>first</code></a> — or any successors — via <a href="http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/next" rel="noreferrer"><code>next</code></a> or <a href="http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/rest" rel="noreferrer"><code>rest</code></a> — it evaluates the function, digs down through the resulting object to peel away any wrapping layers of other <code>LazySeq</code> instances, and finally feeds the innermost object through the java function <code>RT#seq()</code>, which results in an <code>ISeq</code> instance.</p> <p>At this point, the <code>LazySeq</code> has an <code>ISeq</code> to which to delegate calls on behalf of <code>first</code>, <code>next</code>, and <code>rest</code>. Usually the "head" <code>ISeq</code> will be of type <code>Cons</code>, which stores a constant value in its "first" (or "car") slot and another <code>ISeq</code> in its "rest" (or "cdr") slot. That <code>ISeq</code> in its "rest" slot can in turn be a <code>LazySeq</code>, in which case accessing it will again require this same evaluation of a function, peeling away any lazy wrappers on the return value, and passing that value through <code>RT#seq()</code> to yield another <code>ISeq</code> to which to delegate.</p> <p>The <code>LazySeq</code> instances remain linked together, but having <em>forced</em> one (through <code>first</code>, <code>next</code>, or <code>rest</code>) causes it to delegate straight through to some non-lazy <code>ISeq</code> thereafter. Usually that forcing evaluates a function that yields a <code>Cons</code> bound to first value and its tail bound to another <code>LazySeq</code>; it's a chain of generator functions that each yield one value (the <code>Cons</code>'s "first" slot) linked to another opportunity to yield more values (a <code>LazySeq</code> in the <code>Cons</code>'s "rest" slot).</p> <p>Tying this back, in the Fibonacci Sequence example above, <code>map</code> will take each of the nested references to to <code>fib-seq</code> and walk them separately via repeated calls to <code>rest</code>. Each such call will transform at most one <code>LazySeq</code> holding an unevaluated function into a <code>LazySeq</code> pointing to something like a <code>Cons</code>. Once transformed, any subsequent accesses will quickly resolve to the <code>Cons</code>es — where the actual values are stored. When one branch of the <code>map</code> zipping walks <code>fib-seq</code> one element behind the other, the values have already been resolved and are available for constant-time access, with no further evaluation of the generator function required.</p> <p>Here are some diagrams to help visualize this interpretation of the code:</p> <pre><code> +---------+ | LazySeq | fib-seq | fn -------> (fn ...) | sv | | s | +---------+ +---------+ | LazySeq | fib-seq | fn -------> (fn ...) -+ | sv <------------------+ | s | +---------+ +---------+ | LazySeq | fib-seq | fn | | sv -------> RT#seq() -+ | s <------------------+ +---------+ +---------+ +------+ | LazySeq | | ISeq | fib-seq | fn | | | | sv | | | | s ------->| | +---------+ +------+ +---------+ +--------+ +------+ | LazySeq | | Cons | | ISeq | fib-seq | fn | | first ---> 1 | | | sv | | more -------->| | | s ------->| | | | +---------+ +--------+ +------+ +---------+ +--------+ +---------+ | LazySeq | | Cons | | LazySeq | fib-seq | fn | | first ---> 1 | fn -------> (fn ...) | sv | | more -------->| sv | | s ------->| | | s | +---------+ +--------+ +---------+ </code></pre> <p>As <code>map</code> progresses, it hops from <code>LazySeq</code> to <code>LazySeq</code> (and hence <code>Cons</code> to <code>Cons</code>), and the rightmost edge only expands <em>the first time</em> one calls <code>first</code>, <code>next</code>, or <code>rest</code> on a given <code>LazySeq</code>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload