Create a gist now

Instantly share code, notes, and snippets.

@raganwald /fb.es6
Last active Dec 27, 2017

Embed
What would you like to do?
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, ...
@raganwald

This comment has been minimized.

Show comment
Hide comment
@odf

This comment has been minimized.

Show comment
Hide comment
@odf

odf Mar 14, 2016

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

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

This comment has been minimized.

Show comment
Hide comment
@raganwald

raganwald 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.

Owner

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.

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