Generating sequences using iterators and without integers or arrays

sequence.es6

/////////////////////////////////////////////////////////////////////////////////
// Generating "A Sequence Problem" using iterators, without integers or arrays //
// See http://raganwald.com/2017/06/04/sequences.html                          //
/////////////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////
// Generic things useful for working with interables and iterators //
/////////////////////////////////////////////////////////////////////

// 1. These operations produce repeatable iterables.

function * infinitelyMany (element) {
  while (true) {
    yield element;
  }
}

function list () {
  let elements = arguments;
  
  return ({
    *[Symbol.iterator] () {
      yield * elements;
    }
  });
}

function flatList () {
  const lists = arguments;
  
  return ({
    *[Symbol.iterator] () {
      for (const list of lists) {
        yield * list;
      }
    }
  });
}

const EMPTY = list();

const finiteCopy = iterable => list(...iterable);

// Example of a repeatable iterable:

const ayyBeeCee = list('a', 'b', 'c');

console.log([...ayyBeeCee])
  //=> ['a', 'b', 'c']

console.log([...ayyBeeCee])
  //=> ['a', 'b', 'c']

// 2. These operations do not produce repeatable iterables

function * mapWith (fn, iterable) {
  for (const element of iterable) {
    yield fn(element);
  }
}

function * from(fn, iterable) {
  let latch = false;
  
  for (const element of iterable) {
    if (latch = latch || fn(element)) {
      yield element;
    }
  }
}

function * upTo (fn, iterable) {
  for (const element of iterable) {
    yield element;

    if (fn(element)) break;
  }
}

// Example of an operation returning an unrepeatable iterable:

const oneTwoThree = (function * () {
  yield 1;
  yield 2;
  yield 3
})();

const oneFourNine = mapWith(x => x * x, oneTwoThree);

console.log([...oneFourNine])
  //=> [1, 4, 9]

console.log([...oneFourNine])
  //=> []

// 3. Operations that don't produce iterables

function find (fn, iterable) {
  for (const element of iterable) {
    if (fn(element)) return element;
  }
}

function join (iterable) {
  let str = '';
  
  for (const element of iterable) {
    str = str + element;
  }
  
  return str;
}

/////////////////////////////////////////////////////////////////////////////
// Domain-specific code for producing sequences without integers or arrays //
/////////////////////////////////////////////////////////////////////////////

// 1. Pretty-printing

const isIterable = something => typeof something !== 'string' && typeof something[Symbol.iterator] === 'function';

const deepEqual = (a, b) => {
  if (isIterable(a) && isIterable(b)) {
    const aa = a[Symbol.iterator]();
    const bb = b[Symbol.iterator]();
    
    while (true) {
      const { value: aValue, done: aDone } = aa.next();
      const { value: bValue, done: bDone } = bb.next();
      
      if (aDone && bDone) {
        return true;
      } else if (aDone || bDone) {
        return false;
      } else if (!deepEqual(aValue, bValue)) {
        return false;
      }
    }
  } else if (!isIterable(a) && !isIterable(b)) {
    return a === b;
  } else return false;
}

function pp (something) {
  if (isIterable(something)) {
    return join(
      flatList(
        list('('),
        mapWith(pp, something),
        list(')')
      )
    )
  } else {
    return something.toString();
  }
}

function sp (something, level = 1) {
  if (isIterable(something) && level === 0) {
    return '…';
  } else if (isIterable(something)) {
    return join(
      flatList(
        list('('),
        mapWith(x => sp(x, level - 1), something),
        list(')')
      )
    )
  } else {
    return something.toString();
  }
}

// 2. repeating an action a number of times, given by a representation of the number

function timesDo (number, fn) {
  for (const count of upTo(e => deepEqual(e, number), numbersFromOne())) {
    fn(count);
  }
}

// 3. Overlaying one iterable lazily on top of another, given a period specified as
//    a number in the prepresentation. Example in pseudocode using strings:
//
//    i1 = abcdefghijklmnopqrstuvwxyz...
//    i2 = 123456789...
//    three = list('*', '.')
//
//    overlayPeriodic(three, i2, i1)
//      //=> ab1de2gh3jk4mn5pq6st7vw8yz...

function * overlayPeriodic (period, overlayIterator, baseIterator) {
  while (true) {
    for (const number of numbersFromOne()) {
      if (deepEqual(number, period)) break;
      yield baseIterator.next().value;
    }
    baseIterator.next();

    yield overlayIterator.next().value;
  }
}

// 4. Overlay exponents on a base iterable. Using arabic numbers as an example,
//    The base starts as 0000000000000000000000...
//
//    Given a period of three, we want to overlay that with
//    112112113112112113112112114..., which produces:
//
//    001001002001001002001001003...
//
//    Only, naturally, we want the representations, so it's more like:
//
//    ..*..*..(*)..*..*..(*)..*..*..(*.)..
//
//    This is, for a given prime, the progression of exponents in the representation
//    of every number. Where do we get 112112113112112113112112114 from?
//    By overlaying 223223224223223224223223225... on top of 1111111111111...
//    And where do we get 223223224223223225 from? By overlaying 334334335...
//    on top of 2222222... It's exponents of turtles all the way down.

function * exponents (prime, numberIterator, baseIterator) {
  const baseExponent = numberIterator.next().value;
  const allExponents = exponents(prime, numberIterator, infinitelyMany(baseExponent));

  yield * overlayPeriodic(prime, allExponents, baseIterator);
}

// 5. Create the numbers, managing the exponents for each prime and creating new primes
//    when the exponents for all previously seen primes are zero.

function * numbers () {
  const zero = '.';
  yield zero;

  const one = '*';
  yield one;

  // exponents by prime
  let exponentSequences = EMPTY;

  while (true) {
    
    const factorization = finiteCopy(mapWith(s => s.next().value, exponentSequences));
    
    // it is a new prime if there are no exponents not equal to a dot.
    // this includes the empty case
    const isaNewPrime = !find(e => e !== '.', factorization);

    if (isaNewPrime) {
      const prime = flatList(list('*'), factorization);

      // yield it first so we can recursively get all the numbers up to this prime.
      yield prime;

      const exponentsOfPrime = exponents(prime, numbersFromOne(), infinitelyMany(zero));
      // remove the first numbersofprime, as we have already counted them
      timesDo(prime, () => exponentsOfPrime.next())

      exponentSequences = flatList(list(exponentsOfPrime), exponentSequences);

    } else {
      // not a prime, so return the exponentiations, trimming the lead:
      const trimmed = from(e => e !== '.', factorization);

      yield trimmed;
    }
  }
}

// 6. The numbers from one

function * numbersFromOne () {
  yield * from(e => e === '*', numbers());
}

// Example

const thirtyOne = list('*', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.');

for (const number of upTo(e => deepEqual(e, thirtyOne), numbers())) {
  console.log(pp(number));
}
  //=>
    .
    *
    (*)
    (*.)
    ((*))
    (*..)
    (**)
    (*...)
    ((*.))
    ((*).)
    (*.*)
    (*....)
    (*(*))
    (*.....)
    (*..*)
    (**.)
    (((*)))
    (*......)
    ((*)*)
    (*.......)
    (*.(*))
    (*.*.)
    (*...*)
    (*........)
    (*(*.))
    ((*)..)
    (*....*)
    ((*.).)
    (*..(*))
    (*.........)
    (***)
    (*..........)