michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
michael@0:  */
michael@0: "use strict";
michael@0: 
michael@0: module.metadata = {
michael@0:   "stability": "experimental"
michael@0: };
michael@0: 
michael@0: // Disclamer:
michael@0: // In this module we'll have some common argument / variable names
michael@0: // to hint their type or behavior.
michael@0: //
michael@0: // - `f` stands for "function" that is intended to be side effect
michael@0: //   free.
michael@0: // - `p` stands for "predicate" that is function which returns logical
michael@0: //   true or false and is intended to be side effect free.
michael@0: // - `x` / `y` single item of the sequence.
michael@0: // - `xs` / `ys` sequence of `x` / `y` items where `x` / `y` signifies
michael@0: //    type of the items in sequence, so sequence is not of the same item.
michael@0: // - `_` used for argument(s) or variable(s) who's values are ignored.
michael@0: 
michael@0: const { complement, flip, identity } = require("../lang/functional");
michael@0: const { iteratorSymbol } = require("../util/iteration");
michael@0: const { isArray, isArguments, isMap, isSet,
michael@0:         isString, isBoolean, isNumber } = require("../lang/type");
michael@0: 
michael@0: const Sequence = function Sequence(iterator) {
michael@0:   if (iterator.isGenerator && iterator.isGenerator())
michael@0:     this[iteratorSymbol] = iterator;
michael@0:   else
michael@0:     throw TypeError("Expected generator argument");
michael@0: };
michael@0: exports.Sequence = Sequence;
michael@0: 
michael@0: const polymorphic = dispatch => x =>
michael@0:   x === null ? dispatch.null(null) :
michael@0:   x === void(0) ? dispatch.void(void(0)) :
michael@0:   isArray(x) ? (dispatch.array || dispatch.indexed)(x) :
michael@0:   isString(x) ? (dispatch.string || dispatch.indexed)(x) :
michael@0:   isArguments(x) ? (dispatch.arguments || dispatch.indexed)(x) :
michael@0:   isMap(x) ? dispatch.map(x) :
michael@0:   isSet(x) ? dispatch.set(x) :
michael@0:   isNumber(x) ? dispatch.number(x) :
michael@0:   isBoolean(x) ? dispatch.boolean(x) :
michael@0:   dispatch.default(x);
michael@0: 
michael@0: const nogen = function*() {};
michael@0: const empty = () => new Sequence(nogen);
michael@0: exports.empty = empty;
michael@0: 
michael@0: const seq = polymorphic({
michael@0:   null: empty,
michael@0:   void: empty,
michael@0:   array: identity,
michael@0:   string: identity,
michael@0:   arguments: identity,
michael@0:   map: identity,
michael@0:   set: identity,
michael@0:   default: x => x instanceof Sequence ? x : new Sequence(x)
michael@0: });
michael@0: exports.seq = seq;
michael@0: 
michael@0: 
michael@0: 
michael@0: 
michael@0: // Function to cast seq to string.
michael@0: const string = (...etc) => "".concat(...etc);
michael@0: exports.string = string;
michael@0: 
michael@0: // Function for casting seq to plain object.
michael@0: const object = (...pairs) => {
michael@0:   let result = {};
michael@0:   for (let [key, value] of pairs)
michael@0:     result[key] = value;
michael@0: 
michael@0:   return result;
michael@0: };
michael@0: exports.object = object;
michael@0: 
michael@0: // Takes `getEnumerator` function that returns `nsISimpleEnumerator`
michael@0: // and creates lazy sequence of it's items. Note that function does
michael@0: // not take `nsISimpleEnumerator` itslef because that would allow
michael@0: // single iteration, which would not be consistent with rest of the
michael@0: // lazy sequences.
michael@0: const fromEnumerator = getEnumerator => seq(function* () {
michael@0:   const enumerator = getEnumerator();
michael@0:   while (enumerator.hasMoreElements())
michael@0:    yield enumerator.getNext();
michael@0: });
michael@0: exports.fromEnumerator = fromEnumerator;
michael@0: 
michael@0: // Takes `object` and returns lazy sequence of own `[key, value]`
michael@0: // pairs (does not include inherited and non enumerable keys).
michael@0: const pairs = polymorphic({
michael@0:   null: empty,
michael@0:   void: empty,
michael@0:   map: identity,
michael@0:   indexed: indexed => seq(function* () {
michael@0:     const count = indexed.length;
michael@0:     let index = 0;
michael@0:     while (index < count) {
michael@0:       yield [index, indexed[index]];
michael@0:       index = index + 1;
michael@0:     }
michael@0:   }),
michael@0:   default: object => seq(function* () {
michael@0:     for (let key of Object.keys(object))
michael@0:       yield [key, object[key]];
michael@0:   })
michael@0: });
michael@0: exports.pairs = pairs;
michael@0: 
michael@0: 
michael@0: const keys = polymorphic({
michael@0:   null: empty,
michael@0:   void: empty,
michael@0:   indexed: indexed => seq(function* () {
michael@0:     const count = indexed.length;
michael@0:     let index = 0;
michael@0:     while (index < count) {
michael@0:       yield index;
michael@0:       index = index + 1;
michael@0:     }
michael@0:   }),
michael@0:   map: map => seq(function* () {
michael@0:     for (let [key, _] of map)
michael@0:       yield key;
michael@0:   }),
michael@0:   default: object => seq(function* () {
michael@0:     for (let key of Object.keys(object))
michael@0:       yield key;
michael@0:   })
michael@0: });
michael@0: exports.keys = keys;
michael@0: 
michael@0: 
michael@0: const values = polymorphic({
michael@0:   null: empty,
michael@0:   void: empty,
michael@0:   set: identity,
michael@0:   indexed: indexed => seq(function* () {
michael@0:     const count = indexed.length;
michael@0:     let index = 0;
michael@0:     while (index < count) {
michael@0:       yield indexed[index];
michael@0:       index = index + 1;
michael@0:     }
michael@0:   }),
michael@0:   map: map => seq(function* () {
michael@0:     for (let [_, value] of map) yield value;
michael@0:   }),
michael@0:   default: object => seq(function* () {
michael@0:     for (let key of Object.keys(object)) yield object[key];
michael@0:   })
michael@0: });
michael@0: exports.values = values;
michael@0: 
michael@0: 
michael@0: 
michael@0: // Returns a lazy sequence of `x`, `f(x)`, `f(f(x))` etc.
michael@0: // `f` must be free of side-effects. Note that returned
michael@0: // sequence is infinite so it must be consumed partially.
michael@0: //
michael@0: // Implements clojure iterate:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/iterate
michael@0: const iterate = (f, x) => seq(function* () {
michael@0:   let state = x;
michael@0:   while (true) {
michael@0:     yield state;
michael@0:     state = f(state);
michael@0:   }
michael@0: });
michael@0: exports.iterate = iterate;
michael@0: 
michael@0: // Returns a lazy sequence of the items in sequence for which `p(item)`
michael@0: // returns `true`. `p` must be free of side-effects.
michael@0: //
michael@0: // Implements clojure filter:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/filter
michael@0: const filter = (p, sequence) => seq(function* () {
michael@0:   if (sequence !== null && sequence !== void(0)) {
michael@0:     for (let item of sequence) {
michael@0:       if (p(item))
michael@0:         yield item;
michael@0:     }
michael@0:   }
michael@0: });
michael@0: exports.filter = filter;
michael@0: 
michael@0: // Returns a lazy sequence consisting of the result of applying `f` to the
michael@0: // set of first items of each sequence, followed by applying f to the set
michael@0: // of second items in each sequence, until any one of the sequences is
michael@0: // exhausted. Any remaining items in other sequences are ignored. Function
michael@0: // `f` should accept number-of-sequences arguments.
michael@0: //
michael@0: // Implements clojure map:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/map
michael@0: const map = (f, ...sequences) => seq(function* () {
michael@0:   const count = sequences.length;
michael@0:   // Optimize a single sequence case
michael@0:   if (count === 1) {
michael@0:     let [sequence] = sequences;
michael@0:     if (sequence !== null && sequence !== void(0)) {
michael@0:       for (let item of sequence)
michael@0:         yield f(item);
michael@0:     }
michael@0:   }
michael@0:   else {
michael@0:     // define args array that will be recycled on each
michael@0:     // step to aggregate arguments to be passed to `f`.
michael@0:     let args = [];
michael@0:     // define inputs to contain started generators.
michael@0:     let inputs = [];
michael@0: 
michael@0:     let index = 0;
michael@0:     while (index < count) {
michael@0:       inputs[index] = sequences[index][iteratorSymbol]();
michael@0:       index = index + 1;
michael@0:     }
michael@0: 
michael@0:     // Run loop yielding of applying `f` to the set of
michael@0:     // items at each step until one of the `inputs` is
michael@0:     // exhausted.
michael@0:     let done = false;
michael@0:     while (!done) {
michael@0:       let index = 0;
michael@0:       let value = void(0);
michael@0:       while (index < count && !done) {
michael@0:         ({ done, value }) = inputs[index].next();
michael@0: 
michael@0:         // If input is not exhausted yet store value in args.
michael@0:         if (!done) {
michael@0:           args[index] = value;
michael@0:           index = index + 1;
michael@0:         }
michael@0:       }
michael@0: 
michael@0:       // If none of the inputs is exhasted yet, `args` contain items
michael@0:       // from each input so we yield application of `f` over them.
michael@0:       if (!done)
michael@0:         yield f(...args);
michael@0:     }
michael@0:   }
michael@0: });
michael@0: exports.map = map;
michael@0: 
michael@0: // Returns a lazy sequence of the intermediate values of the reduction (as
michael@0: // per reduce) of sequence by `f`, starting with `initial` value if provided.
michael@0: //
michael@0: // Implements clojure reductions:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/reductions
michael@0: const reductions = (...params) => {
michael@0:   const count = params.length;
michael@0:   let hasInitial = false;
michael@0:   let f, initial, source;
michael@0:   if (count === 2) {
michael@0:     ([f, source]) = params;
michael@0:   }
michael@0:   else if (count === 3) {
michael@0:     ([f, initial, source]) = params;
michael@0:     hasInitial = true;
michael@0:   }
michael@0:   else {
michael@0:     throw Error("Invoked with wrong number of arguments: " + count);
michael@0:   }
michael@0: 
michael@0:   const sequence = seq(source);
michael@0: 
michael@0:   return seq(function* () {
michael@0:     let started = hasInitial;
michael@0:     let result = void(0);
michael@0: 
michael@0:     // If initial is present yield it.
michael@0:     if (hasInitial)
michael@0:       yield (result = initial);
michael@0: 
michael@0:     // For each item of the sequence accumulate new result.
michael@0:     for (let item of sequence) {
michael@0:       // If nothing has being yield yet set result to first
michael@0:       // item and yield it.
michael@0:       if (!started) {
michael@0:         started = true;
michael@0:         yield (result = item);
michael@0:       }
michael@0:       // Otherwise accumulate new result and yield it.
michael@0:       else {
michael@0:         yield (result = f(result, item));
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     // If nothing has being yield yet it's empty sequence and no
michael@0:     // `initial` was provided in which case we need to yield `f()`.
michael@0:     if (!started)
michael@0:       yield f();
michael@0:   });
michael@0: };
michael@0: exports.reductions = reductions;
michael@0: 
michael@0: // `f` should be a function of 2 arguments. If `initial` is not supplied,
michael@0: // returns the result of applying `f` to the first 2 items in sequence, then
michael@0: // applying `f` to that result and the 3rd item, etc. If sequence contains no
michael@0: // items, `f` must accept no arguments as well, and reduce returns the
michael@0: // result of calling f with no arguments. If sequence has only 1 item, it
michael@0: // is returned and `f` is not called. If `initial` is supplied, returns the
michael@0: // result of applying `f` to `initial` and the first item in  sequence, then
michael@0: // applying `f` to that result and the 2nd item, etc. If sequence contains no
michael@0: // items, returns `initial` and `f` is not called.
michael@0: //
michael@0: // Implements clojure reduce:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/reduce
michael@0: const reduce = (...args) => {
michael@0:   const xs = reductions(...args);
michael@0:   let x;
michael@0:   for (x of xs) void(0);
michael@0:   return x;
michael@0: };
michael@0: exports.reduce = reduce;
michael@0: 
michael@0: const each = (f, sequence) => {
michael@0:   for (let x of seq(sequence)) void(f(x));
michael@0: };
michael@0: exports.each = each;
michael@0: 
michael@0: 
michael@0: const inc = x => x + 1;
michael@0: // Returns the number of items in the sequence. `count(null)` && `count()`
michael@0: // returns `0`. Also works on strings, arrays, Maps & Sets.
michael@0: 
michael@0: // Implements clojure count:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/count
michael@0: const count = polymorphic({
michael@0:   null: _ => 0,
michael@0:   void: _ => 0,
michael@0:   indexed: indexed => indexed.length,
michael@0:   map: map => map.size,
michael@0:   set: set => set.size,
michael@0:   default: xs => reduce(inc, 0, xs)
michael@0: });
michael@0: exports.count = count;
michael@0: 
michael@0: // Returns `true` if sequence has no items.
michael@0: 
michael@0: // Implements clojure empty?:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/empty_q
michael@0: const isEmpty = sequence => {
michael@0:   // Treat `null` and `undefined` as empty sequences.
michael@0:   if (sequence === null || sequence === void(0))
michael@0:     return true;
michael@0: 
michael@0:   // If contains any item non empty so return `false`.
michael@0:   for (let _ of sequence)
michael@0:     return false;
michael@0: 
michael@0:   // If has not returned yet, there was nothing to iterate
michael@0:   // so it's empty.
michael@0:   return true;
michael@0: };
michael@0: exports.isEmpty = isEmpty;
michael@0: 
michael@0: const and = (a, b) => a && b;
michael@0: 
michael@0: // Returns true if `p(x)` is logical `true` for every `x` in sequence, else
michael@0: // `false`.
michael@0: //
michael@0: // Implements clojure every?:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/every_q
michael@0: const isEvery = (p, sequence) => {
michael@0:   if (sequence !== null && sequence !== void(0)) {
michael@0:     for (let item of sequence) {
michael@0:       if (!p(item))
michael@0:         return false;
michael@0:     }
michael@0:   }
michael@0:   return true;
michael@0: };
michael@0: exports.isEvery = isEvery;
michael@0: 
michael@0: // Returns the first logical true value of (p x) for any x in sequence,
michael@0: // else `null`.
michael@0: //
michael@0: // Implements clojure some:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/some
michael@0: const some = (p, sequence) => {
michael@0:   if (sequence !== null && sequence !== void(0)) {
michael@0:     for (let item of sequence) {
michael@0:       if (p(item))
michael@0:         return true;
michael@0:     }
michael@0:   }
michael@0:   return null;
michael@0: };
michael@0: exports.some = some;
michael@0: 
michael@0: // Returns a lazy sequence of the first `n` items in sequence, or all items if
michael@0: // there are fewer than `n`.
michael@0: //
michael@0: // Implements clojure take:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/take
michael@0: const take = (n, sequence) => n <= 0 ? empty() : seq(function* () {
michael@0:   let count = n;
michael@0:   for (let item of sequence) {
michael@0:     yield item;
michael@0:     count = count - 1;
michael@0:     if (count === 0) break;
michael@0:   }
michael@0: });
michael@0: exports.take = take;
michael@0: 
michael@0: // Returns a lazy sequence of successive items from sequence while
michael@0: // `p(item)` returns `true`. `p` must be free of side-effects.
michael@0: //
michael@0: // Implements clojure take-while:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/take-while
michael@0: const takeWhile = (p, sequence) => seq(function* () {
michael@0:   for (let item of sequence) {
michael@0:     if (!p(item))
michael@0:       break;
michael@0: 
michael@0:     yield item;
michael@0:   }
michael@0: });
michael@0: exports.takeWhile = takeWhile;
michael@0: 
michael@0: // Returns a lazy sequence of all but the first `n` items in
michael@0: // sequence.
michael@0: //
michael@0: // Implements clojure drop:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/drop
michael@0: const drop = (n, sequence) => seq(function* () {
michael@0:   if (sequence !== null && sequence !== void(0)) {
michael@0:     let count = n;
michael@0:     for (let item of sequence) {
michael@0:       if (count > 0)
michael@0:         count = count - 1;
michael@0:       else
michael@0:         yield item;
michael@0:     }
michael@0:   }
michael@0: });
michael@0: exports.drop = drop;
michael@0: 
michael@0: // Returns a lazy sequence of the items in sequence starting from the
michael@0: // first item for which `p(item)` returns falsy value.
michael@0: //
michael@0: // Implements clojure drop-while:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/drop-while
michael@0: const dropWhile = (p, sequence) => seq(function* () {
michael@0:   let keep = false;
michael@0:   for (let item of sequence) {
michael@0:     keep = keep || !p(item);
michael@0:     if (keep) yield item;
michael@0:   }
michael@0: });
michael@0: exports.dropWhile = dropWhile;
michael@0: 
michael@0: // Returns a lazy sequence representing the concatenation of the
michael@0: // suplied sequences.
michael@0: //
michael@0: // Implements clojure conact:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/concat
michael@0: const concat = (...sequences) => seq(function* () {
michael@0:   for (let sequence of sequences)
michael@0:     for (let item of sequence)
michael@0:       yield item;
michael@0: });
michael@0: exports.concat = concat;
michael@0: 
michael@0: // Returns the first item in the sequence.
michael@0: //
michael@0: // Implements clojure first:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/first
michael@0: const first = sequence => {
michael@0:   if (sequence !== null && sequence !== void(0)) {
michael@0:     for (let item of sequence)
michael@0:       return item;
michael@0:   }
michael@0:   return null;
michael@0: };
michael@0: exports.first = first;
michael@0: 
michael@0: // Returns a possibly empty sequence of the items after the first.
michael@0: //
michael@0: // Implements clojure rest:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/rest
michael@0: const rest = sequence => drop(1, sequence);
michael@0: exports.rest = rest;
michael@0: 
michael@0: // Returns the value at the index. Returns `notFound` or `undefined`
michael@0: // if index is out of bounds.
michael@0: const nth = (xs, n, notFound) => {
michael@0:   if (n >= 0) {
michael@0:     if (isArray(xs) || isArguments(xs) || isString(xs)) {
michael@0:       return n < xs.length ? xs[n] : notFound;
michael@0:     }
michael@0:     else if (xs !== null && xs !== void(0)) {
michael@0:       let count = n;
michael@0:       for (let x of xs) {
michael@0:         if (count <= 0)
michael@0:           return x;
michael@0: 
michael@0:         count = count - 1;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0:   return notFound;
michael@0: };
michael@0: exports.nth = nth;
michael@0: 
michael@0: // Return the last item in sequence, in linear time.
michael@0: // If `sequence` is an array or string or arguments
michael@0: // returns in constant time.
michael@0: // Implements clojure last:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/last
michael@0: const last = polymorphic({
michael@0:   null: _ => null,
michael@0:   void: _ => null,
michael@0:   indexed: indexed => indexed[indexed.length - 1],
michael@0:   map: xs => reduce((_, x) => x, xs),
michael@0:   set: xs => reduce((_, x) => x, xs),
michael@0:   default: xs => reduce((_, x) => x, xs)
michael@0: });
michael@0: exports.last = last;
michael@0: 
michael@0: // Return a lazy sequence of all but the last `n` (default 1) items
michael@0: // from the give `xs`.
michael@0: //
michael@0: // Implements clojure drop-last:
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/drop-last
michael@0: const dropLast = flip((xs, n=1) => seq(function* () {
michael@0:   let ys = [];
michael@0:   for (let x of xs) {
michael@0:     ys.push(x);
michael@0:     if (ys.length > n)
michael@0:       yield ys.shift();
michael@0:   }
michael@0: }));
michael@0: exports.dropLast = dropLast;
michael@0: 
michael@0: // Returns a lazy sequence of the elements of `xs` with duplicates
michael@0: // removed
michael@0: //
michael@0: // Implements clojure distinct
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/distinct
michael@0: const distinct = sequence => seq(function* () {
michael@0:   let items = new Set();
michael@0:   for (let item of sequence) {
michael@0:     if (!items.has(item)) {
michael@0:       items.add(item);
michael@0:       yield item;
michael@0:     }
michael@0:   }
michael@0: });
michael@0: exports.distinct = distinct;
michael@0: 
michael@0: // Returns a lazy sequence of the items in `xs` for which
michael@0: // `p(x)` returns false. `p` must be free of side-effects.
michael@0: //
michael@0: // Implements clojure remove
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/remove
michael@0: const remove = (p, xs) => filter(complement(p), xs);
michael@0: exports.remove = remove;
michael@0: 
michael@0: // Returns the result of applying concat to the result of
michael@0: // `map(f, xs)`. Thus function `f` should return a sequence.
michael@0: //
michael@0: // Implements clojure mapcat
michael@0: // http://clojuredocs.org/clojure_core/clojure.core/mapcat
michael@0: const mapcat = (f, sequence) => seq(function* () {
michael@0:   const sequences = map(f, sequence);
michael@0:   for (let sequence of sequences)
michael@0:     for (let item of sequence)
michael@0:       yield item;
michael@0: });
michael@0: exports.mapcat = mapcat;