Repository: calmm-js/partial.lenses
Pull request #59 (2017-02-27 21:12:28)

WIP: Experimental lazy traversals
An approach to #56 

PR to get CI feedback

codecov-io: # [Codecov](https://codecov.io/gh/calmm-js/partial.lenses/pull/59?src=pr&el=h1) Report
> Merging [#59](https://codecov.io/gh/calmm-js/partial.lenses/pull/59?src=pr&el=desc) into [master](https://codecov.io/gh/calmm-js/partial.lenses/commit/f0e9c51b19deadc95647d6b18d6d5d660098cb16?src=pr&el=desc) will **decrease** coverage by `-1.18%`.
> The diff coverage is `70.58%`.


```diff
@@            Coverage Diff             @@
##           master      #59      +/-   ##
==========================================
- Coverage     100%   98.82%   -1.18%     
==========================================
  Files           1        1              
  Lines         417      427      +10     
==========================================
+ Hits          417      422       +5     
- Misses          0        5       +5
```


| [Impacted Files](https://codecov.io/gh/calmm-js/partial.lenses/pull/59?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/partial.lenses.js](https://codecov.io/gh/calmm-js/partial.lenses/compare/f0e9c51b19deadc95647d6b18d6d5d660098cb16...ba316580eba08a78923b24d1c979b0d1ba94f268?src=pr&el=tree#diff-c3JjL3BhcnRpYWwubGVuc2VzLmpz) | `98.82% <70.58%> (-1.18%)` | :x: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/calmm-js/partial.lenses/pull/59?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/calmm-js/partial.lenses/pull/59?src=pr&el=footer). Last update [f0e9c51...ba31658](https://codecov.io/gh/calmm-js/partial.lenses/compare/f0e9c51b19deadc95647d6b18d6d5d660098cb16...ba316580eba08a78923b24d1c979b0d1ba94f268?el=footer&src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

Patch:
diff --git a/README.md b/README.md
index ed10452..a7c5bd9 100644
--- a/README.md
+++ b/README.md
@@ -61,6 +61,8 @@ parts.  [▶ Try Lenses!](https://calmm-js.github.io/partial.lenses/)
     * [Folds over traversals](#folds-over-traversals)
       * [`L.collect(traversal, maybeData) ~> [...values]`](#L-collect "L.collect: PTraversal s a -> Maybe s -> [a]")
       * [`L.collectAs((maybeValue, index) => maybeValue, traversal, maybeData) ~> [...values]`](#L-collectAs "L.collectAs: ((Maybe a, Index) -> Maybe b) -> PTraversal s a -> Maybe s -> [b]")
+      * [`L.first(traversal, maybeData) ~> maybeValue`](#L-first "L.first: PTraversal s a -> Maybe s -> Maybe a")
+      * [`L.firstAs((maybeValue, index) => maybeValue, traversal, maybeData) ~> maybeValue`](#L-firstAs "L.firstAs: ((Maybe a, Index) -> Maybe b) -> PTraversal s a -> Maybe s -> Maybe b")
       * [`L.foldl((value, maybeValue, index) => value, value, traversal, maybeData) ~> value`](#L-foldl "L.foldl: ((r, Maybe a, Index) -> r) -> r -> PTraversal s a -> Maybe s -> r")
       * [`L.foldr((value, maybeValue, index) => value, value, traversal, maybeData) ~> value`](#L-foldr "L.foldr: ((r, Maybe a, Index) -> r) -> r -> PTraversal s a -> Maybe s -> r")
       * [`L.maximum(traversal, maybeData) ~> maybeValue`](#L-maximum "L.maximum: Ord a => PTraversal s a -> Maybe s -> Maybe a")
@@ -1121,6 +1123,55 @@ L.concatAs(R.pipe(R.negate, toCollect),
 The internal implementation of `L.collectAs` is optimized and faster than the
 above naïve implementation.
 
+##### <a name="L-first"></a> [≡](#contents) [▶](https://calmm-js.github.io/partial.lenses/#L-first) [`L.first(traversal, maybeData) ~> maybeValue`](#L-first "L.first: PTraversal s a -> Maybe s -> Maybe a")
+
+**WARNING: `L.first` and [`L.firstAs`](#L-firstAs) are experimental features.**
+
+`L.first` goes lazily over the elements focused on by the given traversal and
+returns the first non-`undefined` element.
+
+```js
+L.first([L.elems, "y"], [{x:1},{y:2},{z:3}])
+// 2
+```
+
+Note that `L.first` is equivalent to [`L.firstAs(R.identity)`](#L-firstAs).
+
+##### <a name="L-firstAs"></a> [≡](#contents) [▶](https://calmm-js.github.io/partial.lenses/#L-firstAs) [`L.firstAs((maybeValue, index) => maybeValue, traversal, maybeData) ~> maybeValue`](#L-firstAs "L.firstAs: ((Maybe a, Index) -> Maybe b) -> PTraversal s a -> Maybe s -> Maybe b")
+
+**WARNING: [`L.first`](#L-first) and `L.firstAs` are experimental features.**
+
+`L.firstAs` goes lazily over the elements focused on by the given traversal,
+applying the given function to each element, and returns the first
+non-`undefined` value returned by the function.
+
+```js
+L.firstAs(x => x > 3 ? -x : undefined, L.elems, [3,1,4,1,5])
+// -4
+```
+
+`L.firstAs` operates lazily.  The user specified function is only applied to
+elements until the first non-`undefined` value is returned and after that
+`L.firstAs` returns without examining more elements.
+
+Note that `L.firstAs` can be used to implement many other operations over
+traversals such as finding an element matching a predicate and checking whether
+all/any elements match a predicate.  For example, here is how you could
+implement a for all predicate over traversals:
+
+```js
+const all = R.curry((p, t, s) => !L.firstAs(x => p(x) ? undefined : true, t, s))
+```
+
+Now:
+
+```js
+all(x => x < 9,
+    flatten,
+    [[[1], 2], {y: 3}, [{l: 4, r: [5]}, {x: 6}]])
+// true
+```
+
 ##### <a name="L-foldl"></a> [≡](#contents) [▶](https://calmm-js.github.io/partial.lenses/#L-foldl) [`L.foldl((value, maybeValue, index) => value, value, traversal, maybeData) ~> value`](#L-foldl "L.foldl: ((r, Maybe a, Index) -> r) -> r -> PTraversal s a -> Maybe s -> r")
 
 `L.foldl` performs a fold from left over the elements focused on by the given
diff --git a/bench/bench.js b/bench/bench.js
index 0ba4d75..3b5b18d 100644
--- a/bench/bench.js
+++ b/bench/bench.js
@@ -116,6 +116,8 @@ const everywhere = [L.optional, L.lazy(rec => {
 
 const xyzs = L.seq("x","y","z")
 
+const pi = [3,1,4,1,5]
+
 const Benchmark = require("benchmark")
 Benchmark.options.maxTime = Number(process.argv[2]) || Benchmark.options.maxTime
 
@@ -132,6 +134,14 @@ R.forEach(bs => {
   s.run()
 }, [
   [
+    `L.firstAs(x => x > 3 ? x : undefined, L.elems, xs100)`,
+    `R.find(x => x > 3, xs100)`,
+    `O.Fold.findOf(O.Traversal.traversed, x => x > 3, xs100)`,
+  ], [
+    `L.firstAs(x => x < 3 ? x : undefined, L.elems, xs100)`,
+    `R.find(x => x < 3, xs100)`,
+    [`O.Fold.findOf(O.Traversal.traversed, x => x < 3, xs100)`, "NO SHORTCUT EVALUATION"],
+  ], [
     `L.foldr(add, 0, L.elems, xs100)`,
     `O.Fold.foldrOf(O.Traversal.traversed, addC, 0, xs100)`,
     `R.reduceRight(add, 0, xs100)`,
@@ -310,6 +320,10 @@ R.forEach(bs => {
     `L.concatAs(toList, List, L.elems, xs100)`,
   ], [
     `L.modify(flatten, inc, xsss100)`,
+  ], [
+    `L.firstAs(x => x > 3 ? x : undefined, L.elems, pi)`,
+    `R.find(x => x > 3, pi)`,
+    `O.Fold.findOf(O.Traversal.traversed, x => x > 3, pi)`,
   ], [
     `L.get(d0x0y, axay)`,
   ], [
diff --git a/src/partial.lenses.js b/src/partial.lenses.js
index a2980af..2e8a3a0 100644
--- a/src/partial.lenses.js
+++ b/src/partial.lenses.js
@@ -60,7 +60,12 @@ const Ident = {map: applyU, of: id, ap: applyU, chain: applyU}
 
 const Const = {map: sndU}
 
-const ConcatOf = (ap, empty) => ({map: sndU, ap, of: always(empty)})
+function ConcatOf(ap, empty, delay) {
+  const c = {map: sndU, ap, of: always(empty)}
+  if (delay)
+    c.delay = delay
+  return c
+}
 
 const Monoid = (concat, empty) => ({concat, empty: () => empty})
 
@@ -146,13 +151,33 @@ const Collect = ConcatOf(join)
 
 //
 
+function the(v) {
+  function result() {return result}
+  result.v = v
+  return result
+}
+
+const First = ConcatOf((l, r) => l && l() || r && r(), void 0, id)
+
+//
+
+const traversePartialIndexLazy = (map, ap, z, delay, xi2yA, xs, i, n) =>
+  i < n
+  ? ap(map(cjoin, xi2yA(xs[i], i)), delay(() =>
+       traversePartialIndexLazy(map, ap, z, delay, xi2yA, xs, i+1, n)))
+  : z
+
 function traversePartialIndex(A, xi2yA, xs) {
-  const ap = A.ap, map = A.map
   if (process.env.NODE_ENV !== "production")
     reqApplicative(A)
-  let xsA = (0,A.of)(void 0), i = xs.length
-  while (i--)
-    xsA = ap(map(cjoin, xi2yA(xs[i], i)), xsA)
+  const {map, ap, of, delay} = A
+  let xsA = of(void 0),
+      i = xs.length
+  if (delay)
+    xsA = traversePartialIndexLazy(map, ap, xsA, delay, xi2yA, xs, 0, i)
+  else
+    while (i--)
+      xsA = ap(map(cjoin, xi2yA(xs[i], i)), xsA)
   return map(toArray, xsA)
 }
 
@@ -363,20 +388,34 @@ const branchOnMerge = (x, keys) => xs => {
   return r
 }
 
+function branchOnLazy(keys, vals, map, ap, z, delay, A, xi2yA, x, i) {
+  if (i < keys.length) {
+    const k = keys[i], v = x[k]
+    return ap(map(cpair,
+                  vals ? vals[i](A, xi2yA, x[k], k) : xi2yA(v, k)), delay(() =>
+              branchOnLazy(keys, vals, map, ap, z, delay, A, xi2yA, x, i+1)))
+  } else {
+    return z
+  }
+}
+
 const branchOn = (keys, vals) => (A, xi2yA, x, _) => {
   if (process.env.NODE_ENV !== "production")
     reqApplicative(A)
-  const of = A.of
+  const {map, ap, of, delay} = A
   let i = keys.length
   if (!i)
     return of(object0ToUndefined(x))
   if (!(x instanceof Object))
     x = object0
-  const ap = A.ap, map = A.map
   let xsA = of(0)
-  while (i--) {
-    const k = keys[i], v = x[k]
-    xsA = ap(map(cpair, vals ? vals[i](A, xi2yA, v, k) : xi2yA(v, k)), xsA)
+  if (delay) {
+    xsA = branchOnLazy(keys, vals, map, ap, xsA, delay, A, xi2yA, x, 0)
+  } else {
+    while (i--) {
+      const k = keys[i], v = x[k]
+      xsA = ap(map(cpair, vals ? vals[i](A, xi2yA, v, k) : xi2yA(v, k)), xsA)
+    }
   }
   return map(branchOnMerge(x, keys), xsA)
 }
@@ -517,7 +556,7 @@ export function log() {
 // Operations on traversals
 
 export const concatAs = curryN(4, (xMi2y, m) => {
-  const C = ConcatOf(m.concat, (0,m.empty)())
+  const C = ConcatOf(m.concat, (0,m.empty)(), m.delay)
   return (t, s) => run(t, C, xMi2y, s)
 })
 
@@ -546,6 +585,20 @@ export const collectAs = curry((xi2y, t, s) =>
 
 export const collect = collectAs(id)
 
+export const firstAs = curry((xi2yM, t, s) => {
+  if (process.env.NODE_ENV !== "production" && !firstAs.warned) {
+    firstAs.warned = 1
+    console.warn("partial.lenses: `first` and `firstAs` are experimental features.")
+  }
+  return (s = run(t,
+                  First,
+                  (x, i) => (x = xi2yM(x, i), void 0 !== x ? the(x) : x),
+                  s),
+          s && (s = s()) && s.v)
+})
+
+export const first = firstAs(id)
+
 export const foldl = curry((f, r, t, s) =>
   fold(f, r, run(t, Collect, pair, s)))
 


Test patch:
diff --git a/test/core.js b/test/core.js
index ec2d12b..d3ea9ae 100644
--- a/test/core.js
+++ b/test/core.js
@@ -59,6 +59,10 @@ export const concat = concatAs(R.identity)
 export const merge = concat
 export const mergeAs = concatAs
 
+export const firstAs = L.firstAs
+
+export const first = L.firstAs(R.identity)
+
 export const foldl = foldx(R.pipe)
 export const foldr = foldx(R.compose)
 
diff --git a/test/tests.js b/test/tests.js
index 9c14d8b..22eefdf 100644
--- a/test/tests.js
+++ b/test/tests.js
@@ -568,10 +568,13 @@ describe("L.getInverse", () => {
   testEq('L.getInverse(offBy1, 1)', 0)
 })
 
-export const flatten = L.lazy(rec => {
-  const nest = [L.elems, rec]
-  return L.choose(x => R.is(Array, x) ? nest : L.identity)
-})
+export const flatten = [L.optional, L.lazy(rec => {
+  const elems = [L.elems, rec]
+  const values = [L.values, rec]
+  return L.choose(x => (x instanceof Array ? elems :
+                        x instanceof Object ? values :
+                        L.identity))
+})]
 
 describe("L.lazy", () => {
   testEq('L.collect(flatten, [[[1], 2], 3, [4, [[5]], [6]]])',
@@ -743,3 +746,21 @@ describe("seq", () => {
   testEq(`collectM(L.seq(1, 0, 2), ["b", "a", "c"])`,
          ["a", "b", "c"])
 })
+
+describe("firstAs", () => {
+  testEq(`L.first(L.elems, [])`, undefined)
+  testEq(`L.first(L.values, {})`, undefined)
+  testEq(`L.firstAs((x, i) => x > 3 ? [x + 2, i] : undefined,
+                    L.elems,
+                    [3, 1, 4, 1, 5])`,
+         [6, 2])
+  testEq(`L.firstAs((x, i) => x > 3 ? [x + 2, i] : undefined,
+                    L.values,
+                    {a:3, b:1, c:4, d:1, e:5})`,
+         [6, "c"])
+  testEq(`L.firstAs(x => {}, L.values, {x:1})`, undefined)
+  testEq(`L.firstAs(x => x < 9 ? undefined : [x],
+                    flatten,
+                    [[[1], 2], {y: 3}, [{l: 41, r: [5]}, {x: 6}]])`,
+        [41])
+})
diff --git a/test/types.js b/test/types.js
index 6b07851..6f37644 100644
--- a/test/types.js
+++ b/test/types.js
@@ -9,17 +9,22 @@ const T_functor = T.object({
   map: T.fn([T.fn([T.any], T.any), T.any], T.any)
 })
 
-const T_applicative = T.object({
-  map: T.fn([T.fn([T.any], T.any), T.any], T.any),
+const T_applicative = T.or(T.object({
+  delay: T.fn([T.any], T.any),
   of: T.fn([T.any], T.any),
-  ap: T.fn([T.any, T.any], T.any)
-})
+  ap: T.fn([T.any, T.any], T.any),
+  map: T.fn([T.fn([T.any], T.any), T.any], T.any)
+}), T.object({
+  of: T.fn([T.any], T.any),
+  ap: T.fn([T.any, T.any], T.any),
+  map: T.fn([T.fn([T.any], T.any), T.any], T.any)
+}))
 
 const T_monad = T.object({
   chain: T.fn([T.fn([T.any], T.any), T.any], T.any),
-  map: T.fn([T.fn([T.any], T.any), T.any], T.any),
   of: T.fn([T.any], T.any),
-  ap: T.fn([T.any, T.any], T.any)
+  ap: T.fn([T.any, T.any], T.any),
+  map: T.fn([T.fn([T.any], T.any), T.any], T.any)
 })
 
 const T_opticFnOf = Category =>
@@ -34,7 +39,8 @@ const T_opticOf = Category => T.lazy(T_optic => T.or(
   T.string,
   T.array(T_optic),
   T.fn([T_maybeData, T_index], T_maybeData),
-  T_opticFnOf(Category)))
+  T_opticFnOf(Category)
+))
 
 const T_optic = T_opticOf(T.or(T_monad, T_applicative, T_functor))
 
@@ -83,6 +89,13 @@ export const concat = T.fn([T_monoid, T_traversal, T_maybeData], T.any)
 export const mergeAs = concatAs
 export const merge = concat
 
+export const firstAs =
+  T.fn([T.fn([T_maybeData, T_index], T.any),
+        T_traversal,
+        T_maybeData],
+       T.any)
+export const first = T.fn([T_traversal, T_maybeData], T.any)
+
 export const foldl =
   T.fn([T.fn([T.any, T_maybeData, T_index], T.any),
         T.any,