Repository: gcanti/fp-ts (ts)

Issue:
Call stack size exception with 5500 elements
## 🐛 Bug report

### Current Behavior

If we have a not so big array and we use traverse or sequence is raising a call stack size exceed

### Expected behavior

Don't throw `RangeError: Maximum call stack size exceeded`

### Reproducible example

```
import * as fp from 'fp-ts'

const doProcessing = (number) => fp.task.task.of(number * 2)

const pipeline = fp.pipeable.pipe(
  
  fp.task.task.of(fp.array.range(1,5500)),
  fp.task.chain( (x) => {
    return fp.array.array.traverse(fp.task.task)(x,doProcessing)
  })
)

pipeline().then(console.log).catch(console.log)
```

### Suggested solution(s)

I guess is trying to execute everything in parallel, can be executed in chunks or sequentially?

### Additional context



### Your environment

I've tried in fp-ts@2.1.1 and fp-ts 2.5.3

<!-- PLEASE FILL THIS OUT -->

| Software   | Version(s) |
| ---------- | ---------- |
| fp-ts      |      2.1.1, 2.5.3      |
| TypeScript |      3.8.3      |


Pull request description:
Stack safety for Task via microtasks suspension
We can improve the stack safety of tasks by forcing suspension of otherwise sync closure calls. 

The suspension mechanism used to trampoline a thunk f is `Promise.resolve().then(f)` that uses microtasks (higher priority compared to setTimeout's)

Effectively closes #1177 for async tasks.

Patch:
diff --git a/docs/modules/Option.ts.md b/docs/modules/Option.ts.md
index 65d51d15..4f28af10 100644
--- a/docs/modules/Option.ts.md
+++ b/docs/modules/Option.ts.md
@@ -241,7 +241,7 @@ Use [`chainNullableK`](#chainnullablek) instead.
 **Signature**
 
 ```ts
-export declare const mapNullable: <A, B>(f: (a: A) => B | null | undefined) => (ma: Option<A>) => Option<B>
+export declare const mapNullable: <A, B>(f: (a: A) => B | null | undefined) => (ma: Option<A>) => Option<NonNullable<B>>
 ```
 
 Added in v2.0.0
@@ -1163,7 +1163,9 @@ This is `chain` + `fromNullable`, useful when working with optional values.
 **Signature**
 
 ```ts
-export declare const chainNullableK: <A, B>(f: (a: A) => B | null | undefined) => (ma: Option<A>) => Option<B>
+export declare const chainNullableK: <A, B>(
+  f: (a: A) => B | null | undefined
+) => (ma: Option<A>) => Option<NonNullable<B>>
 ```
 
 **Example**
diff --git a/src/Option.ts b/src/Option.ts
index 8af53d71..c2917289 100644
--- a/src/Option.ts
+++ b/src/Option.ts
@@ -1043,7 +1043,7 @@ export const fromNullableK: <A extends ReadonlyArray<unknown>, B>(
  * @category interop
  * @since 2.9.0
  */
-export const chainNullableK = <A, B>(f: (a: A) => B | null | undefined) => (ma: Option<A>): Option<B> =>
+export const chainNullableK = <A, B>(f: (a: A) => B | null | undefined) => (ma: Option<A>): Option<NonNullable<B>> =>
   isNone(ma) ? none : fromNullable(f(ma.value))
 
 /**
diff --git a/src/Task.ts b/src/Task.ts
index 4f4ad604..57256baa 100644
--- a/src/Task.ts
+++ b/src/Task.ts
@@ -53,7 +53,7 @@ export interface Task<A> {
  * @category natural transformations
  * @since 2.0.0
  */
-export const fromIO: FromIO1<URI>['fromIO'] = (ma) => () => Promise.resolve(ma())
+export const fromIO: FromIO1<URI>['fromIO'] = (ma) => () => Promise.resolve().then(ma)
 
 // -------------------------------------------------------------------------------------
 // combinators
@@ -90,7 +90,7 @@ export function delay(millis: number): <A>(ma: Task<A>) => Task<A> {
     new Promise((resolve) => {
       setTimeout(() => {
         // tslint:disable-next-line: no-floating-promises
-        ma().then(resolve)
+        Promise.resolve().then(ma).then(resolve)
       }, millis)
     })
 }
@@ -119,7 +119,8 @@ const _chain: Chain1<URI>['chain'] = (ma, f) => pipe(ma, chain(f))
  * @category Functor
  * @since 2.0.0
  */
-export const map: <A, B>(f: (a: A) => B) => (fa: Task<A>) => Task<B> = (f) => (fa) => () => fa().then(f)
+export const map: <A, B>(f: (a: A) => B) => (fa: Task<A>) => Task<B> = (f) => (fa) => () =>
+  Promise.resolve().then(fa).then(f)
 
 /**
  * Apply a function to an argument under a type constructor.
@@ -128,7 +129,7 @@ export const map: <A, B>(f: (a: A) => B) => (fa: Task<A>) => Task<B> = (f) => (f
  * @since 2.0.0
  */
 export const ap: <A>(fa: Task<A>) => <B>(fab: Task<(a: A) => B>) => Task<B> = (fa) => (fab) => () =>
-  Promise.all([fab(), fa()]).then(([f, a]) => f(a))
+  Promise.all([Promise.resolve().then(fab), Promise.resolve().then(fa)]).then(([f, a]) => f(a))
 
 /**
  * @category Pointed
@@ -143,7 +144,9 @@ export const of: Pointed1<URI>['of'] = (a) => () => Promise.resolve(a)
  * @since 2.0.0
  */
 export const chain: <A, B>(f: (a: A) => Task<B>) => (ma: Task<A>) => Task<B> = (f) => (ma) => () =>
-  ma().then((a) => f(a)())
+  Promise.resolve()
+    .then(ma)
+    .then((a) => f(a)())
 
 /**
  * Derivable from `Chain`.
@@ -199,7 +202,7 @@ declare module './HKT' {
  */
 export function getRaceMonoid<A = never>(): Monoid<Task<A>> {
   return {
-    concat: (x, y) => () => Promise.race([x(), y()]),
+    concat: (x, y) => () => Promise.race([Promise.resolve().then(x), Promise.resolve().then(y)]),
     empty: never
   }
 }
@@ -480,7 +483,7 @@ export const ApT: Task<readonly []> =
  */
 export const traverseReadonlyNonEmptyArrayWithIndex = <A, B>(f: (index: number, a: A) => Task<B>) => (
   as: ReadonlyNonEmptyArray<A>
-): Task<ReadonlyNonEmptyArray<B>> => () => Promise.all(as.map((a, i) => f(i, a)())) as any
+): Task<ReadonlyNonEmptyArray<B>> => () => Promise.all(as.map((a, i) => Promise.resolve().then(() => f(i, a)()))) as any
 
 /**
  * Equivalent to `ReadonlyArray#traverseWithIndex(ApplicativePar)`.
@@ -505,12 +508,16 @@ export const traverseReadonlyNonEmptyArrayWithIndexSeq = <A, B>(f: (index: numbe
   _.tail(as).reduce<Promise<NonEmptyArray<B>>>(
     (acc, a, i) =>
       acc.then((bs) =>
-        f(i + 1, a)().then((b) => {
-          bs.push(b)
-          return bs
-        })
+        Promise.resolve()
+          .then(f(i + 1, a))
+          .then((b) => {
+            bs.push(b)
+            return bs
+          })
       ),
-    f(0, _.head(as))().then(_.singleton)
+    Promise.resolve()
+      .then(f(0, _.head(as)))
+      .then(_.singleton)
   )
 
 /**


Test patch:
diff --git a/test/Task.ts b/test/Task.ts
index 174b7b64..76a64083 100644
--- a/test/Task.ts
+++ b/test/Task.ts
@@ -5,7 +5,7 @@ import * as RA from '../src/ReadonlyArray'
 import * as _ from '../src/Task'
 import * as assert from 'assert'
 import * as S from '../src/string'
-import { ReadonlyNonEmptyArray } from '../src/ReadonlyNonEmptyArray'
+import * as RNEA from '../src/ReadonlyNonEmptyArray'
 
 const delayReject = <A>(n: number, a: A): _.Task<A> => () =>
   new Promise<A>((_, reject) => {
@@ -33,6 +33,18 @@ const assertOp = <A, B, C>(f: (a: _.Task<A>, b: _.Task<B>) => _.Task<C>) => asyn
 }
 
 describe('Task', () => {
+  // -------------------------------------------------------------------------------------
+  // safety
+  // -------------------------------------------------------------------------------------
+  it('stack-safe', async () => {
+    const doProcessing = (number: number) => _.of(number * 2)
+    const pipeline = pipe(_.of(RNEA.range(1, 55000)), _.chain(RNEA.traverse(_.ApplicativeSeq)(doProcessing)))
+
+    const res = await pipeline()
+
+    expect(res.length).toBe(55000)
+  })
+
   // -------------------------------------------------------------------------------------
   // pipeables
   // -------------------------------------------------------------------------------------
@@ -165,7 +177,7 @@ describe('Task', () => {
   })
 
   describe('array utils', () => {
-    const input: ReadonlyNonEmptyArray<string> = ['a', 'b']
+    const input: RNEA.ReadonlyNonEmptyArray<string> = ['a', 'b']
 
     it('traverseReadonlyArrayWithIndex', async () => {
       const f = _.traverseReadonlyArrayWithIndex((i, a: string) => _.of(a + i))