Created
March 9, 2018 03:26
-
-
Save lqt0223/ee95d0695958eb473042e00c3b1787a4 to your computer and use it in GitHub Desktop.
27 Reading SICP - the stream (implemented as delayed list) and its applications
This file contains hidden or 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
// constructors | |
function isNull(stream) { | |
return Array.isArray(stream) && stream.length == 0 | |
} | |
function isAllNull(streams) { | |
return streams.every((stream) => isNull(stream)) | |
} | |
function isSomeNull(streams) { | |
return streams.some((stream) => isNull(stream)) | |
} | |
function emptyStream() { | |
return [] | |
} | |
function cons(a, b) { | |
return [a, b] | |
} | |
function car(stream) { | |
return stream[0] | |
} | |
function cdr(stream) { | |
return stream[1]() | |
} | |
function streamify(list) { | |
if (isNull(list)) { | |
return emptyStream() | |
} else { | |
var head = list.shift() | |
return cons(head, () => streamify(list)) | |
} | |
} | |
// transformers and information trackers | |
function dump(stream) { | |
if (!isNull(stream)) { | |
console.log(car(stream)) | |
dump(cdr(stream)) | |
} | |
} | |
function ref(stream, n) { | |
if (n == 0) { | |
return car(stream) | |
} else { | |
return ref(cdr(stream), n - 1) | |
} | |
} | |
function map(proc, ...streams) { | |
if (isAllNull(streams)) { | |
return emptyStream() | |
} else if (isSomeNull(streams)) { | |
throw 'Argument streams are not of equal size' | |
} else { | |
var heads = streams.map((stream) => car(stream)) | |
var head = proc.apply(null, heads) | |
var tails = streams.map((stream) => cdr(stream)) | |
var args = ([proc]).concat(tails) | |
return cons(head, () => map.apply(null, args)) | |
} | |
} | |
function filter(pred, stream) { | |
if (isNull(stream)) { | |
return emptyStream() | |
} else if (pred(car(stream))) { | |
return cons(car(stream), () => filter(pred, cdr(stream))) | |
} else { | |
return filter(pred, cdr(stream)) | |
} | |
} | |
function each(proc, stream) { | |
if (!isNull(stream)) { | |
proc(car(stream)) | |
each(proc, cdr(stream)) | |
} | |
} | |
// applications | |
function enumerateLiteral(low, high) { | |
if (low > high) { | |
return emptyStream() | |
} else { | |
return cons(low, () => enumerateLiteral(low + 1, high)) | |
} | |
} | |
function add(s1, s2) { | |
return map((x, y) => x + y, s1, s2) | |
} | |
function scale(s, factor) { | |
return map((x) => x * factor, s) | |
} | |
// fibonacci sequence | |
function fibgen(a, b) { | |
return cons(a, () => fibgen(b, a + b)) | |
} | |
var fibs = fibgen(0, 1) | |
// prime number sequence | |
function integersFrom(n) { | |
return cons(n, () => integersFrom(n + 1)) | |
} | |
function divisible(x, y) { | |
return x % y == 0 | |
} | |
function sieve(s) { | |
return cons(car(s), () => sieve(filter((x) => !divisible(x, car(s)), cdr(s)))) | |
} | |
var primes = sieve(integersFrom(2)) | |
// estimating pi by partial sum | |
function partialSum(s) { | |
function ps(s, sum) { | |
if (isNull(s)) { | |
return emptyStream() | |
} else { | |
sum += car(s) | |
return cons(sum, () => ps(cdr(s), sum)) | |
} | |
} | |
return ps(s, 0) | |
} | |
function piSummands(n, minus) { | |
return cons((1 / n) * minus, () => piSummands(n + 2, minus * -1)) | |
} | |
var pi = scale(partialSum(piSummands(1, 1)), 4) | |
// euler acceleration | |
function eulerTrans(s) { | |
var s0 = ref(s, 0) | |
var s1 = ref(s, 1) | |
var s2 = ref(s, 2) | |
var trans = s2 - Math.pow((s2 - s1), 2) / (s0 - 2 * s1 + s2) | |
return cons(trans, () => eulerTrans(cdr(s))) | |
} | |
var e = eulerTrans | |
var accPi = e(e(pi)) | |
// the stream of pairs | |
function interleave(s1, s2) { | |
if (isNull(s1)) { | |
return s2 | |
} else { | |
return cons(car(s1), () => interleave(s2, cdr(s1))) | |
} | |
} | |
function pairs(s, t) { | |
return cons(cons(car(s), car(t)), () => interleave(map((x) => cons(car(s), x), cdr(t)), pairs(cdr(s), cdr(t)))) | |
} | |
var s1 = integersFrom(1) | |
var s2 = integersFrom(1) | |
var s3 = pairs(s1, s2) | |
// estimating pi by cesaro's method | |
function gcd(x, y) { | |
if (x == y) { | |
return x | |
} else if (x > y) { | |
return gcd(x - y, y) | |
} else { | |
return gcd(x, y - x) | |
} | |
} | |
function rand() { | |
return cons(Math.floor(Math.random() * 100), () => rand()) | |
} | |
var rand1 = rand() | |
var rand2 = rand() | |
var cesaro = map((x, y) => gcd(x, y) == 1, rand1, rand2) | |
function monteCarlo(exprStream) { | |
function mc(stream, trials, passed) { | |
trials++ | |
if (car(stream)) { | |
passed++ | |
} | |
return cons(passed / trials, () => mc(cdr(stream), trials, passed)) | |
} | |
return mc(exprStream, 0, 0) | |
} | |
var t1 = monteCarlo(cesaro) | |
var t2 = map((x) => Math.sqrt(6 / x), t1) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment