StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>My Clojure is a bit rusty, but this seems to be a literal translation of the famous Haskell one-liner:</p> <pre><code>fibs = 0 : 1 : zipWith (+) fibs (tail fibs) </code></pre> <p>[I'm going to be using pseudo-Haskell, because it's a little bit more succinct.]</p> <p>The first thing you need to do, is simply let laziness sink in. When you look at a definition like this:</p> <pre><code>zeroes = 0 : zeroes </code></pre> <p>Your immediate gut reaction as a strict programmer would be "ZOMG infinite loop! Must fix bug!" But it isn't an infinite loop. This is a <em>lazy</em> infinite loop. If you do something stupid like</p> <pre><code>print zeroes </code></pre> <p>Then, yes, there <em>will</em> be an infinite loop. But as long as you simply use a finite number of elements, you will never notice that the recursion doesn't actually terminate. This is <em>really</em> hard to get. I still don't.</p> <p>Laziness is like the monetary system: it's based on the assumption that the vast majority of people never use the vast majority of their money. So, when <em>you</em> put $1000 in the bank, they don't keep it in their safe. They lend it to someone else. Actually, they <em>leverage</em> the money, which means that they lend $5000 to someone else. They only ever need enough money so that they can quickly reshuffle it so that it's <em>there</em> when you are looking at it, giving you the <em>appearance</em> that they actually keep your money.</p> <p>As long as they can manage to always give out money when you walk up to an ATM, it doesn't actually matter that the vast majority of your money isn't there: they only need the small amount you are withdrawing at the point in time when you are making your withdrawal.</p> <p>Laziness works the same: whenever you look at it, the value is there. If you look at the first, tenth, hundreth, quadrillionth element of <code>zeroes</code>, it <em>will</em> be there. But it will <em>only</em> be there, <em>if</em> and <em>when</em> you look at it, <em>not</em> before.</p> <p>That's why this inifintely recursive definition of <code>zeroes</code> works: as long as you don't try to look at the <em>last</em> element (or <em>every</em> element) of an infinite list, you are safe.</p> <p>Next step is <code>zipWith</code>. (Clojure's <code>map</code> is just a generalization of what in other programming languages are usually three different functions: <code>map</code>, <code>zip</code> and <code>zipWith</code>. In this example, it is used as <code>zipWith</code>.)</p> <p>The reason why the <code>zip</code> family of functions is named that way, is because it actually works like a zipper, and that is also how to best visualize it. Say we have some sporting event, where every contestant gets two tries, and the score from both tries is added up to give the end result. If we have two sequences, <code>run1</code> and <code>run2</code> with the scores from each run, we can calculate the end result like so:</p> <pre><code>res = zipWith (+) run1 run2 </code></pre> <p>Assuming our two lists are <code>(3 1 6 8 6)</code> and <code>(4 6 7 1 3)</code>, we line both of those lists up side by side, like the two halves of a zipper, and then we zip them together using our given function (<code>+</code> in this case) to yield a new sequence:</p> <pre><code>3 1 6 8 6 + + + + + 4 6 7 1 3 = = = = = 7 7 13 9 9 </code></pre> <p>Contestant #3 wins.</p> <p>So, what does our <code>fib</code> look like?</p> <p>Well, it starts out with a <code>0</code>, then we append a <code>1</code>, then we append the sum of the infinite list with the infinite list shifted by one element. It's easiest to just draw that out:</p> <ul> <li><p>the first element is zero:</p> <pre><code>0 </code></pre></li> <li><p>the second element is one:</p> <pre><code>0 1 </code></pre></li> <li><p>the third element is the first element plus the first element of the rest (i.e. the second element). We visualize this again like a zipper, by putting the two lists on top of each other.</p> <pre><code>0 1 + 1 = 1 </code></pre></li> <li><p>Now, the element that we just computed is not just the <em>output</em> of the <code>zipWith</code> function, it is at the same time also the <em>input</em>, as it gets appended to both lists (which are actually the same list, just shifted by one):</p> <pre><code>0 1 1 + + 1 1 = = 1 2 </code></pre></li> <li><p>and so forth:</p> <pre><code>0 1 1 2 + + + 1 1 2 = = = 1 2 3 0 1 1 2 3 ^ + + + + | 1 1 2 3 ^ | = = = = | | 1 2 3 5---+---+ </code></pre></li> </ul> <p>Or if you draw it a little bit differently and merge the result list and the second input list (which really are the same, anyway) into one:</p> <pre><code>0 1 1 2 3 ^ + + + + + | 1 = 1 = 2 = 3 = 5---+ </code></pre> <p>That's how <em>I</em> visualize it, anyway.</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