Repository: gcanti/fp-ts
Pull request #1352 (2020-11-13 21:56:34)

Array chain rec
Addition of two implementations of chainRec (depth-first and breadth-first) for ReadonlyArray and Array.

In `ChainRec` instance by default the depth-first method is selected, but there is access to breadth-first via `BreadthFirstChainRec` instances.

As for the optimization of each of the two algorithms, breadth-first avoids initial array copy by having two loops that do the same thing. In depth-first I couldn't avoid copy of the initial array.

qlonik: Friendly bump: is this useful?
gcanti: @qlonik I'm sorry, somehow I missed this PR, I apologize.

Following the current naming convention (for example `SemigroupSum`, `SemigroupProduct`), I would rename: 

- `ChainRec` to `ChainRecDepthFirst`
- `BreadthFirstChainRec` to `ChainRecBreadthFirst`

(I'll retarget this PR to the `2.11` branch which is dedicated to the next release)
qlonik: Done. I also rebased it for clean merge. 

In the `Array.ts` module, I'm reusing implementations from `ReadonlyArray.ts`. It used to be like that for other non-pipeable functions, which is why I implemented like this. However, it seems that now they are implemented independently between two modules. So, should I copy implementation from readonly array to regular array?

Patch:
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


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]
+      )
+    })
+  })
 })