Re: short-circuiting Array.prototype.reduce

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: short-circuiting Array.prototype.reduce

Kyle Simpson
> The example code isn't very compelling either; something more real-world would be good

I recently ran across a usage of `reduce(..)` that could have benefitted from an early return. Figured I'd just drop it here for posterity sake, in case anything ever comes of this idea.

I had an array of arrays (2-dimensional array), where each inner array had a list of simple string/number elements (none of them falsy) that could have some repetition within the inner array. I wanted to filter the outer array (the list of the inner arrays) based on whether an inner array had any adjacent duplicates. That is, `[1,4,2,4]` is fine to keep but `[2,4,4,5]` should be filtered out.

Since `reduce(..)` conveniently can compare two adjacent elements if you always return the current value, I decided to model the inner check as a `reduce(..)` that reduces from the original array value to either a `false` or a truthy value (the last element of the inner array element). This reduction result then is how `filter(..)` decides to keep or discard. The reason an early exit would be nice is that as soon as you run across an adjacency-duplication, no more reduction is necessary -- you can immediately "reduce" to `false`.

Here's how I did it, which worked but which was slightly less appealing:

```js
var outer = [
  // [1,2,1,3,4,2]
  // ["foo","bar","bar",10,"foo"]
  // ..
];

outer = outer.filter(function filterer(inner){
  return inner.reduce(function reducer(prev,current){
    if (prev === false || prev === current) return false;
    return current;
  });
});
```

The reduction initial-value is omitted, so it's `undefined`, which never matches any of the `inner` contents.

The `prev === false` check is the way that I fake the "early exit", by which once the reduction value is tripped to `false`, that's always the result for the rest of the reduction.

There's lots of other ways to "slice" that problem, I know. But reduction was attractive except for its lack of early exit.
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: short-circuiting Array.prototype.reduce

Bergi
Kyle Simpson schrieb:

> Since `reduce(..)` conveniently can compare two adjacent elements if you always return the current value, I decided to model the inner check as a `reduce(..)` that reduces from the original array value to either a `false` or a truthy value (the last element of the inner array element).

Um, that's not exactly what reduction is meant for. The reduce method is
designed so that the return values and the accumulator argument do have
the same type. In your example, you have somehow mixed an expected
boolean result with the item type of the array.
This leads to several bug in your implementation, which doesn't work
* with lists of booleans
* with empty arrays
* with arrays whose last element is falsy

 > The example code isn't very compelling either; something more
real-world would be good

Well, basically all operations that return an absorbing element
<https://en.wikipedia.org/wiki/Absorbing_element> would benefit from this.

  Bergi
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: short-circuiting Array.prototype.reduce

Kyle Simpson
> Um, that's not exactly what reduction is meant for.

There's lots of different ways `reduce(..)` gets used in the wild; I can list several entirely distinct but common idioms right off the top of my head. Just because it's not the original intent doesn't mean it's invalid to do so.

To the point of the earlier question I was addressing, I was just giving *an* example of real code, in a very specific circumstance, where I would have liked early-exit. It was not a broad endorsement of the presented idiom as a general pattern.


> The reduce method is designed so that the return values and the accumulator argument do have the same type.

In my observation, there's nothing at all that requires that. This is certainly not the only time that I've made effective use of mixing/toggling types during reduction.


> In your example, you have somehow mixed an expected boolean result with the item type of the array.

If by "expected boolean result" you mean what `filter(..)` expects to receive, actually it doesn't require a strict boolean. It expects a truthy/falsy value (check the spec). I like coercion. I use it liberally. The values in my `inner` arrays were all truthy values (see below) and `filter(..)` works perfectly fine receiving such.


> This leads to several bug in your implementation, which doesn't work

None of those are "bugs" in my implementation, because none of those can happen within the constraints of the problem. If you re-read the stated setup for the problem I was solving, you'll see the constraints I'm referring to.

BTW, since you brought it up, for the empty `inner` array case to be supported (I didn't need it, but...), all I would need to do is `inner.reduce( function.., undefined )` (or `false` if you prefer) if I wanted empty arrays filtered out, or `inner.reduce( function.., true )` if I wanted empty arrays preserved. Easy.


> all operations that return an absorbing element...would benefit

My `false` value trigger on finding an `inner` that should be filtered out is conceptually that. From then on in the reduction, all other values are "absorbed" (aka ignored, aka overriden) by the `false`. :)
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: short-circuiting Array.prototype.reduce

Jason Orendorff
In reply to this post by Kyle Simpson
On Thu, Mar 26, 2015 at 8:22 PM, Kyle Simpson <[hidden email]> wrote:
> outer = outer.filter(function filterer(inner){
>   return inner.reduce(function reducer(prev,current){
>     if (prev === false || prev === current) return false;
>     return current;
>   });
> });

I think you could write that like this:

    outer = outer.filter(arr =>
      !arr.some((e, i) =>
        i > 0 && arr[i-1] === e));

Array.prototype.some is designed to produce a boolean result and
already has early exit built in.

-j
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: short-circuiting Array.prototype.reduce

Kyle Simpson
> I think you could write that like this:
>
>    outer = outer.filter(arr =>
>      !arr.some((e, i) =>
>        i > 0 && arr[i-1] === e));

Yes, you are of course correct. What I was doing in the originally cited code was illustrating using how `reduce(..)` by its nature supports the adjacency check, instead of using indexes and manual `i-1` type logic.

IOW, I initially wanted to avoid the ugly `i-1`, and I traded that for the unfortunate lack of early exit necessitating the equally ugly `prev === false`. :/



_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss