Support for `Stream`

[jituanlin]

It is possible that implement Stream in ts?

I wrote a demo:

import {pipe} from 'fp-ts/function';
import {fold, Option} from 'fp-ts/Option';

export interface Cons<A> {
  head: () => A;
  tail: () => Stream<A>;
  readonly _tag: 'Cons';
}

export interface Empty<A> {
  readonly _tag: 'Empty';
}

export type Stream<A> = Cons<A> | Empty<A>;

export const cons = <A>(head: () => A, tail: () => Stream<A>): Cons<A> => ({
  head,
  tail,
  _tag: 'Cons',
});

export const empty: Empty<unknown> = {
  _tag: 'Empty',
};

export const foldRight = <A, B>(z: B, f: (a: A, b: () => B) => B) => (
  s: Stream<A>
): B => {
  switch (s._tag) {
    case 'Cons':
      return f(s.head(), () => foldRight(z, f)(s.tail()));
    case 'Empty':
      return z;
  }
};

export const exist = <A>(p: (a: A) => boolean) => (s: Stream<A>): boolean =>
  pipe(
    s,
    foldRight(false as boolean, (a, b) => p(a) || b())
  );

export const stream = <A>(...as: ReadonlyArray<A>): Stream<A> => {
  if (as.length === 0) {
    return empty;
  }
  const [head, ...tails] = as;
  return cons(
    () => head,
    () => stream(...tails)
  );
};

export const unfold = <A, S>(z: S, f: (z: S) => Option<[A, S]>): Stream<A> =>
  pipe(
    f(z),
    fold(
      () => empty as Stream<A>,
      ([a, z1]) =>
        cons(
          () => a,
          () => unfold(z1, f)
        )
    )
  );

export const take = (n: number) => <A>(s: Stream<A>): Stream<A> => {
  switch (s._tag) {
    case 'Empty':
      return s;
    case 'Cons':
      if (n == 1) {
        return cons(s.head, () => empty as Empty<A>);
      } else {
        return cons(s.head, () => take(n - 1)(s.tail()));
      }
  }
};

export const toArray = <A>(s: Stream<A>): ReadonlyArray<A> => {
  switch (s._tag) {
    case 'Empty':
      return [];
    case 'Cons':
      return [s.head(), ...toArray(s.tail())];
  }
};

And this is the test:

import {exist, stream, take, toArray, unfold} from './index';
import {pipe} from 'fp-ts/function';
import {none, some} from 'fp-ts/Option';

describe('exist', () => {
  it('should be lazy', function () {
    const evaluated: number[] = [];
    const result = pipe(
      stream(1, 2, -1, 3, 4),
      exist(a => {
        evaluated.push(a);
        return a < 0;
      })
    );
    expect(result).toEqual(true);
    expect(evaluated).toEqual([1, 2, -1]);
  });
});

describe('should take and unfold  be lazy', () => {
  const evaluated: number[] = [];

  const stream = unfold(1, n => {
    evaluated.push(n);
    return n < 10 ? some([n, n + 1]) : none;
  });

  const as = pipe(stream, take(3), toArray);

  expect(as).toEqual([1, 2, 3]);
  expect(evaluated).toEqual([1, 2, 3]);
});

Stream is useful for lazy evaluation.

If is ok to add it to fp-ts, I am happy to make a MR to branch v3.0.0(give me a chance ,pls :) )

[mikearnaldi]

Recursive functions are unsafe, this will lead to stack overflows as soon as the number of elements grow

[waynevanson]

If we can get this as a stack safe operation its more likely to be considered

[mikearnaldi]

If we can get this as a stack safe operation its more likely to be considered

it's honestly very hard to do stack safe with decent performance, given the rest of the data types present I don't think it will be in-scope, maybe an observable like impl