Skip to content

Instantly share code, notes, and snippets.

@lqt0223
Created March 9, 2018 03:26
Show Gist options
  • Save lqt0223/ee95d0695958eb473042e00c3b1787a4 to your computer and use it in GitHub Desktop.
Save lqt0223/ee95d0695958eb473042e00c3b1787a4 to your computer and use it in GitHub Desktop.
27 Reading SICP - the stream (implemented as delayed list) and its applications
// 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