Skip to content

Instantly share code, notes, and snippets.

@sjsyrek
Last active December 4, 2016 13:37
Show Gist options
  • Save sjsyrek/3fb2fa03797ae0e89426b484ca8a6dcf to your computer and use it in GitHub Desktop.
Save sjsyrek/3fb2fa03797ae0e89426b484ca8a6dcf to your computer and use it in GitHub Desktop.
How I Implemented Lazy Infinite Lists in JavaScript with Proxy
// How I Used Proxy to Implement Lazy Infinite Lists in JavaScript
// Published on medium.com December 4, 2016 (http://bit.ly/2gVb1k5)
// Example code
// proxy example
class Secret {
constructor(msg) { this.info = msg }
}
let handler = {
get: (target, prop) => prop === "info" ? "Too many secrets" : target[prop]
}
let makeSecret = msg => new Proxy(new Secret(msg), handler)
let s1 = new Secret("Confidential information")
let s2 = makeSecret("More confidential information")
// linked list
class List {
constructor(x, xs) {
this.head = () => x
this.tail = () => xs
}
[Symbol.iterator]() {
const listIterator = function* (xs) {
do {
yield head(xs)
xs = tail(xs)
} while (xs !== emptyList)
}
const gen = listIterator(this)
return {
next() { return gen.next() }
}
}
valueOf() {
let value = xs => isEmpty(xs) ? `[]` : `${head(xs)}:${value(tail(xs))}`
return isEmpty(this) ? `[]` : `[${value(this)}]`
}
}
// basic list interface
const emptyList = new List()
const isEmpty = xs => xs === emptyList
const cons = (x, xs) => new List(x, xs)
const list = (...as) => as.length === 0 ? emptyList : new List(as.shift(), list(...as))
const head = xs => {
if (isEmpty(xs)) { throw Error('EmptyListError') }
return xs.head()
}
const tail = xs => {
if (isEmpty(xs)) { throw Error('EmptyListError') }
return xs.tail()
}
// lazy list constructors
const listRange = (start, end) => {
if (start === end) { return list(start) }
if (start > end) { return listRangeBy(start, end, x => x - 1) }
return listRangeBy(start, end, x => x + 1)
}
const listRangeBy = (start, end, step) => {
if (start === end) { return list(start) }
let x = start
const xs = list(x)
const listGenerator = function*() {
x = step(x)
while (start < end ? x < end : x > end) {
yield list(x)
x = step(x)
}
}
const gen = listGenerator()
const handler = {
get: function(target, prop) {
if (prop === `tail` && isEmpty(tail(target))) {
const next = gen.next()
if (next.done === false) { target[prop] = () => new Proxy(next.value, handler) }
}
return target[prop]
}
}
const proxy = new Proxy(xs, handler)
return proxy
}
// infinite list constructors
const listInf = start => listInfBy(start, x => x + 1)
const listInfBy = (start, step) => listRangeBy(start, Infinity, step)
// basic list functions
const length = xs => {
const lenAcc = (xs, n) => isEmpty(xs) ? n : lenAcc(tail(xs), n + 1)
return lenAcc(xs, 0)
}
const index = (as, n) => {
if (n < 0 || isEmpty(as)) { throw Error('OutOfRangeError') }
const x = head(as)
const xs = tail(as)
if (n === 0) { return x }
return index(xs, n - 1)
}
const listAppend = (xs, ys) => {
if (isEmpty(xs)) { return ys }
if (isEmpty(ys)) { return xs }
return cons(head(xs), listAppend(tail(xs), ys))
}
const take = (n, as) => {
if (n <= 0) { return emptyList }
if (isEmpty(as)) { return emptyList }
const x = head(as)
const xs = tail(as)
return cons(x, take(n - 1, xs))
}
const drop = (n, as) => {
if (n <= 0) { return as }
if (isEmpty(as)) { return emptyList }
const xs = tail(as)
return drop(n - 1, xs)
}
const map = (f, as) => {
if (isEmpty(as)) { return emptyList }
const x = f(head(as))
const xs = tail(as)
return cons(x, map(f, xs))
}
// functions on infinite lists
const iterate = (f, x) => listInfBy(x, x => f(x))
const repeat = a => cons(a, listInfBy(a, a => a))
const replicate = (n, x) => take(n, repeat(x))
const cycle = as => {
if (isEmpty(as)) { throw Error('EmptyListError') }
let x = head(as)
let xs = tail(as)
const c = list(x)
const listGenerator = function* () {
do {
x = isEmpty(xs) ? head(as) : head(xs)
xs = isEmpty(xs) ? tail(as) : tail(xs)
yield list(x)
} while (true)
}
const gen = listGenerator()
const handler = {
get: function (target, prop) {
if (prop === `tail` && isEmpty(tail(target))) {
const next = gen.next()
target[prop] = () => new Proxy(next.value, handler)
}
return target[prop]
}
}
const proxy = new Proxy(c, handler)
return proxy
}
// examples
const fib = n => n < 2 ? n : fib(n - 1) + fib(n - 2)
const fibs = n => map(fib, take(n, listInf(1)))
const fact = n => n === 1 ? n : fact(n - 1) * n
const facts = n => map(fact, take(n, listInf(1)))
const sqrt = (a0, eps, n) => {
const within = (eps, rest) => {
let a = index(rest, 0)
let b = index(rest, 1)
return Math.abs(a - b) <= eps ? b : within(eps, drop(1, rest))
}
const next = (n, x) => (x + n / x) / 2
return within(eps, iterate(next.bind(null, n), a0))
}
const booleans = cycle(list(false, true))
// binary tree
class Tree {
constructor(left, label, right) {
this.left = () => left
this.label = () => label
this.right = () => right
}
}
const leaf = new Tree()
const node = (left, label, right) => new Tree(left, label, right)
const insert = (x, t) => {
if (t === leaf) { return node(leaf, x, leaf) }
if (x === t.label()) { return t }
if (x < t.label()) { return node(insert(x, t.left()), t.label(), t.right()) }
return node(t.left(), t.label(), insert(x, t.right()))
}
const preorder = t => t === leaf ? [] : [t.label()].concat(preorder(t.left()).concat(preorder(t.right())))
const inorder = t => t === leaf ? [] : inorder(t.left()).concat([t.label()].concat(inorder(t.right())))
const postorder = t => t === leaf ? [] : postorder(t.left()).concat(postorder(t.right()).concat([t.label()]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment