Last active
November 23, 2020 07:22
-
-
Save nodename/22acb6bbf05c5c38cc2fffdefd99c931 to your computer and use it in GitHub Desktop.
Functional programming with lazy sequences in JavaScript
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
// A lazy sequence is an object that has several methods: an API. | |
// A star function RETURNS a lazy sequence: | |
const naturals = function* () { | |
let i = 1; | |
while (true) { // infinite loop generates an infinite sequence! | |
yield i++; | |
} | |
}; | |
// this will not terminate until the heap runs out of memory: | |
/* | |
for (const num of createNat()) { | |
console.log(num); | |
} */ | |
// The for...of syntax is part of the lazy sequence's API; another is the next() method | |
// And so is the spread operator (...), and | |
// you can call Array.from() on them, | |
// because generator objects implement the Iterable interface | |
const take = function* (n, it) { | |
if (n < 0) { | |
n = 0; | |
} | |
let i = 0; | |
for (const x of it) { | |
if (i++ < n) { | |
yield x; | |
} else { | |
break; | |
} | |
} | |
}; | |
for (const x of take(5, naturals())) { | |
console.log(x); | |
} | |
// You can use take on an array because it has an iterator and will invoke it for you: | |
for (const x of take(5, [2, 4, 6, 8, 10, 12, 14])) { | |
console.log(x); | |
} | |
let xs = [...take(5, [2, 4, 6, 8, 10, 12, 14])]; | |
console.log(xs); | |
const drop = function* (n, it) { | |
let i = 0; | |
for (const x of it) { | |
if (i++ >= n) { | |
yield x; | |
} | |
} | |
}; | |
/* | |
for (const x of drop(5, createNat())) { | |
console.log(x); | |
} | |
*/ | |
for (const x of drop(5, take(10, naturals()))) { | |
console.log(x); | |
} | |
/* | |
for (const x of take(3, drop(5, range(1, 11)))) { | |
console.log(x); | |
} | |
*/ | |
const inc = x => x + 1; | |
// yield* is recursion | |
/* recursive: bad | |
function* iterate(f, val) { | |
yield val; | |
yield* iterate(f, f(val)); // This will blow the stack if allowed to recurse too deep | |
} | |
*/ | |
const iterate = function* (f, val) { | |
while (true) { | |
yield (val); | |
val = f(val); | |
} | |
}; | |
const createNat_v2 = () => iterate(inc, 1); | |
for (const x of take(20, createNat_v2())) { | |
console.log(x); | |
} | |
const times2 = x => 2 * x; | |
const powersOfTwo = iterate(times2, 1); | |
for (const x of take(10, powersOfTwo)) { | |
console.log(x); | |
} | |
// const lazyMap = function* lazyMap(mapFunc, iterator) { | |
// while (true) { | |
// const result = iterator.next(); | |
// if (result.done) { | |
// break; | |
// } | |
// yield mapFunc(result.value); | |
// } | |
// } | |
const lazyMap = function* (f, it) { | |
for (const x of it) { | |
yield f(x); | |
} | |
}; | |
const square = x => x * x; | |
const createSquares = () => lazyMap(square, naturals()); | |
for (const x of take(10, createSquares())) { | |
console.log(x); | |
} | |
const first = (it) => { // Note: not a generator function! | |
for (const x of it) { | |
return x; | |
} | |
}; | |
let oneTwoThree = [1, 2, 3]; | |
console.log(first(oneTwoThree)); | |
const rest = function* (it) { | |
yield* drop(1, it); | |
}; | |
// can't just log rest([1, 2, 3]); it's an iterator | |
for (const x of rest(oneTwoThree)) { | |
console.log(x); | |
} | |
console.log([...rest(oneTwoThree)]); | |
function* createFib() { | |
yield* lazyMap(first, iterate(([a, b]) => [b, a + b], [0, 1])); | |
} | |
for (const x of take(10, createFib())) { | |
console.log(x); | |
} | |
const concat = function* (as, bs) { | |
/* | |
for (const a of as) { | |
yield (a); | |
} | |
for (const b of bs) { | |
yield (b); | |
} | |
*/ | |
yield* as; | |
yield* bs; | |
}; | |
// const lazyFilter = function* lazyFilter(filterFunc, iterator) { | |
// while (true) { | |
// const result = iterator.next(); | |
// if (result.done) { | |
// break; | |
// } | |
// if (filterFunc(result.value)) { | |
// yield result.value; | |
// } | |
// } | |
// } | |
const lazyFilter = function* (predicate, it) { | |
for (const x of it) { | |
if (predicate(x)) { | |
yield x; | |
} | |
} | |
}; | |
const isEven = x => x % 2 === 0; | |
const evens = lazyFilter(isEven, naturals()); | |
// start (inclusive), end (exclusive) | |
/* | |
const range = function* (start, end) { | |
while (start < end) { | |
yield start++; | |
} | |
}; */ | |
// generalizing createNat: | |
// let's generalize range a bit: (to be just like Clojure) | |
// last element will be end - step | |
const range = function* (start = 0, end = Infinity, step = 1) { | |
if (arguments.length === 1) { // a single arg should be taken as end, not start | |
end = start; | |
start = 0; | |
} | |
let value = start; | |
while (value < end) { | |
yield value; | |
value += step; | |
} | |
}; | |
console.log(first(range())); | |
/* | |
for (const x of rest(range())) { | |
console.log(x); // 1, 2, 3, ... | |
} | |
*/ | |
let x = first(rest(range())); | |
console.log(x); | |
for (const x of range(10)) { | |
console.log(x); // should be [0...9] | |
} | |
for (const x of range(0, 10)) { | |
console.log(x); // should be [0...9] | |
} | |
for (const x of range(0, 10, 2)) { | |
console.log(x); // should be [0, 2, 4, 6, 8] | |
} | |
for (const x of take(10, range())) { | |
console.log(x); | |
} | |
const createNat_v3 = () => (drop(1, range())); | |
for (const x of (take(10, createNat_v3()))) { | |
console.log(x); | |
} | |
let persons = ["James", "Arlene", "Melquiades", "Samson", "Carlotta"]; | |
const show = ([person, index]) => console.log(index + ": " + person); | |
const forEach = (f, it) => { | |
for (const x of it) { | |
f(x); | |
} | |
}; | |
// as and bs are lazy sequences, i.e. iterators | |
// return a lazy sequence of pairs | |
/* recursive version; not good for infinite lists | |
const zip = function* (as, bs) { | |
const firstA = as.next(); | |
const firstB = bs.next(); | |
if (!(firstA.done || firstB.done)) { | |
yield([firstA.value, firstB.value]); | |
yield* zip(as, bs); | |
} | |
}; | |
*/ | |
/* | |
const zip = function* (as, bs) { | |
if (as instanceof Array) { // you can use for...of on an Array but it doesn't recognize next() | |
as = as[Symbol.iterator](); | |
} | |
if (bs instanceof Array) { | |
bs = bs[Symbol.iterator](); | |
} | |
// There's no syntax for parallel for...next, so we do it "manually": | |
let firstA = as.next(); | |
let firstB = bs.next(); | |
while (!(firstA.done || firstB.done)) { | |
yield ([firstA.value, firstB.value]); | |
firstA = as.next(); | |
firstB = bs.next(); | |
} | |
}; | |
*/ | |
const zip = function* (...iterables) { | |
let iterators = iterables.map(i => i[Symbol.iterator]()); | |
while (true) { | |
let results = iterators.map(iter => iter.next()); | |
if (results.some(result => result.done)) { | |
return; | |
} else { | |
yield results.map(result => result.value); | |
} | |
} | |
}; | |
const as = ["a", "b", "c"]; | |
const bs = [1, 2, 3, 4]; | |
const cs = ["X", "Y", "Z"]; | |
for (const element of zip(as, bs, cs)) { | |
console.log(element); | |
} | |
for (const pair of zip(persons, range())) { | |
console.log(pair); | |
} | |
let zArray = [...zip(as, bs, cs)]; | |
console.log(zArray); | |
forEach(show, zip(persons, range())); | |
// zipWith goes here | |
const flatten = function* (it) { | |
for (const x of it) { | |
if (typeof (x[Symbol.iterator]) == "function") { | |
yield* flatten(x); | |
} else { | |
yield x; | |
} | |
} | |
}; | |
let it = flatten([1, [2, 3], [[4], [5]]]); | |
for (const num of it) { | |
console.log(num); | |
} | |
const flatMap = function(f, it) { | |
return flatten(lazyMap(f, it)); | |
} | |
it = flatMap(x => [x - 1, x], evens); | |
for (const x of take(10, it)) { | |
console.log(x); | |
} | |
// Here's reduce: | |
const reduce = (f, initial, it) => { | |
let result = initial; | |
for (const x of it) { | |
result = f(result, x); | |
} | |
return result; | |
}; | |
// Note that reduce has to realize the entire sequence, | |
// so you lose laziness. | |
// And of course it will blow the stack if the sequence is loo long (or infinite). | |
const add = (x, y) => x + y; | |
let s = range(0, 10); | |
reduce(add, 0, lazyMap(inc, lazyFilter(isEven, s))) | |
// There's no concern about creating intermediate sequences here, | |
// because the lazy filter and map functions do not materialize | |
// more than they need for any given step. | |
// It's only when we reach reduce, an eager function, | |
// that we need to have the whole sequence realized. | |
// A lazy sequence is just an iterator that offers an api to materialize the next item. | |
// TODO FizzBuzz! | |
// List Comprehensions | |
// I. | |
const digits = [1, 2, 3]; | |
const products = function* () { | |
for (const x1 of digits) { | |
for (const x2 of digits) { | |
yield x1 * x2; // or yield [x1, x2]; or whatever | |
} | |
} | |
}; | |
console.log([...products()]); | |
// II. produce a sequence of the first three powers for a range of integers | |
const threePowers = function* () { | |
for (const x of range(1, 6)) { | |
const y = x * x; | |
const z = x * x * x; | |
yield [x, y, z]; | |
} | |
}; | |
console.log([...threePowers()]); | |
//III. | |
// Python: x = [i for i in range(10)] // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] | |
const xlist = [...range(10)]; | |
console.log(xlist); | |
// Python: squares = [x**2 for x in range(10)] // [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] | |
const squares = [...(function* () { for (const x of range(10)) yield x * x; })()]; | |
console.log(squares); | |
// Python: list1 = [3,4,5] | |
// Python: multiplied = [item*3 for item in list1] // [9,12,15] | |
const list1 = [3, 4, 5]; | |
const multiplied = [...(function* () { for (const item of list1) yield item * 3; })()]; | |
console.log(multiplied); | |
// Python: listOfWords = ["this","is","a","list","of","words"] | |
// Python: firstLetters = [ word[0] for word in listOfWords ] | |
// [‘t’, ‘i’, ‘a’, ‘l’, ‘o’, ‘w’] | |
const listOfWords = ["this", "is", "a", "list", "of", "words"]; | |
const firstLetters = [...(function* () { for (const word of listOfWords) yield word[0]; })()]; | |
console.log(firstLetters); | |
// Can we write a little dsl for this? | |
const pyComprehension = (f, it, cond = () => true) => { | |
const fun = function* () { | |
for (const x of it) { | |
if (cond(x)) { | |
yield f(x); | |
} | |
} | |
} | |
return [...fun()]; | |
}; | |
const firstLetters1 = pyComprehension(word => word[0], listOfWords); | |
console.log(firstLetters1); | |
// Python: [ [ 1 if item_idx == row_idx else 0 for item_idx in range(0, 3) ] for row_idx in range(0, 3) ] | |
// [ [1, 0, 0], | |
// [0, 1, 0], | |
// [0, 0, 1] ] | |
//const diagonal = pyComprehension() | |
//const diagonalMatrix = pyComprehension(f, range(0, 3)) | |
const diagonalMatrixGen = function () { | |
const fun = function* () { | |
for (const row_idx of range(0, 3)) { | |
const innerFunction = function* () { | |
for (const item_idx of range(0, 3)) { | |
if (item_idx === row_idx) yield 1; else yield 0; | |
} | |
}; | |
yield [...innerFunction()]; | |
} | |
}; | |
return [...fun()]; | |
}; | |
const diagonalMatrixGen2 = function () { | |
const fun = function* () { | |
for (const row_idx of range(0, 3)) { | |
yield pyComprehension( | |
item_idx => { if (item_idx === row_idx) return 1; else return 0; }, | |
range(0, 3)); | |
} | |
}; | |
return [...fun()]; | |
}; | |
const diagonalMatrix = pyComprehension( | |
row_idx => pyComprehension( | |
item_idx => { if (item_idx === row_idx) return 1; else return 0; }, | |
range(0, 3)), | |
range(0, 3) | |
); | |
console.log(diagonalMatrix); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment