Repository: gcanti/fp-ts (ts)

Issue:
Array to model non-determinism
## 🐛 Bug report

I have been using `Array` in combination with `liftA2` to model some non-determinism / cartesian product-like calculations. I did this under the assumption that `Array` would behave similar to `List` in Haskell. Maybe this assumption is wrong tough?

With fp-ts 2 removing the `liftN` functions and recommending `sequenceS` and `sequenceT` instead, I decided to have a go at refactoring my implementation using `sequenceS`. But to my surprise this didn’t result in the same behavior.

I can probably work around it for now by using `comprehension` instead. Though I would still like to know if this is the expected behavior for `Array`.

I have done some tests to reproduce this with both 1.19.4 and 2.0.2

### Current Behavior

1.19.4
```
liftA2 [
  '1 - a', '1 - b',
  '1 - c', '2 - a',
  '2 - b', '2 - c',
  '3 - a', '3 - b',
  '3 - c'
]
sequenceS [
  '1 - c', '1 - c',
  '1 - c', '2 - c',
  '2 - c', '2 - c',
  '3 - c', '3 - c',
  '3 - c'
]
sequenceT [
  '1 - a', '1 - b',
  '1 - c', '2 - a',
  '2 - b', '2 - c',
  '3 - a', '3 - b',
  '3 - c'
]
```

2.0.2
```
sequenceS [
  '1 - c', '1 - c',
  '1 - c', '2 - c',
  '2 - c', '2 - c',
  '3 - c', '3 - c',
  '3 - c'
]
sequenceT [
  '1 - a', '1 - a',
  '1 - a', '2 - a',
  '2 - a', '2 - a',
  '3 - a', '3 - a',
  '3 - a'
]
```

### Expected behavior

I expected that all the variants should result in the same output as the `liftA2` variant.

It is also interesting that `sequenceT` behaves like `liftA2` in 1.19.4 but completely different in 2.0.2.

### Reproducible example

This is the code that produces the above output.

1.19.4
```typescript
import { liftA2, sequenceS, sequenceT } from "fp-ts/lib/Apply";                                                                              
import { array, map } from "fp-ts/lib/Array";
import { curry } from "fp-ts/lib/function";
import { pipe } from "fp-ts/lib/pipeable";

function test(x: number, y: string): string {
  return `${x} - ${y}`;
}

const a1 = [1, 2, 3]; 
const a2 = ["a", "b", "c"];

const t1 = liftA2(array)(curry(test))(a1)(a2);
const t2 = pipe(
  sequenceS(array)({ x: a1, y: a2 }), 
  map(({ x, y }) => test(x, y)) 
);
const t3 = pipe(
  sequenceT(array)(a1, a2),
  map(([x, y]) => test(x, y)) 
);

console.log("liftA2", t1);
console.log("sequenceS", t2);
console.log("sequenceT", t3);
```

2.0.2
```typescript
import { sequenceS, sequenceT } from "fp-ts/lib/Apply";
import { array, map } from "fp-ts/lib/Array";
import { pipe } from "fp-ts/lib/pipeable";

function test(x: number, y: string): string {
  return `${x} - ${y}`;
}

const a1 = [1, 2, 3]; 
const a2 = ["a", "b", "c"];

const t2 = pipe(
  sequenceS(array)({ x: a1, y: a2 }),                                                                                                        
  map(({ x, y }) => test(x, y))
);
const t3 = pipe(
  sequenceT(array)(a1, a2),
  map(([x, y]) => test(x, y)) 
);

console.log("sequenceS", t2);
console.log("sequenceT", t3);
```

### Your environment

It mostly worked in 1.19.4 apart from `sequenceS` and not at all in 2.0.2

| Software   | Version(s) |
| ---------- | ---------- |
| fp-ts      |      1.19.4 & 2.0.2      |
| TypeScript |      3.5.3      |


Pull request description:
fix `sequenceT`, `sequenceS` implementations, closes #914

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index a2255880..629ef71f 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -14,6 +14,11 @@
 **Note**: Gaps between patch versions are faulty/broken releases. **Note**: A feature tagged as Experimental is in a
 high state of flux, you're at risk of it changing without notice.
 
+# 2.0.3
+
+- **Bug Fix**
+  - fix `sequenceT`, `sequenceS` implementations, closes #914 (@gcanti)
+
 # 2.0.2
 
 - **Bug Fix**
diff --git a/package.json b/package.json
index fd0b0e16..90879fcf 100644
--- a/package.json
+++ b/package.json
@@ -1,6 +1,6 @@
 {
   "name": "fp-ts",
-  "version": "2.0.2",
+  "version": "2.0.3",
   "description": "Functional programming in TypeScript",
   "files": [
     "lib",
diff --git a/src/Apply.ts b/src/Apply.ts
index 6bc29f0f..644ec311 100644
--- a/src/Apply.ts
+++ b/src/Apply.ts
@@ -12,6 +12,7 @@
  */
 import { Functor, Functor1, Functor2, Functor2C, Functor3, Functor4 } from './Functor'
 import { HKT, Kind, Kind2, Kind3, Kind4, URIS, URIS2, URIS3, URIS4 } from './HKT'
+import { tuple } from './function'
 
 /**
  * @since 2.0.0
@@ -55,6 +56,22 @@ export interface Apply4<F extends URIS4> extends Functor4<F> {
   readonly ap: <S, R, E, A, B>(fab: Kind4<F, S, R, E, (a: A) => B>, fa: Kind4<F, S, R, E, A>) => Kind4<F, S, R, E, B>
 }
 
+function curried(f: Function, n: number, acc: Array<unknown>) {
+  return function(x: unknown) {
+    const combined = acc.concat([x])
+    return n === 0 ? f.apply(null, combined) : curried(f, n - 1, combined)
+  }
+}
+
+const tupleConstructors: Record<number, (a: unknown) => unknown> = {}
+
+function getTupleConstructor(len: number): (a: unknown) => any {
+  if (!tupleConstructors.hasOwnProperty(len)) {
+    tupleConstructors[len] = curried(tuple, len - 1, [])
+  }
+  return tupleConstructors[len]
+}
+
 /**
  * Tuple sequencing, i.e., take a tuple of monadic actions and does them from left-to-right, returning the resulting tuple.
  *
@@ -95,19 +112,13 @@ export function sequenceT<F>(
 ): <T extends Array<HKT<F, any>>>(
   ...t: T & { 0: HKT<F, any> }
 ) => HKT<F, { [K in keyof T]: [T[K]] extends [HKT<F, infer A>] ? A : never }>
-export function sequenceT<F>(F: Apply<F>): (...args: Array<HKT<F, any>>) => HKT<F, any> {
-  return (...args: Array<HKT<F, any>>) => {
-    const fst = args[0]
-    const others = args.slice(1)
-    let fas: HKT<F, Array<any>> = F.map(fst, a => [a])
-    for (const fa of others) {
-      fas = F.ap(
-        F.map(fas, as => (a: any) => {
-          as.push(a)
-          return as
-        }),
-        fa
-      )
+export function sequenceT<F>(F: Apply<F>): any {
+  return <A>(...args: Array<HKT<F, A>>) => {
+    const len = args.length
+    const f = getTupleConstructor(len)
+    let fas = F.map(args[0], f)
+    for (let i = 1; i < len; i++) {
+      fas = F.ap(fas, args[i])
     }
     return fas
   }
@@ -115,6 +126,21 @@ export function sequenceT<F>(F: Apply<F>): (...args: Array<HKT<F, any>>) => HKT<
 
 type EnforceNonEmptyRecord<R> = keyof R extends never ? never : R
 
+function getRecordConstructor(keys: Array<string>) {
+  const len = keys.length
+  return curried(
+    (...args: Array<unknown>) => {
+      const r: Record<string, unknown> = {}
+      for (let i = 0; i < len; i++) {
+        r[keys[i]] = args[i]
+      }
+      return r
+    },
+    len - 1,
+    []
+  )
+}
+
 /**
  * Like `Apply.sequenceT` but works with structs instead of tuples.
  *
@@ -169,17 +195,11 @@ export function sequenceS<F>(
 export function sequenceS<F>(F: Apply<F>): (r: Record<string, HKT<F, any>>) => HKT<F, Record<string, any>> {
   return r => {
     const keys = Object.keys(r)
-    const fst = keys[0]
-    const others = keys.slice(1)
-    let fr: HKT<F, Record<string, any>> = F.map(r[fst], a => ({ [fst]: a }))
-    for (const key of others) {
-      fr = F.ap(
-        F.map(fr, r => (a: any) => {
-          r[key] = a
-          return r
-        }),
-        r[key]
-      )
+    const len = keys.length
+    const f = getRecordConstructor(keys)
+    let fr = F.map(r[keys[0]], f)
+    for (let i = 1; i < len; i++) {
+      fr = F.ap(fr, r[keys[i]])
     }
     return fr
   }


Test patch:
diff --git a/test/Apply.ts b/test/Apply.ts
index 79b3ce3e..f36c5309 100644
--- a/test/Apply.ts
+++ b/test/Apply.ts
@@ -1,12 +1,9 @@
 import * as assert from 'assert'
-import { sequenceT, sequenceS } from '../src/Apply'
-import { either, left, right, getValidation } from '../src/Either'
-import { none, option, some, isSome, isNone } from '../src/Option'
-import * as fc from 'fast-check'
-import { getSome } from './property-test/Option'
-import { nonEmptyArray } from './property-test/NonEmptyArray'
-import { getEq, array, getMonoid } from '../src/Array'
-import { fromEquals } from '../src/Eq'
+import { sequenceS, sequenceT } from '../src/Apply'
+import { array, getMonoid } from '../src/Array'
+import { either, getValidation, left, right } from '../src/Either'
+import { none, option, some } from '../src/Option'
+import { pipe } from '../src/pipeable'
 
 describe('Apply', () => {
   it('sequenceT', () => {
@@ -15,19 +12,35 @@ describe('Apply', () => {
     assert.deepStrictEqual(sequenceTOption(some(1), some('2')), some([1, '2']))
     assert.deepStrictEqual(sequenceTOption(some(1), some('2'), none), none)
 
-    const S = getEq(fromEquals((x, y) => x === y))
-    const somes = getSome(fc.oneof<string | number>(fc.string(), fc.integer()))
-    const allSomesInput = nonEmptyArray(somes)
-    const maybeNoneInput = nonEmptyArray(fc.oneof(fc.constant(none), somes))
-    const input = fc.oneof(allSomesInput, maybeNoneInput)
-    fc.assert(
-      fc.property(input, options => {
-        const x = sequenceTOption(...(options as any))
-        return (
-          (options.every(isSome) && isSome(x) && S.equals(x.value as any, array.compact(options))) ||
-          (options.some(isNone) && isNone(x))
-        )
-      })
+    // #914
+    const a1 = [1, 2, 3]
+    const a2 = ['a', 'b', 'c']
+    const a3 = [true, false]
+    assert.deepStrictEqual(
+      pipe(
+        sequenceT(array)(a1, a2, a3),
+        arr => arr.map(([x, y, z]) => `(${x}, ${y}, ${z})`)
+      ),
+      [
+        '(1, a, true)',
+        '(1, a, false)',
+        '(1, b, true)',
+        '(1, b, false)',
+        '(1, c, true)',
+        '(1, c, false)',
+        '(2, a, true)',
+        '(2, a, false)',
+        '(2, b, true)',
+        '(2, b, false)',
+        '(2, c, true)',
+        '(2, c, false)',
+        '(3, a, true)',
+        '(3, a, false)',
+        '(3, b, true)',
+        '(3, b, false)',
+        '(3, c, true)',
+        '(3, c, false)'
+      ]
     )
   })
 
@@ -47,5 +60,36 @@ describe('Apply', () => {
     assert.deepStrictEqual(adoValidation({ a: right(1), b: right(2) }), right({ a: 1, b: 2 }))
     assert.deepStrictEqual(adoValidation({ a: right(1), b: left(['error']) }), left(['error']))
     assert.deepStrictEqual(adoValidation({ a: left(['error1']), b: left(['error2']) }), left(['error1', 'error2']))
+
+    // #914
+    const a1 = [1, 2, 3]
+    const a2 = ['a', 'b', 'c']
+    const a3 = [true, false]
+    assert.deepStrictEqual(
+      pipe(
+        sequenceS(array)({ a1, a2, a3 }),
+        arr => arr.map(({ a1, a2, a3 }) => `(${a1}, ${a2}, ${a3})`)
+      ),
+      [
+        '(1, a, true)',
+        '(1, a, false)',
+        '(1, b, true)',
+        '(1, b, false)',
+        '(1, c, true)',
+        '(1, c, false)',
+        '(2, a, true)',
+        '(2, a, false)',
+        '(2, b, true)',
+        '(2, b, false)',
+        '(2, c, true)',
+        '(2, c, false)',
+        '(3, a, true)',
+        '(3, a, false)',
+        '(3, b, true)',
+        '(3, b, false)',
+        '(3, c, true)',
+        '(3, c, false)'
+      ]
+    )
   })
 })