Support for lazy evaluation of large/infinite lists

[cyberixae]

🚀 Feature request

Support for working with generators and iterators without casting them to array to force evaluation.

Current Behavior

Currently fp-ts only supports fully evaluated arrays which means limits it's use to small arrays. It is often desirable to defined huge structures, while not all the results of that structure are needed.

Desired Behavior

import { pipe } from 'fp-ts/lib/pipeable'
import { map, take } from 'fp-ts/lib/Iterator'
import { enumFrom } from 'fp-ts/lib/Enumeration'

const evenNumbers = pipe(
  enumFrom(0),
  map((x) => 2 * x),
);
expect(pipe(
  evenNumbers,
  take(4),
), [0, 2, 4, 6])

Suggested Solution

Implement new Enumeration and Iterator modules.

Who does this impact? Who is this for?

For everyone. Using iterators makes defining things easier.

Describe alternatives you've considered

It is possible to work around this by sacrificing generality. For example one could create a function that specifically calculates the first 4 even numbers without relaying on a general definition of even numbers.

Additional context

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_Generators https://docs.python.org/3/library/itertools.html https://www.futurelearn.com/courses/functional-programming-haskell/0/steps/27237 http://zvon.org/other/haskell/Outputprelude/enumFromThenTo_f.html

Your environment

I tend to use latest versions of fp-ts and TypeScript where possible.

[cyberixae]

TypeScript 3.6 release notes have. some explanation about related native types https://www.typescriptlang.org/docs/handbook/release-notes/typescript-3-6.html

[raveclassic]

IMO generators/iterators seem a bit out of scope of fp-ts, they are just too specific.

[cyberixae]

To clarify, this issue is not about adding general support for all possible iterator and generator combinations. It is about using iterators to support operations on type LazyArray<A> = Iterator<A, undefined, never> and type NonEmptyLazyArray<A> = Iterator<A, A, never>.

[raveclassic]

I think the proper way for fp-ts would be to support generic IterableIterator and to supply appropriate typeclass instances (Functor etc.). Like the following:

import { Functor1 } from 'fp-ts/lib/Functor';

export const URI = 'IterableIterator';
export type URI = typeof URI;

export interface Iterator<A> {
    readonly next: () => IteratorResult<A, A>;
}

export interface IterableIterator<A> extends Iterator<A> {
    [Symbol.iterator](): Iterator<A>;
}

declare module 'fp-ts/lib/HKT' {
    interface URItoKind<A> {
        [URI]: IterableIterator<A>;
    }
}

export const iterableIterator: Functor1<URI> = {
    URI,
    map: (fa, f) => new MapIterableIterator(fa, f),
};

class MapIterableIterator<A, B> implements IterableIterator<B> {
    constructor(readonly fa: IterableIterator<A>, readonly f: (a: A) => B) {}

    [Symbol.iterator]() {
        return this;
    }

    next() {
        const result = this.fa.next();
        const value = this.f(result.value);
        return {
            done: result.done,
            value,
        };
    }
}

Note that there's also AsyncIterableIterator - should we also support it?

[raveclassic]

There's also https://github.com/ReactiveX/IxJS (and perhaps any other implementation of pull-observables) - should it be added to the core or to something like fp-ts-ixjs?

[raveclassic]

Or it could be even simpler with generators with downlevelIteration: true in tsconfig.json:

import { Monad1 } from 'fp-ts/lib/Monad';
import { Filterable1 } from 'fp-ts/lib/Filterable';
import { identity, not, Predicate } from 'fp-ts/lib/function';
import { isSome, none, some } from 'fp-ts/lib/Option';
import { isLeft } from 'fp-ts/lib/Either';
import { Alternative1 } from 'fp-ts/lib/Alternative';

export const URI = 'Generator';
export type URI = typeof URI;

interface Generator<A> {
    readonly next: () => IteratorResult<A, void>;
    readonly [Symbol.iterator]: () => Generator<A>;
}

declare module 'fp-ts/lib/HKT' {
    interface URItoKind<A> {
        [URI]: Generator<A>;
    }
}

export const generator: Monad1<'Generator'> & Filterable1<'Generator'> & Alternative1<'Generator'> = {
    URI: 'Generator',
    *map(fa, f) {
        for (const a of fa) {
            yield f(a);
        }
    },
    *of(a) {
        yield a;
    },
    *ap(fab, fa) {
        for (const ab of fab) {
            for (const a of fa) {
                yield ab(a);
            }
        }
    },
    *chain(fa, f) {
        for (const a of fa) {
            for (const b of f(a)) {
                yield b;
            }
        }
    },
    *filter<A>(fa: Generator<A>, p: Predicate<A>) {
        for (const a of fa) {
            if (p(a)) {
                yield a;
            }
        }
    },
    *filterMap(fa, f) {
        for (const a of fa) {
            const ob = f(a);
            if (isSome(ob)) {
                yield ob.value;
            }
        }
    },
    compact: fa => generator.filterMap(fa, identity),
    partition<A>(fa: Generator<A>, f: Predicate<A>) {
        return {
            left: generator.filter(fa, not(f)),
            right: generator.filter(fa, f),
        };
    },
    partitionMap(fa, f) {
        return {
            left: generator.filterMap(fa, a => {
                const ebc = f(a);
                return isLeft(ebc) ? some(ebc.left) : none;
            }),
            right: generator.filterMap(fa, a => {
                const ebc = f(a);
                return isLeft(ebc) ? none : some(ebc.right);
            }),
        };
    },
    separate: fa => generator.partitionMap(fa, identity),
    *zero() {},
    *alt(fx, fy) {
        for (const x of fx) {
            yield x;
        }
        for (const y of fy()) {
            yield y;
        }
    },
};

const r = generator.map(
    (function*() {
        yield 1;
    })(),
    n => `${n * 2}`,
);

@gcanti Looks useful to me

[gcanti]

@raveclassic I think that generators should go in a library in its own

[raveclassic]

@gcanti Yeah, this is what I thought first. But on the other hand they are part of the language, not some foreign abstraction like Observable (although it's on its way to ECMA spec). It's the same as Array, Map or Set. Even more we can iterate over them as well.

[cyberixae]

I ended up implementing some helpers for type NonEmptyGeneratorFunction<A> = () => Generator<A, A, undefined>. The quality is not great but they let me experiment with the model. https://github.com/maasglobal/scrapql/blob/master/src/__tests__/negf.ts

[waynevanson]

I love the idea of this, and would like to see this in a library somewhere or in here.

Are there any updates on if someone has been working on this?

[cyberixae]

I still use the code I linked but it has moved to https://github.com/maasglobal/scrapql/blob/master/src/utils/negf.ts https://github.com/maasglobal/scrapql/blob/master/src/utils/__tests__/negf.ts

However, it still more of a temporary hack/experiment and I don't have intention to develop it much further. I think it would be useful to have separate types for Nonempty generator. generator and infinite generator. Also there is need for utilities for converting between arrays and generators.

[cyberixae]

I imagine the type signature would look as follows.

export type GenFResult<A> = IteratorResult<A, void>;
export type GenF<A> = () => Generator<A, void, undefined>;
export type NEGenFResult<A> = IteratorResult<A, A>;
export type NEGenF<A> = () => Generator<A, A, undefined>;
export type InfGenFResult<A> = IteratorResult<A, never>;
export type InfGenF<A> = () => Generator<A, never, undefined>;

[cyberixae]

JavaScript is perhaps soon getting some standard tools for working with iterators. They should at least solve some simple cases and will perhaps make implementing this kind of library easier. https://github.com/tc39/proposal-iterator-helpers

[mtavkhelidze]

@cyberixae I have something similar here: https://gist.github.com/mtavkhelidze/a6191a85670bcff9e1472840add4b5a6

[cyberixae]

JavaScript standard library functions seem to discard the iterator return value. Below are the latest versions of the type signatures I was studying. Unfortunately these are incompatible with the way JavaScript standard library functions deal with iterators. Because these signatures are incompatible to begin with, it might be a good idea to create some 100% incompatible way that suits the use cases of the lazy lists better than standard iterators or generators.

type AbstractList<Y, R> = () => Generator<Y, R, never>
type InfiniteList<A> = AbstractList<A, never>
type NonEmptyList<A> = AbstractList<A, A>
type EmptyList = AbstractList<never, void>
type List<A> = InfiniteList<A>|NonEmptyList<A>|EmptyList

[cyberixae]

I wrote some alternative type signatures for lazy lists. Maybe I end up writing a library. Let me know whether or not you think these signatures would do the job.

import { ReadonlyNonEmptyArray } from './ReadonlyNonEmptyArray'

/* nodes */

export type StaticHead<A> = {
  readonly _tag: 'StaticHead'
  readonly head: ReadonlyNonEmptyArray<A>
  readonly tail: List<A>
}
export type FiniteHead<A> = StaticHead<A> & {
  readonly tail: FiniteList<A>
}

export type LazyHead<A> = {
  readonly _tag: 'LazyHead'
  readonly head: () => Generator<A, void, undefined>
  readonly tail: List<A>
}
export type InfiniteHead<A> = LazyHead<A> & {
  readonly tail: InfiniteList<A>
}

/* terminators */

export type EmptyTail<A> = {
  readonly _tag: 'EmptyTail'
  readonly tail: ReadonlyArray<A> & []
}

export type InfiniteTail<A> = {
  readonly _tag: 'InfiniteTail'
  readonly tail: () => Generator<A, never, undefined>
}

/* possibly infinite */

export type List<A> = LazyHead<A>|StaticHead<A>|EmptyTail<A>|InfiniteTail<A>
export type EmptyList<A> = EmptyTail<A>
export type NonemptyList<A> = StaticHead<A>

/* provably infinite */

export type InfiniteList<A> = InfiniteHead<A>|InfiniteTail<A>
export type EmptyInfiniteList<_A> = never
export type NonEmptyInfiniteList<A> = InfiniteList<A>

/* provably finite */

export type FiniteList<A> = FiniteHead<A>|EmptyTail<A>
export type EmptyFiniteList<A> = EmptyTail<A>
export type NonemptyFiniteList<A> = FiniteHead<A>