pelotom / immutagen Goto Github PK

type LazyList<T> = Iterable<T> &
  ({ empty: true } | { empty: false; head: T; lazyTail: () => LazyList<T> });

const Empty: LazyList<never> = {
  empty: true,
  *[Symbol.iterator]() {},
};

const Cons = <T>(head: T, lazyTail: () => LazyList<T>): LazyList<T> => {
  return {
    empty: false,
    head,
    lazyTail,
    *[Symbol.iterator]() {
      yield head;
      yield* lazyTail();
    },
  };
};

const ofGenerator = <Params extends any[], T>(
  f: (...params: Params) => Generator<T>,
  ...params: Params
): LazyList<T> => {
  const g = f(...params);
  const cache: T[] = [];
  function lazyListSlice(startIndex: number): LazyList<T> {
    while (startIndex >= cache.length) {
      const { done, value } = g.next();
      if (done) {
        return Empty;
      }
      cache.push(value);
    }
    return Cons(cache[startIndex], () => lazyListSlice(startIndex + 1));
  }
  return lazyListSlice(0);
};

function map<T, U>(ts: LazyList<T>, f: (t: T) => U): LazyList<U> {
  if (ts.empty) {
    return Empty;
  }
  return Cons(f(ts.head), () => map(ts.lazyTail(), f));
}

function merge(as: LazyList<number>, bs: LazyList<number>): LazyList<number> {
  if (as.empty) {
    return bs;
  }
  if (bs.empty) {
    return as;
  }
  // Note: No eager `lazyTail` calls in recursive functions or it stackoverflows
  const [a, alt] = [as.head, as.lazyTail];
  const [b, blt] = [bs.head, bs.lazyTail];
  if (a < b) {
    return Cons(a, () => merge(alt(), bs));
  }
  if (a === b) {
    return Cons(a, () => merge(alt(), blt()));
  }
  if (a > b) {
    return Cons(b, () => merge(as, blt()));
  }
  throw new Error(`Numbers (${a}) and (${b}) are incomparable!`);
}

const smooth = (function () {
  const smoothInstance = Cons(1, makeSmooth);
  function makeSmooth(): LazyList<number> {
    const smoothTimes = (n: number) =>
      map(smoothInstance, (x: number) => x * n);
    return merge(smoothTimes(2), smoothTimes(3));
  }
  return smoothInstance;
})();

const smoothList = [];
for (const i of smooth) {
  if (i > 100000) {
    break;
  }
  smoothList.push(i);
}
console.log(smoothList);
/*
[
      1,     2,     3,     4,     6,     8,     9,    12,    16,
     18,    24,    27,    32,    36,    48,    54,    64,    72,
     81,    96,   108,   128,   144,   162,   192,   216,   243,
    256,   288,   324,   384,   432,   486,   512,   576,   648,
    729,   768,   864,   972,  1024,  1152,  1296,  1458,  1536,
   1728,  1944,  2048,  2187,  2304,  2592,  2916,  3072,  3456,
   3888,  4096,  4374,  4608,  5184,  5832,  6144,  6561,  6912,
   7776,  8192,  8748,  9216, 10368, 11664, 12288, 13122, 13824,
  15552, 16384, 17496, 18432, 19683, 20736, 23328, 24576, 26244,
  27648, 31104, 32768, 34992, 36864, 39366, 41472, 46656, 49152,
  52488, 55296, 59049, 62208, 65536, 69984, 73728, 78732, 82944,
  93312,
  ... 1 more item
]
*/