Repository: gcanti/fp-ts (ts)

Issue:
Performance of sequenceT & sequenceS
## 🐛 Bug report

In general we're very happy with fp-ts performance, but recently we've noticed small problems with sequenceT and specifically the `curried` function. It's not a huge problem - but a noticeable one and it would be nice if it could be fixed.

### Reproducible example

fp-ts generic curried of 1 and 2 arguments + a handrolled curried of 2 arguments for reference.

https://stackblitz.com/edit/fp-ts-curried-performance-jc38ka?file=index.js

```

curried(1) x 4,532,421 ops/sec ±1.45% (65 runs sampled)

curried(2) x 2,342,792 ops/sec ±0.88% (65 runs sampled)

curried2 handrolled x 34,394,850 ops/sec ±1.55% (62 runs sampled)

```

### Suggested solution(s)

1. (approx 1 order of magnitude, 5-10 x times speed up) Replace `acc.concat([x])` with a faster implementation of `concat`:
```
const fastConcat = <T>(a: T[], b: T) => {
  const result = Array(a.length + 1);

  for (let i = 0; i < a.length; i++) {
    result[i] = a[i];
  }
  result[a.length] = b;
  return result;
};
```
2. (solid 1 order of magnitude, 10-50 x times speed up) Handroll the first N (5?) curried implementations, ie.
```
function curried2<T>(f: Function) {
  return function (x1: T) {
    return function (x2: T) {
      return f(x1, x2);
    };
  }
}
```
*) alternatively first N implementations could be autogenerated, although this might be a controversial suggestion:
```const f = Function("f", `return ${range(1, N).map(n => `x${n}`).join(" => ")} => f(${range(1, N).map(n => `x${n}`).join(" + ")})`);```


### Your environment

| Software   | Version(s) |
| ---------- | ---------- |
| fp-ts      |      2.5.3      |
| TypeScript |   3.9.3         |


Pull request:
improve performance of sequenceT and sequenceS, fix #1255
**Before**

`sequenceT`

```
sequenceT (1) x 3,038,314 ops/sec ±1.06% (86 runs sampled)
sequenceT (2) x 1,486,717 ops/sec ±1.80% (86 runs sampled)
sequenceT (3) x 1,033,153 ops/sec ±0.79% (85 runs sampled)
sequenceT (4) x 799,994 ops/sec ±0.81% (87 runs sampled)
sequenceT (5) x 625,985 ops/sec ±0.80% (90 runs sampled)
```

`sequenceS`

```
sequenceS (1) x 2,723,960 ops/sec ±0.78% (86 runs sampled)
sequenceS (2) x 1,266,164 ops/sec ±0.74% (89 runs sampled)
sequenceS (3) x 809,389 ops/sec ±1.03% (89 runs sampled)
sequenceS (4) x 638,330 ops/sec ±1.43% (86 runs sampled)
sequenceS (5) x 522,986 ops/sec ±1.21% (89 runs sampled)
```

**After**

`sequenceT`

```
sequenceT (1) x 15,737,986 ops/sec ±0.71% (88 runs sampled)
sequenceT (2) x 8,389,840 ops/sec ±0.65% (86 runs sampled)
sequenceT (3) x 5,759,450 ops/sec ±0.54% (90 runs sampled)
sequenceT (4) x 4,307,637 ops/sec ±1.44% (85 runs sampled)
sequenceT (5) x 3,464,223 ops/sec ±1.75% (85 runs sampled)
```

`sequenceS`

```
sequenceS (1) x 13,783,868 ops/sec ±1.90% (82 runs sampled)
sequenceS (2) x 8,007,962 ops/sec ±1.55% (83 runs sampled)
sequenceS (3) x 4,969,669 ops/sec ±1.50% (86 runs sampled)
sequenceS (4) x 3,796,491 ops/sec ±0.98% (87 runs sampled)
sequenceS (5) x 2,973,628 ops/sec ±0.50% (89 runs sampled)
```

/cc @pbadenski

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 8290b11d..a7d889ff 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -19,10 +19,13 @@ high state of flux, you're at risk of it changing without notice.
 - **Bug Fix**
   - `These`
     - fix `ap` implementation in `getMonad` function (@gcanti)
+- **Polish**
+  - improve performance of sequenceT and sequenceS, fix #1255 (@gcanti)
 - **New Feature**
   - `function`
     - add `hole` (type hole simulation) (@gcanti)
   - `Array`
+    - add `chainWithIndex`, #1256 (@OliverJAsh)
     - add `functorArray` instance (@gcanti)
     - add `functorWithIndexArray` instance (@gcanti)
     - add `applicativeArray` instance (@gcanti)
@@ -141,6 +144,7 @@ high state of flux, you're at risk of it changing without notice.
     - add `bifunctorReaderTaskEither` instance (@gcanti)
     - add `altReaderTaskEither` instance (@gcanti)
   - `ReadonlyArray`
+    - add `chainWithIndex`, #1256 (@OliverJAsh)
     - add `functorArray` instance (@gcanti)
     - add `functorWithIndexArray` instance (@gcanti)
     - add `applicativeArray` instance (@gcanti)
diff --git a/docs/modules/Array.ts.md b/docs/modules/Array.ts.md
index bf6845c4..3c527b56 100644
--- a/docs/modules/Array.ts.md
+++ b/docs/modules/Array.ts.md
@@ -135,6 +135,7 @@ Added in v2.0.0
   - [unsafeInsertAt](#unsafeinsertat)
   - [unsafeUpdateAt](#unsafeupdateat)
 - [utils](#utils)
+  - [chainWithIndex](#chainwithindex)
   - [chunksOf](#chunksof)
   - [comprehension](#comprehension)
   - [deleteAt](#deleteat)
@@ -1763,6 +1764,16 @@ Added in v2.0.0
 
 # utils
 
+## chainWithIndex
+
+**Signature**
+
+```ts
+export declare const chainWithIndex: <A, B>(f: (index: number, a: A) => B[]) => (ma: A[]) => B[]
+```
+
+Added in v2.7.0
+
 ## chunksOf
 
 Splits an array into length-`n` pieces. The last piece will be shorter if `n` does not evenly divide the length of
diff --git a/docs/modules/ReadonlyArray.ts.md b/docs/modules/ReadonlyArray.ts.md
index 09ed2578..ce884c31 100644
--- a/docs/modules/ReadonlyArray.ts.md
+++ b/docs/modules/ReadonlyArray.ts.md
@@ -127,6 +127,7 @@ Added in v2.5.0
   - [unsafeUpdateAt](#unsafeupdateat)
 - [utils](#utils)
   - [Spanned (interface)](#spanned-interface)
+  - [chainWithIndex](#chainwithindex)
   - [chunksOf](#chunksof)
   - [comprehension](#comprehension)
   - [deleteAt](#deleteat)
@@ -1556,6 +1557,16 @@ export interface Spanned<I, R> {
 
 Added in v2.5.0
 
+## chainWithIndex
+
+**Signature**
+
+```ts
+export declare const chainWithIndex: <A, B>(f: (i: number, a: A) => readonly B[]) => (ma: readonly A[]) => readonly B[]
+```
+
+Added in v2.7.0
+
 ## chunksOf
 
 Splits an array into length-`n` pieces. The last piece will be shorter if `n` does not evenly divide the length of
diff --git a/perf/Apply/sequenceS.ts b/perf/Apply/sequenceS.ts
new file mode 100644
index 00000000..ee04bba5
--- /dev/null
+++ b/perf/Apply/sequenceS.ts
@@ -0,0 +1,45 @@
+import * as Benchmark from 'benchmark'
+import * as A from '../../src/Apply'
+import * as E from '../../src/Either'
+
+/*
+sequenceS (1) x 13,783,868 ops/sec ±1.90% (82 runs sampled)
+sequenceS (2) x 8,007,962 ops/sec ±1.55% (83 runs sampled)
+sequenceS (3) x 4,969,669 ops/sec ±1.50% (86 runs sampled)
+sequenceS (4) x 3,796,491 ops/sec ±0.98% (87 runs sampled)
+sequenceS (5) x 2,973,628 ops/sec ±0.50% (89 runs sampled)
+sequenceS (6) x 1,126,226 ops/sec ±3.36% (84 runs sampled)
+*/
+
+const suite = new Benchmark.Suite()
+
+const sequenceS = A.sequenceS(E.applicativeEither)
+
+suite
+  .add('sequenceS (1)', function () {
+    sequenceS({ a: E.right(1) })
+  })
+  .add('sequenceS (2)', function () {
+    sequenceS({ a: E.right(1), b: E.right(2) })
+  })
+  .add('sequenceS (3)', function () {
+    sequenceS({ a: E.right(1), b: E.right(2), c: E.right(3) })
+  })
+  .add('sequenceS (4)', function () {
+    sequenceS({ a: E.right(1), b: E.right(2), c: E.right(3), d: E.right(4) })
+  })
+  .add('sequenceS (5)', function () {
+    sequenceS({ a: E.right(1), b: E.right(2), c: E.right(3), d: E.right(4), e: E.right(5) })
+  })
+  .add('sequenceS (6)', function () {
+    sequenceS({ a: E.right(1), b: E.right(2), c: E.right(3), d: E.right(4), e: E.right(5), f: E.right(6) })
+  })
+  .on('cycle', function (event: any) {
+    // tslint:disable-next-line: no-console
+    console.log(String(event.target))
+  })
+  .on('complete', function (this: any) {
+    // tslint:disable-next-line: no-console
+    console.log('Fastest is ' + this.filter('fastest').map('name'))
+  })
+  .run({ async: true })
diff --git a/perf/Apply/sequenceT.ts b/perf/Apply/sequenceT.ts
new file mode 100644
index 00000000..47dcdb1d
--- /dev/null
+++ b/perf/Apply/sequenceT.ts
@@ -0,0 +1,45 @@
+import * as Benchmark from 'benchmark'
+import * as A from '../../src/Apply'
+import * as E from '../../src/Either'
+
+/*
+sequenceT (1) x 15,737,986 ops/sec ±0.71% (88 runs sampled)
+sequenceT (2) x 8,389,840 ops/sec ±0.65% (86 runs sampled)
+sequenceT (3) x 5,759,450 ops/sec ±0.54% (90 runs sampled)
+sequenceT (4) x 4,307,637 ops/sec ±1.44% (85 runs sampled)
+sequenceT (5) x 3,464,223 ops/sec ±1.75% (85 runs sampled)
+sequenceT (6) x 1,899,460 ops/sec ±2.75% (84 runs sampled)
+*/
+
+const suite = new Benchmark.Suite()
+
+const sequenceT = A.sequenceT(E.applicativeEither)
+
+suite
+  .add('sequenceT (1)', function () {
+    sequenceT(E.right(1))
+  })
+  .add('sequenceT (2)', function () {
+    sequenceT(E.right(1), E.right(2))
+  })
+  .add('sequenceT (3)', function () {
+    sequenceT(E.right(1), E.right(2), E.right(3))
+  })
+  .add('sequenceT (4)', function () {
+    sequenceT(E.right(1), E.right(2), E.right(3), E.right(4))
+  })
+  .add('sequenceT (5)', function () {
+    sequenceT(E.right(1), E.right(2), E.right(3), E.right(4), E.right(5))
+  })
+  .add('sequenceT (6)', function () {
+    sequenceT(E.right(1), E.right(2), E.right(3), E.right(4), E.right(5), E.right(6))
+  })
+  .on('cycle', function (event: any) {
+    // tslint:disable-next-line: no-console
+    console.log(String(event.target))
+  })
+  .on('complete', function (this: any) {
+    // tslint:disable-next-line: no-console
+    console.log('Fastest is ' + this.filter('fastest').map('name'))
+  })
+  .run({ async: true })
diff --git a/src/Apply.ts b/src/Apply.ts
index de109bf9..56465aa8 100644
--- a/src/Apply.ts
+++ b/src/Apply.ts
@@ -97,12 +97,22 @@ export interface Apply4<F extends URIS4> extends Functor4<F> {
 
 function curried(f: Function, n: number, acc: ReadonlyArray<unknown>) {
   return function (x: unknown) {
-    const combined = acc.concat([x])
+    const combined = Array(acc.length + 1)
+    for (let i = 0; i < acc.length; i++) {
+      combined[i] = acc[i]
+    }
+    combined[acc.length] = x
     return n === 0 ? f.apply(null, combined) : curried(f, n - 1, combined)
   }
 }
 
-const tupleConstructors: Record<number, (a: unknown) => unknown> = {}
+const tupleConstructors: Record<number, (a: unknown) => any> = {
+  1: (a) => [a],
+  2: (a) => (b: any) => [a, b],
+  3: (a) => (b: any) => (c: any) => [a, b, c],
+  4: (a) => (b: any) => (c: any) => (d: any) => [a, b, c, d],
+  5: (a) => (b: any) => (c: any) => (d: any) => (e: any) => [a, b, c, d, e]
+}
 
 function getTupleConstructor(len: number): (a: unknown) => any {
   if (!tupleConstructors.hasOwnProperty(len)) {
@@ -178,17 +188,41 @@ type EnforceNonEmptyRecord<R> = keyof R extends never ? never : R
 
 function getRecordConstructor(keys: ReadonlyArray<string>) {
   const len = keys.length
-  return curried(
-    (...args: ReadonlyArray<unknown>) => {
-      const r: Record<string, unknown> = {}
-      for (let i = 0; i < len; i++) {
-        r[keys[i]] = args[i]
-      }
-      return r
-    },
-    len - 1,
-    []
-  )
+  switch (len) {
+    case 1:
+      return (a: any) => ({ [keys[0]]: a })
+    case 2:
+      return (a: any) => (b: any) => ({ [keys[0]]: a, [keys[1]]: b })
+    case 3:
+      return (a: any) => (b: any) => (c: any) => ({ [keys[0]]: a, [keys[1]]: b, [keys[2]]: c })
+    case 4:
+      return (a: any) => (b: any) => (c: any) => (d: any) => ({
+        [keys[0]]: a,
+        [keys[1]]: b,
+        [keys[2]]: c,
+        [keys[3]]: d
+      })
+    case 5:
+      return (a: any) => (b: any) => (c: any) => (d: any) => (e: any) => ({
+        [keys[0]]: a,
+        [keys[1]]: b,
+        [keys[2]]: c,
+        [keys[3]]: d,
+        [keys[4]]: e
+      })
+    default:
+      return curried(
+        (...args: ReadonlyArray<unknown>) => {
+          const r: Record<string, unknown> = {}
+          for (let i = 0; i < len; i++) {
+            r[keys[i]] = args[i]
+          }
+          return r
+        },
+        len - 1,
+        []
+      )
+  }
 }
 
 /* tslint:disable:readonly-array */
diff --git a/src/Array.ts b/src/Array.ts
index fb04f0eb..7796caf6 100644
--- a/src/Array.ts
+++ b/src/Array.ts
@@ -1054,6 +1054,13 @@ export const apSecond: <B>(fb: Array<B>) => <A>(fa: Array<A>) => Array<B> = RA.a
  */
 export const chain: <A, B>(f: (a: A) => Array<B>) => (ma: Array<A>) => Array<B> = RA.chain as any
 
+/**
+ * @since 2.7.0
+ */
+export const chainWithIndex: <A, B>(
+  f: (index: number, a: A) => Array<B>
+) => (ma: Array<A>) => Array<B> = RA.chainWithIndex as any
+
 /**
  * Composes computations in sequence, using the return value of one computation to determine the next computation and
  * keeping only the result of the first.
diff --git a/src/ReadonlyArray.ts b/src/ReadonlyArray.ts
index db654505..500227e7 100644
--- a/src/ReadonlyArray.ts
+++ b/src/ReadonlyArray.ts
@@ -1431,13 +1431,16 @@ export const zero: Alternative1<URI>['zero'] = () => empty
 const map_: Monad1<URI>['map'] = (fa, f) => fa.map((a) => f(a))
 const mapWithIndex_: FunctorWithIndex1<URI, number>['mapWithIndex'] = (fa, f) => fa.map((a, i) => f(i, a))
 const ap_: Monad1<URI>['ap'] = (fab, fa) => flatten(map_(fab, (f) => map_(fa, f)))
-const chain_: Monad1<URI>['chain'] = (fa, f) => {
+const chainWithIndex_: <A, B>(fa: ReadonlyArray<A>, f: (i: number, a: A) => ReadonlyArray<B>) => ReadonlyArray<B> = (
+  fa,
+  f
+) => {
   let outLen = 0
   const l = fa.length
   const temp = new Array(l)
   for (let i = 0; i < l; i++) {
     const e = fa[i]
-    const arr = f(e)
+    const arr = f(i, e)
     outLen += arr.length
     temp[i] = arr
   }
@@ -1453,6 +1456,8 @@ const chain_: Monad1<URI>['chain'] = (fa, f) => {
   }
   return out
 }
+const chain_: <A, B>(fa: ReadonlyArray<A>, f: (a: A) => ReadonlyArray<B>) => ReadonlyArray<B> = (fa, f) =>
+  chainWithIndex_(fa, (_index, a) => f(a))
 const filterMap_: Filterable1<URI>['filterMap'] = (as, f) => filterMapWithIndex_(as, (_, a) => f(a))
 const filter_: Filter1<URI> = <A>(as: ReadonlyArray<A>, predicate: Predicate<A>) => as.filter(predicate)
 const partitionWithIndex_: PartitionWithIndex1<URI, number> = <A>(
@@ -1631,6 +1636,13 @@ export const apSecond = <B>(fb: ReadonlyArray<B>) => <A>(fa: ReadonlyArray<A>):
 export const chain: <A, B>(f: (a: A) => ReadonlyArray<B>) => (ma: ReadonlyArray<A>) => ReadonlyArray<B> = (f) => (ma) =>
   chain_(ma, f)
 
+/**
+ * @since 2.7.0
+ */
+export const chainWithIndex: <A, B>(
+  f: (i: number, a: A) => ReadonlyArray<B>
+) => (ma: ReadonlyArray<A>) => ReadonlyArray<B> = (f) => (ma) => chainWithIndex_(ma, f)
+
 /**
  * Composes computations in sequence, using the return value of one computation to determine the next computation and
  * keeping only the result of the first.


Test patch:
diff --git a/test/Apply.ts b/test/Apply.ts
index 65093c3c..0a3da903 100644
--- a/test/Apply.ts
+++ b/test/Apply.ts
@@ -9,8 +9,18 @@ describe('Apply', () => {
   it('sequenceT', () => {
     const sequenceTOption = sequenceT(O.applicativeOption)
     assert.deepStrictEqual(sequenceTOption(O.some(1)), O.some([1]))
-    assert.deepStrictEqual(sequenceTOption(O.some(1), O.some('2')), O.some([1, '2']))
-    assert.deepStrictEqual(sequenceTOption(O.some(1), O.some('2'), O.none), O.none)
+    assert.deepStrictEqual(sequenceTOption(O.some(1), O.some('a')), O.some([1, 'a']))
+    assert.deepStrictEqual(sequenceTOption(O.some(1), O.some('a'), O.some(true)), O.some([1, 'a', true]))
+    assert.deepStrictEqual(sequenceTOption(O.some(1), O.some('a'), O.some(true), O.some(2)), O.some([1, 'a', true, 2]))
+    assert.deepStrictEqual(
+      sequenceTOption(O.some(1), O.some('a'), O.some(true), O.some(2), O.some('b')),
+      O.some([1, 'a', true, 2, 'b'])
+    )
+    assert.deepStrictEqual(
+      sequenceTOption(O.some(1), O.some('a'), O.some(true), O.some(2), O.some('b'), O.some(false)),
+      O.some([1, 'a', true, 2, 'b', false])
+    )
+    assert.deepStrictEqual(sequenceTOption(O.some(1), O.some('a'), O.none), O.none)
 
     // #914
     const a1: ReadonlyArray<number> = [1, 2, 3]
@@ -44,7 +54,23 @@ describe('Apply', () => {
   it('sequenceS', () => {
     const adoOption = sequenceS(O.applicativeOption)
     assert.deepStrictEqual(adoOption({ a: O.some(1) }), O.some({ a: 1 }))
-    assert.deepStrictEqual(adoOption({ a: O.some(1), b: O.some(2) }), O.some({ a: 1, b: 2 }))
+    assert.deepStrictEqual(adoOption({ a: O.some(1), b: O.some('a') }), O.some({ a: 1, b: 'a' }))
+    assert.deepStrictEqual(
+      adoOption({ a: O.some(1), b: O.some('a'), c: O.some(true) }),
+      O.some({ a: 1, b: 'a', c: true })
+    )
+    assert.deepStrictEqual(
+      adoOption({ a: O.some(1), b: O.some('a'), c: O.some(true), d: O.some(2) }),
+      O.some({ a: 1, b: 'a', c: true, d: 2 })
+    )
+    assert.deepStrictEqual(
+      adoOption({ a: O.some(1), b: O.some('a'), c: O.some(true), d: O.some(2), e: O.some('b') }),
+      O.some({ a: 1, b: 'a', c: true, d: 2, e: 'b' })
+    )
+    assert.deepStrictEqual(
+      adoOption({ a: O.some(1), b: O.some('a'), c: O.some(true), d: O.some(2), e: O.some('b'), f: O.some(false) }),
+      O.some({ a: 1, b: 'a', c: true, d: 2, e: 'b', f: false })
+    )
     assert.deepStrictEqual(adoOption({ a: O.some(1), b: O.none }), O.none)
 
     const adoEither = sequenceS(E.applicativeEither)
diff --git a/test/Array.ts b/test/Array.ts
index bc8103da..6fb932a8 100644
--- a/test/Array.ts
+++ b/test/Array.ts
@@ -131,6 +131,16 @@ describe('Array', () => {
       )
     })
 
+    it('chainWithIndex', () => {
+      assert.deepStrictEqual(
+        pipe(
+          [1, 2, 3],
+          _.chainWithIndex((i, n) => [n + i])
+        ),
+        [1, 3, 5]
+      )
+    })
+
     it('chainFirst', () => {
       assert.deepStrictEqual(
         pipe(
diff --git a/test/ReadonlyArray.ts b/test/ReadonlyArray.ts
index aa90752c..4a56ebe4 100644
--- a/test/ReadonlyArray.ts
+++ b/test/ReadonlyArray.ts
@@ -127,6 +127,16 @@ describe('ReadonlyArray', () => {
       )
     })
 
+    it('chainWithIndex', () => {
+      assert.deepStrictEqual(
+        pipe(
+          [1, 2, 3],
+          _.chainWithIndex((i, n) => [n + i])
+        ),
+        [1, 3, 5]
+      )
+    })
+
     it('chainFirst', () => {
       assert.deepStrictEqual(
         pipe(