Instantly share code, notes, and snippets.

# raganwald/fb.es6

Last active December 27, 2017 16:41
Star You must be signed in to star a gist
An elegant expression of the Fibonacci Sequence using generators https://en.wikipedia.org/wiki/Fibonacci_number
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 function * zipWith (zipper, ...iterables) { const iterators = iterables.map(i => i[Symbol.iterator]()); while (true) { const pairs = iterators.map(j => j.next()), dones = pairs.map(p => p.done), values = pairs.map(p => p.value); if (dones.indexOf(true) >= 0) break; yield zipper(...values); } }; function * tail (iterable) { const iterator = iterable[Symbol.iterator](); iterator.next(); yield * iterator; } const plus = (x, y) => x + y; function * fibs () { yield 0; yield 1; yield * zipWith(plus, fibs(), tail(fibs())); } fibs() //=> 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181, ... function memoize (generator) { const memos = {}, iterators = {}; return function * (...args) { const key = JSON.stringify(args); let i = 0; if (memos[key] == null) { memos[key] = []; iterators[key] = generator(...args); } while (true) { if (i < memos[key].length) { yield memos[key][i++]; } else { const { done, value } = iterators[key].next(); if (done) { return; } else { yield memos[key][i++] = value; } } } } } const mfibs = memoize(function * () { yield 0; yield 1; yield * zipWith(plus, mfibs(), tail(mfibs())); }); mfibs() //=> 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181, ...

### odf commented Mar 14, 2016

It's even more elegant if you use lazy sequences and don't have to create exponentially many generator instances. :-)

### raganwald commented Mar 14, 2016

It's even more elegant if you use lazy sequences and don't have to create exponentially many generator instances

Very true, I wanted to recreate the surface definition as directly as possible. I've added a memoized version (`mfibs`) for your entertainment.