Skip to content

Instantly share code, notes, and snippets.

@peter-leonov
Forked from gvergnaud/lazy-list.js
Created May 21, 2017 21:07
Show Gist options
  • Save peter-leonov/8171e7b339d55dded3002588e85c6b19 to your computer and use it in GitHub Desktop.
Save peter-leonov/8171e7b339d55dded3002588e85c6b19 to your computer and use it in GitHub Desktop.
Lazy List, implemented with es6 generators
/* ----------------------------------------- *
Lazy List Implementation
* ----------------------------------------- */
// Haskell-like infinite List, implemented with es6 generators
// Lazyness lets you do crazy stuff like
List.range(0, Infinity)
.drop(1000)
.map(n => -n)
.filter(n => n % 2 === 0)
.take(2)
.reduce((r, n) => r * n, 1)
// => 1002000
List.fibonacci
.take(10)
.toArray()
// => [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ]
List.integers
.zipWith(List.fibonacci, (x, y) => x * y)
.map(x => `The result is ${x}!!`)
.take(5)
.toArray()
// => [ 'The result is 0!!', 'The result is 1!!', 'The result is 2!!',
// 'The result is 6!!', 'The result is 12!!' ]
// since nothing is executed until .toArray or .reduce is called, we can chain any
// number of operators in any order without any performance impact.
class List {
constructor(generator, length = Infinity) {
this[Symbol.iterator] = generator
this.length = length
}
static get integers () {
return this.range(0, Infinity)
}
static get fibonacci () {
return new List(function* () {
let x = 1
let y = 1
yield* [ 0, x, y ]
while (true) {
let next = x + y
yield next
x = y
y = next
}
}, Infinity)
}
static of (...args) {
return new List(function* () {
yield* args
}, args.length)
}
static from (iterable) {
return new List(function* () {
yield* iterable
}, iterable.length)
}
static range (start, end, step = 1) {
return new List(function* () {
let i = start
while (i <= end) {
yield i
i += step
}
}, Math.floor((end - start + 1) / step))
}
static empty () {
return new List(function* () {}, 0)
}
concat (iterable) {
const generator = this[Symbol.iterator]
return new List(function* () {
yield* generator()
yield* iterable
}, this.length + iterable.length)
}
map (mapper) {
const generator = this[Symbol.iterator]
return new List(function* () {
for (const value of generator()) {
yield mapper(value)
}
}, this.length)
}
filter (predicate) {
const generator = this[Symbol.iterator]
return new List(function* () {
for (const value of generator()) {
if (predicate(value)) yield value
}
}, this.length)
}
scan (scanner, seed) {
const generator = this[Symbol.iterator]
return new List(function* () {
let acc = seed
for (const value of generator()) {
yield acc = scanner(acc, value)
}
}, this.length)
}
reduce (reducer, seed) {
return this.toArray().reduce(reducer, seed)
}
ap (list) {
const generator = this[Symbol.iterator]
return new List(function* () {
for (const f of generator()) {
yield* list.map(f)
}
}, this.length)
}
take (x) {
const generator = this[Symbol.iterator]
return new List(function* () {
const iterator = generator()
let next = iterator.next()
let n = 0
while (!next.done && x > n) {
yield next.value
n++
next = iterator.next()
}
}, this.length > x ? x : this.length)
}
drop (x) {
const generator = this[Symbol.iterator]
return new List(function* () {
const iterator = generator()
let next = iterator.next()
let n = 1
while (!next.done) {
if (n > x) yield next.value
n++
next = iterator.next()
}
}, this.length - x)
}
zipWith (lazyList, zipper) {
const generator1 = this[Symbol.iterator]
const generator2 = lazyList[Symbol.iterator]
return new List(function* () {
const iterator1 = generator1()
const iterator2 = generator2()
let next1 = iterator1.next()
let next2 = iterator2.next()
let i = 0
while (!next1.done && !next2.done) {
yield zipper(next1.value, next2.value)
next1 = iterator1.next()
next2 = iterator2.next()
}
}, this.length < lazyList.length ? this.length : lazyList.length)
}
head () {
return this[Symbol.iterator]().next().value
}
tail () {
return this.drop(1)
}
toArray () {
return [ ...this ]
}
toString () {
const displayedCount = 100
return `List [ ${
this.take(displayedCount).toArray().join(', ')
}${
this.length > displayedCount ? ' ...' : ''
} ]`
}
inspect () {
return this.toString()
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment