Functional programming with lazy sequences in JavaScript

lazy-seqs.js

// 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);