Last active
December 27, 2017 16:41
-
-
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
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, ... |
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
It's even more elegant if you use lazy sequences and don't have to create exponentially many generator instances. :-)