Code from "Enumerations, Denumerables, and Cardinals"

enumerations.es6

// See: http://raganwald.com/2019/02/27/enumerability.html

// combinators

function slice (generator, n, limit = Infinity) {
  return function * sliced () {
    let i = 0;
    
    for (const element of generator()) {
      if (i++ < n) continue;
      if (i > limit) break;
      
      yield element;
    }
  }
}

const take = (generator, n) => slice(generator, 0, n);

function count (generator) {
  let i = 0;
  
  for (const element of generator()) ++i;
  
  return i;
}

function whileWith (predicate, generator) {
  return function * whiled () {
    for (const element of generator()) {
      if (predicate(element)) {
        yield element;
      } else {
        break;
      }
    }
  }
}

function merge (...generators) {
  return function * merged () {
    const iterables = generators.map(g => g());

    while (true) {
      const values =
        iterables
      	 .map(i => i.next())
         .filter(({done}) => !done)
         .map(({value}) => value)
      if (values.length === 0) break;
      yield * values;
    }
  }
}

function zip (...generators) {
  return function * zipped () {
    const iterables = generators.map(g => g());

    while (true) {
      const values = iterables.map(i => i.next());
      if (values.some(({done}) => done)) break;
      yield values.map(({value}) => value);
    }
  }
}

function concatenate (...generators) {
  return function * concatenated () {
    for (const generator of generators) {
      yield * generator();
    }
  }
}

function concat (generatorOfGenerators) {
  return function * concated () {
    for (const generator of generatorOfGenerators()) {
      yield * generator();
    }
  }
}

function mapWith (fn, g) {
  return function * () {
    for (const e of g()) yield fn(e);
  }
}

function at (generator, index) {
  let i = 0;

  for (const element of generator()) {
    if (i++ === index) return element;
  }
}

function prod2 (g1, g2) {
  return function * () {
  	for (const sum of naturals()) {
      for (const [i1, i2] of zip(upTo(0, sum), downTo(sum, 0))()) {
        yield [at(g1, i1), at(g2, i2)];
      }
    }
  }
}

function prod (first, ...rest) {
  if (rest.length === 0) {
    return mapWith(
    	e => [e],
    	first
      );
  } else {
    return mapWith(
      ([eFirst, eRests]) => [eFirst].concat(eRests),
      prod2(first, prod(...rest))
    );
  }
}

function cons (head, generator) {
  return function * () {
    yield head;
    yield * generator();
  }
}

function just (...elements) {
  return function * () {
    yield * elements;
  }
}

const flatten =
  denumerableOfDenumerables =>
    mapWith(
      ([denumerables, index]) => at(denumerables, index),
      prod2(denumerableOfDenumerables, naturals)
    );

function uniq (generator, keyFn = x => x) {
  return function * uniqued () {
    const seen = new Set();
    
    for (const element of generator()) {
      const key = keyFn(element);
      
      if (seen.has(key)) {
        continue;
      } else {
        seen.add(key);
        yield element;
      }
    }
  }
}

const exponent = (generator, n) => prod(...new Array(n).fill(generator));

const exponentsOf =
  generator =>
    mapWith(
      p => exponent(generator, p),
      upTo(1, Infinity)
    );

const products = generator => cons([], flatten(exponentsOf(generator)));

function combination (generator, k) {
  if (k === 1) {
    return mapWith(
      e => [e],
      generator
    )
  } else {
    return flatten(
      mapWith(
        index => {
          const element = at(generator, index);
          const rest = slice(generator, index + 1);

          return mapWith(
            arr => (arr.unshift(element), arr),
            combination(rest, k - 1)
          );
        },
        naturals
      )
    );
  }
}

const subsets =
  generator =>
    cons(
      [],
      flatten(
        mapWith(
          k => combination(generator, k),
          naturals
        )
      )
    );

// enumerations of numbers

function upTo (start, limit, by = 1) {
  return function * upTo () {
    for (let i = start; i <= limit; i += by) yield i;
  };
}

function downTo (start, limit, by = 1) {
  return function * downTo () {
    for (let i = start; i >= limit; i -= by) yield i;
  }
}

const naturals = upTo(0, Infinity);
const negatives = downTo(-1, -Infinity);
const positives = upTo(1, Infinity);
const integers = merge(naturals, negatives);
const evens = upTo(0, Infinity, 2);
const odds = upTo(1, Infinity, 2);

const rationals = mapWith(
  ([numerator, denominator]) => `${numerator}/${denominator}`,
  prod2(naturals, positives)
);

const exp =
  n =>
    mapWith(
      p => Math.pow(n, p),
      upTo(1, Infinity)
    );

// counter-examples

function nprod2 (g1, g2) {
  return function * () {
  	for (const e1 of g1()) {
      for (const e2 of g2()) {
        yield [e1, e2];
      }
    }
  }
}

// examples

function * fibonacci () {
  yield *
    cons(0,
      cons(1,
        mapWith(
          ([a, b]) => a + b,
          zip(fibonacci, slice(fibonacci, 1))
        )
      )
    )();
}

function isFib (n) {
  const fibsUpToN = whileWith(x => x <= n, fibonacci);
  
  for (const f of fibsUpToN()) {
    if (f === n) return true;
  }
  
  return false;
}

function * productsOfProducts () {
  yield * cons([],
    flatten(exponentsOf(productsOfProducts))
  )();
}

// given a tree of nested arrays, returns a finie enumeration
// of adding a single new array in each possible place
//
// e.g. given [[], []], returns an enumeration of:
//
// [[], [], []]
// [[[]], []]
// [[], [[]]]
function plusOne (tree) {
  const deepClone = tree => tree.map(deepClone);

  return function * plused () {
  	yield deepClone(tree).concat([[]]);
    
    for (let index = 0; index < tree.length; ++index) {
      const child = tree[index];
      
      for (const plussedChild of plusOne(child)()) {
        yield tree.slice(0, index)
          .concat([ plussedChild ])
          .concat(tree.slice(index + 1));
      }
    };
  }
}

// given a generator that returns trees, returns an enumeration of all the ways to plus one all the trees
const plusOneAll = generator =>
  uniq(
    concat(mapWith(plusOne, generator)),
    JSON.stringify
  );

// build recursively
function * treesBySize () {
  yield * cons(just([]),
    mapWith(plusOneAll, treesBySize)
  )();
}

// an enumeration of all tree topologies, ordered by number of nodes
const trees = concat(treesBySize);

function pp (array) {
  return `(${array.map(pp).join('')})`;
}

const lispy = mapWith(pp, trees);
 
const asForest = array => array.map(pp).join('')

const balanced = mapWith(asForest, trees);

function isBalanced (str) {
  const balancedUpToStrLength = whileWith(b => b.length <= str.length, balanced);
  
  for (const b of balancedUpToStrLength()) {
    if (b === str) return true;
  }
  
  return false;
}

function test (recognizer, examples) {
  for (const example of examples) {
    console.log(`'${example}' => ${recognizer(example)}`);
  }
}