Last active
July 18, 2022 03:00
-
-
Save erwinv/521af9e455bf6f1399244cc7fa88ffa0 to your computer and use it in GitHub Desktop.
Infinite Data Structures: https://www.youtube.com/watch?v=bnRNiE_OVWA
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
twinPrimes = filter twin (zip primes (tail primes)) | |
twin (x,y) = y == x+2 | |
primes = sieve [2..] | |
sieve (p:ps) = p : sieve [x | x <- ps, mod x p /= 0] |
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* naturalNumbers(from = 1) { | |
let n = from; | |
while (true) { | |
yield n++; | |
} | |
} | |
function* primes() { | |
// yield* sieveRecursive(naturalNumbers(2)); // call stack overflows | |
yield* sieveIterative(); // no stack overflow, even better performance | |
} | |
function* sieveRecursive(xs) { | |
const nextPrime = xs.next().value; | |
yield nextPrime; | |
// stack overflows because of the recursive filters | |
// (1 filter added to the stack for every new prime number) | |
yield* sieveRecursive(filter(x => x % nextPrime !== 0, xs)); | |
} | |
function* sieveIterative() { | |
const primes = []; | |
for (const x of naturalNumbers(2)) { | |
if (every( | |
p => x % p !== 0, | |
takeWhile(p => p <= Math.floor(Math.sqrt(x)), primes) | |
)) | |
{ | |
primes.push(x); | |
yield x; | |
} | |
} | |
} | |
function every(predicate, xs) { | |
for (const x of xs) { | |
if (!predicate(x)) return false; | |
} | |
return true; | |
} | |
function* filter(predicate, xs) { | |
for (const x of xs) { | |
if (predicate(x)) { | |
yield x; | |
} | |
} | |
} | |
function* twinPrimes() { | |
const areTwins = ([x, y]) => y === x + 2 | |
yield* filter(areTwins, zip(primes(), tail(primes()))) | |
} | |
function* tail(xs) { | |
xs.next(); | |
yield* xs; | |
} | |
function* zip(xs, ys) { | |
for (const x of xs) { | |
const {done, value: y} = ys.next(); | |
if (done) return; | |
yield [x, y]; | |
} | |
} | |
function* take(n, xs) { | |
if (n <= 0) return; | |
let i = 0; | |
for (const x of xs) { | |
yield x; | |
if (++i >= n) return; | |
} | |
} | |
function* takeWhile(predicate, xs) { | |
for (const x of xs) { | |
if (!predicate(x)) return; | |
yield x; | |
} | |
} | |
function main() { | |
// for (const n of primes()) { | |
// console.log(n); | |
// } | |
for (const twins of twinPrimes()) { | |
console.log(twins); | |
} | |
} | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment