Skip to content

Instantly share code, notes, and snippets.

@raganwald
Last active December 27, 2017 16:41
Show Gist options
  • Save raganwald/9714874740ec0048e3bc to your computer and use it in GitHub Desktop.
Save raganwald/9714874740ec0048e3bc to your computer and use it in GitHub Desktop.
An elegant expression of the Fibonacci Sequence using generators https://en.wikipedia.org/wiki/Fibonacci_number
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
Copy link

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
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment