Repository: gcanti/fp-ts
Pull request #1461 (2021-03-30 15:35:27)

Backport SK
Backports `SK` from 3.0.0 to 2.11 based on the v2.11 roadmap https://github.com/gcanti/fp-ts/issues/1446



Patch:
diff --git a/docs/modules/function.ts.md b/docs/modules/function.ts.md
index 90672c5f..914ca72f 100644
--- a/docs/modules/function.ts.md
+++ b/docs/modules/function.ts.md
@@ -25,6 +25,7 @@ Added in v2.0.0
   - [Lazy (interface)](#lazy-interface)
   - [Predicate (interface)](#predicate-interface)
   - [Refinement (interface)](#refinement-interface)
+  - [SK](#sk)
   - [absurd](#absurd)
   - [constFalse](#constfalse)
   - [constNull](#constnull)
@@ -227,6 +228,16 @@ export interface Refinement<A, B extends A> {
 
 Added in v2.0.0
 
+## SK
+
+**Signature**
+
+```ts
+export declare const SK: <A, B>(_: A, b: B) => B
+```
+
+Added in v2.11.0
+
 ## absurd
 
 **Signature**
diff --git a/src/Array.ts b/src/Array.ts
index c2512b9c..9feb663e 100644
--- a/src/Array.ts
+++ b/src/Array.ts
@@ -6,6 +6,7 @@ import { Alternative1 } from './Alternative'
 import { Applicative as ApplicativeHKT, Applicative1 } from './Applicative'
 import { apFirst as apFirst_, Apply1, apS as apS_, apSecond as apSecond_ } from './Apply'
 import { bind as bind_, Chain1, chainFirst as chainFirst_ } from './Chain'
+import { ChainRec1 } from './ChainRec'
 import { Compactable1 } from './Compactable'
 import { Either } from './Either'
 import { Eq } from './Eq'
@@ -1273,6 +1274,10 @@ const _wilt: Witherable1<URI>['wilt'] = <F>(
   const wiltF = wilt(F)
   return (fa, f) => pipe(fa, wiltF(f))
 }
+/* istanbul ignore next */
+const _chainRecDepthFirst: ChainRec1<URI>['chainRec'] = RA.ChainRecDepthFirst.chainRec as any
+/* istanbul ignore next */
+const _chainRecBreadthFirst: ChainRec1<URI>['chainRec'] = RA.ChainRecBreadthFirst.chainRec as any
 
 // -------------------------------------------------------------------------------------
 // type class members
@@ -1994,6 +1999,31 @@ export const Witherable: Witherable1<URI> = {
   wilt: _wilt
 }
 
+/**
+ * Exposing depth first recursion by default
+ * @category instances
+ * @since 2.10.0
+ */
+export const ChainRecDepthFirst: ChainRec1<URI> = {
+  URI,
+  map: _map,
+  ap: _ap,
+  chain: _chain,
+  chainRec: _chainRecDepthFirst
+}
+
+/**
+ * @category instances
+ * @since 2.10.0
+ */
+export const ChainRecBreadthFirst: ChainRec1<URI> = {
+  URI,
+  map: _map,
+  ap: _ap,
+  chain: _chain,
+  chainRec: _chainRecBreadthFirst
+}
+
 /**
  * Filter values inside a context.
  *
diff --git a/src/ReadonlyArray.ts b/src/ReadonlyArray.ts
index bf9ae91f..ed11a9f3 100644
--- a/src/ReadonlyArray.ts
+++ b/src/ReadonlyArray.ts
@@ -6,6 +6,7 @@ import { Alternative1 } from './Alternative'
 import { Applicative as ApplicativeHKT, Applicative1 } from './Applicative'
 import { apFirst as apFirst_, Apply1, apS as apS_, apSecond as apSecond_ } from './Apply'
 import { bind as bind_, Chain1, chainFirst as chainFirst_ } from './Chain'
+import { ChainRec1 } from './ChainRec'
 import { Compactable1 } from './Compactable'
 import { Either } from './Either'
 import { Eq, fromEquals } from './Eq'
@@ -1337,6 +1338,54 @@ const _wilt: Witherable1<URI>['wilt'] = <F>(
   const wiltF = wilt(F)
   return (fa, f) => pipe(fa, wiltF(f))
 }
+const _chainRecDepthFirst: ChainRec1<URI>['chainRec'] = <A, B>(
+  a: A,
+  f: (a: A) => ReadonlyArray<Either<A, B>>
+): ReadonlyArray<B> => {
+  // tslint:disable-next-line: readonly-array
+  const todo: Array<Either<A, B>> = [...f(a)]
+  // tslint:disable-next-line: readonly-array
+  const result: Array<B> = []
+
+  while (todo.length > 0) {
+    const e = todo.shift()!
+    if (e._tag === 'Left') {
+      todo.unshift(...f(e.left))
+    } else {
+      result.push(e.right)
+    }
+  }
+
+  return result
+}
+const _chainRecBreadthFirst: ChainRec1<URI>['chainRec'] = <A, B>(
+  a: A,
+  f: (a: A) => ReadonlyArray<Either<A, B>>
+): ReadonlyArray<B> => {
+  const initial = f(a)
+  // tslint:disable-next-line: readonly-array
+  const todo: Array<Either<A, B>> = []
+  // tslint:disable-next-line: readonly-array
+  const result: Array<B> = []
+
+  function go(e: Either<A, B>): void {
+    if (e._tag === 'Left') {
+      f(e.left).forEach((v) => todo.push(v))
+    } else {
+      result.push(e.right)
+    }
+  }
+
+  for (const e of initial) {
+    go(e)
+  }
+
+  while (todo.length > 0) {
+    go(todo.shift()!)
+  }
+
+  return result
+}
 
 // -------------------------------------------------------------------------------------
 // type class members
@@ -2084,6 +2133,31 @@ export const TraversableWithIndex: TraversableWithIndex1<URI, number> = {
   traverseWithIndex: _traverseWithIndex
 }
 
+/**
+ * Exposing depth first recursion by default
+ * @category instances
+ * @since 2.10.0
+ */
+export const ChainRecDepthFirst: ChainRec1<URI> = {
+  URI,
+  map: _map,
+  ap: _ap,
+  chain: _chain,
+  chainRec: _chainRecDepthFirst
+}
+
+/**
+ * @category instances
+ * @since 2.10.0
+ */
+export const ChainRecBreadthFirst: ChainRec1<URI> = {
+  URI,
+  map: _map,
+  ap: _ap,
+  chain: _chain,
+  chainRec: _chainRecBreadthFirst
+}
+
 /**
  * @category instances
  * @since 2.7.0
diff --git a/src/ReadonlyMap.ts b/src/ReadonlyMap.ts
index 554f2d0a..178b2881 100644
--- a/src/ReadonlyMap.ts
+++ b/src/ReadonlyMap.ts
@@ -9,7 +9,7 @@ import { Filterable2 } from './Filterable'
 import { FilterableWithIndex2C } from './FilterableWithIndex'
 import { Foldable, Foldable1, Foldable2, Foldable2C, Foldable3 } from './Foldable'
 import { FoldableWithIndex2C } from './FoldableWithIndex'
-import { pipe, Predicate, Refinement } from './function'
+import { pipe, Predicate, Refinement, SK } from './function'
 import { flap as flap_, Functor2 } from './Functor'
 import { FunctorWithIndex2C } from './FunctorWithIndex'
 import { HKT, Kind, Kind2, Kind3, URIS, URIS2, URIS3 } from './HKT'
@@ -937,7 +937,7 @@ export const getTraversableWithIndex = <K>(O: Ord<K>): TraversableWithIndex2C<UR
 
   const sequence = <F>(F: Applicative<F>): (<A>(ta: ReadonlyMap<K, HKT<F, A>>) => HKT<F, ReadonlyMap<K, A>>) => {
     const traverseWithIndexF = traverseWithIndex(F)
-    return (ta) => traverseWithIndexF(ta, (_, a) => a)
+    return (ta) => traverseWithIndexF(ta, SK)
   }
   return {
     URI,
diff --git a/src/ReadonlyNonEmptyArray.ts b/src/ReadonlyNonEmptyArray.ts
index 091cc9b5..73600abb 100644
--- a/src/ReadonlyNonEmptyArray.ts
+++ b/src/ReadonlyNonEmptyArray.ts
@@ -21,7 +21,7 @@ import { Eq, fromEquals } from './Eq'
 import { Extend1 } from './Extend'
 import { Foldable1 } from './Foldable'
 import { FoldableWithIndex1 } from './FoldableWithIndex'
-import { Endomorphism, identity, Lazy, pipe, Predicate, Refinement } from './function'
+import { Endomorphism, identity, Lazy, pipe, Predicate, Refinement, SK } from './function'
 import { bindTo as bindTo_, flap as flap_, Functor1 } from './Functor'
 import { FunctorWithIndex1 } from './FunctorWithIndex'
 import { HKT } from './HKT'
@@ -749,7 +749,7 @@ export const traverse: PipeableTraverse1<URI> = <F>(
  */
 export const sequence: Traversable1<URI>['sequence'] = <F>(
   F: ApplicativeHKT<F>
-): (<A>(as: ReadonlyNonEmptyArray<HKT<F, A>>) => HKT<F, ReadonlyNonEmptyArray<A>>) => traverseWithIndex(F)((_, a) => a)
+): (<A>(as: ReadonlyNonEmptyArray<HKT<F, A>>) => HKT<F, ReadonlyNonEmptyArray<A>>) => traverseWithIndex(F)(SK)
 
 /**
  * @category TraversableWithIndex
diff --git a/src/ReadonlyRecord.ts b/src/ReadonlyRecord.ts
index 2734e624..87417eb1 100644
--- a/src/ReadonlyRecord.ts
+++ b/src/ReadonlyRecord.ts
@@ -9,7 +9,7 @@ import { Filterable1 } from './Filterable'
 import { FilterableWithIndex1, PredicateWithIndex, RefinementWithIndex } from './FilterableWithIndex'
 import { Foldable as FoldableHKT, Foldable1, Foldable2, Foldable3 } from './Foldable'
 import { FoldableWithIndex1 } from './FoldableWithIndex'
-import { identity, pipe, Predicate, Refinement } from './function'
+import { identity, pipe, Predicate, Refinement, SK } from './function'
 import { flap as flap_, Functor1 } from './Functor'
 import { FunctorWithIndex1 } from './FunctorWithIndex'
 import { HKT, Kind, Kind2, Kind3, URIS, URIS2, URIS3 } from './HKT'
@@ -508,7 +508,7 @@ export function sequence<F>(
 export function sequence<F>(
   F: Applicative<F>
 ): <A>(ta: ReadonlyRecord<string, HKT<F, A>>) => HKT<F, ReadonlyRecord<string, A>> {
-  return traverseWithIndex(F)((_, a) => a)
+  return traverseWithIndex(F)(SK)
 }
 
 /**
diff --git a/src/function.ts b/src/function.ts
index 5e114f35..05d68ff5 100644
--- a/src/function.ts
+++ b/src/function.ts
@@ -748,3 +748,8 @@ export function pipe(
  * @since 2.7.0
  */
 export const hole: <T>() => T = absurd as any
+
+/**
+ * @since 2.11.0
+ */
+export const SK = <A, B>(_: A, b: B): B => b


Test patch:
diff --git a/test/ReadonlyArray.ts b/test/ReadonlyArray.ts
index b2ee1feb..4b4a576d 100644
--- a/test/ReadonlyArray.ts
+++ b/test/ReadonlyArray.ts
@@ -1220,4 +1220,135 @@ describe('ReadonlyArray', () => {
     U.deepStrictEqual(_.size([]), 0)
     U.deepStrictEqual(_.size(['a']), 1)
   })
+
+  describe('chainRec', () => {
+    it('depth-first', () => {
+      const chainRec = _.ChainRecDepthFirst.chainRec
+      assert.deepStrictEqual(
+        chainRec(1, () => []),
+        []
+      )
+      assert.deepStrictEqual(
+        chainRec(1, () => [E.right('foo')]),
+        ['foo']
+      )
+      assert.deepStrictEqual(
+        chainRec(1, (a) => {
+          if (a < 5) {
+            return [E.right(a), E.left(a + 1)]
+          } else {
+            return [E.right(a)]
+          }
+        }),
+        [1, 2, 3, 4, 5]
+      )
+      assert.deepStrictEqual(
+        chainRec(1, (a) => {
+          if (a < 5) {
+            return [E.left(a + 1), E.right(a)]
+          } else {
+            return [E.right(a)]
+          }
+        }),
+        [5, 4, 3, 2, 1]
+      )
+      assert.deepStrictEqual(
+        chainRec(1, (a) => {
+          if (a < 5) {
+            return a % 2 === 0 ? [E.right(a), E.left(a + 1)] : [E.left(a + 1), E.right(a)]
+          } else {
+            return [E.right(a)]
+          }
+        }),
+        [2, 4, 5, 3, 1]
+      )
+      assert.deepStrictEqual(
+        chainRec(0, (a) => {
+          if (a === 0) {
+            return [E.right(a), E.left(a - 1), E.left(a + 1)]
+          } else if (0 < a && a < 5) {
+            return [E.right(a), E.left(a + 1)]
+          } else if (-5 < a && a < 0) {
+            return [E.right(a), E.left(a - 1)]
+          } else {
+            return [E.right(a)]
+          }
+        }),
+        [0, -1, -2, -3, -4, -5, 1, 2, 3, 4, 5]
+      )
+      assert.deepStrictEqual(
+        chainRec(0, (a) => {
+          if (a === 0) {
+            return [E.left(a - 1), E.right(a), E.left(a + 1)]
+          } else if (0 < a && a < 5) {
+            return [E.right(a), E.left(a + 1)]
+          } else if (-5 < a && a < 0) {
+            return [E.left(a - 1), E.right(a)]
+          } else {
+            return [E.right(a)]
+          }
+        }),
+        [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
+      )
+    })
+    it('breadth-first', () => {
+      const chainRec = _.ChainRecBreadthFirst.chainRec
+      assert.deepStrictEqual(
+        chainRec(1, () => []),
+        []
+      )
+      assert.deepStrictEqual(
+        chainRec(1, () => [E.right('foo')]),
+        ['foo']
+      )
+      assert.deepStrictEqual(
+        chainRec(1, (a) => {
+          if (a < 5) {
+            return [E.right(a), E.left(a + 1)]
+          } else {
+            return [E.right(a)]
+          }
+        }),
+        [1, 2, 3, 4, 5]
+      )
+      assert.deepStrictEqual(
+        chainRec(1, (a) => {
+          if (a < 5) {
+            return [E.left(a + 1), E.right(a)]
+          } else {
+            return [E.right(a)]
+          }
+        }),
+        [1, 2, 3, 4, 5]
+      )
+      assert.deepStrictEqual(
+        chainRec(0, (a) => {
+          if (a === 0) {
+            return [E.right(a), E.left(a - 1), E.left(a + 1)]
+          } else if (0 < a && a < 5) {
+            return [E.right(a), E.left(a + 1)]
+          } else if (-5 < a && a < 0) {
+            return [E.right(a), E.left(a - 1)]
+          } else {
+            return [E.right(a)]
+          }
+        }),
+        [0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5]
+      )
+      assert.deepStrictEqual(
+        chainRec(0, (a) => {
+          if (a === 0) {
+            return [E.left(a - 1), E.right(a), E.left(a + 1)]
+          } else if (0 < a && a < 5) {
+            return [E.right(a), E.left(a + 1)]
+          } else if (-5 < a && a < 0) {
+            return [E.left(a - 1), E.right(a)]
+          } else {
+            return [E.right(a)]
+          }
+        }),
+        [0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5]
+      )
+    })
+  })
 })