# Iterator.prototype.findMin, Iterator.prototype.findMax methods

**URL:** <https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859>\
**Category:** 💡 Ideas\
**Tags:** proposal\
**Created:** [December 8, 2023, 5:55pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859 "2023-12-08T17:55:14Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![ducin](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/ducin/32/1949_2.png) [@ducin](https://es.discourse.group/u/ducin)\
**Post date:** [December 8, 2023, 5:55pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/1 "2023-12-08T17:55:14Z")

</div>

This proposal introduces two new [`Iterator.prototype` helper methods](https://github.com/tc39/proposal-iterator-helpers/) which are meant to be a specialized usage of `Array.prototype.reduce`:

- `Iterator.prototype.findMin<T>( comparatorFn: ( valueA: T, valueB: T ): -1|0|1): T | undefined` - find "the smallest" value within a collection, according to a custom order (defined by a comparator function which is the same as `Array.prototype.sort`'s callback as defined in [`23.1.3.30 Array.prototype.sort ( comparefn )` in ES2023 specs](https://ecma-international.org/wp-content/uploads/ECMA-262_14th_edition_june_2023.pdf))
- `Iterator.prototype.findMax<T>( comparatorFn: ( valueA: T, valueB: T ): -1|0|1): T | undefined` - same as above, but "the biggest".

# EXAMPLE

```js
function* peopleGen() {
  yield {name: "Adam", age: 15};
  yield {name: "John", age: 40};
  yield {name: "Lisa", age: 23};
}

const result = peopleGen()
  .findMax((a, b) => a.age - b.age);
result.next(); // {value: {name: "Adam", age: 15}, done: false};
result.next(); // {value: {name: "John", age: 40}, done: false};
result.next(); // {value: {name: "John", age: 40}, done: false};

```

# POLYFILL

not sure if the polyfill is available before [Iterator.prototype](https://github.com/tc39/proposal-iterator-helpers/) becomes available.

# BEFORE

Currently we can achieve it by running the `Array.prototype.reduce`, where the current accumulator is the currently biggest/smallest item out of entire collection:

```js
var people = [
  {name: "Adam", age: 15},
  {name: "John", age: 40},
  {name: "Lisa", age: 23}
];

var theYoungest = people.reduce((minSoFar, item) => {
      if (minSoFar.age < item.age){ // earlier in order
          return minSoFar
      } else if (minSoFar.age > item.age){ // later in order
          return item
      } else { // equal in order
          return minSoFar
      } 
  });

```

The solution currently is perfectly available, though **there's no abstraction** to extract the _comparatorFn_ which is reusable across `.findMin`, `.findMax` and `.sort` array methods.

# AFTER

```js
var people = [
  {name: "Adam", age: 15},
  {name: "John", age: 40},
  {name: "Lisa", age: 23}
];
// var iterator = people.values()
var theYoungest = people.values().findMin((a, b) => a.age - b.age); // {name: "Adam", age: 15}
var theOldest = people.values().findMax((a, b) => a.age - b.age); // {name: "John", age: 40}

```

---

<div class="post-metadata">

**Author:** ![bakkot](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/bakkot/32/22_2.png) [@bakkot](https://es.discourse.group/u/bakkot)\
**Post date:** [December 8, 2023, 5:59pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/2 "2023-12-08T17:59:42Z")

</div>

Unfortunately we've found that adding new methods to Array.prototype is frequently not web-compatible (see e.g. [Web Compatibility Issue: Sugar versions v0.9 through v1.3.9 (inclusive) · Issue #37 · tc39/proposal-array-grouping · GitHub](https://github.com/tc39/proposal-array-grouping/issues/37)), so there is a very high bar for new Array methods (we can't just [break the web](https://github.com/tc39/faq/?tab=readme-ov-file#why-dont-we-just-break-the-web)). So this is unlikely to happen.

---

<div class="post-metadata">

**Author:** ![ducin](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/ducin/32/1949_2.png) [@ducin](https://es.discourse.group/u/ducin)\
**Post date:** [December 8, 2023, 6:01pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/3 "2023-12-08T18:01:25Z")

</div>

_EDIT: original proposal provided `min` and `max`_

Is this only about the names already-polluted-within-the-ecosystem (like old [smoosh gate](https://developer.chrome.com/blog/smooshgate))? If so, different names can be provided, such as `findMin` and `findMax`. Maybe these would be even better...

But if it's about [browser vendors refusing to extend Array.prototype](https://github.com/tc39/proposal-array-grouping/issues/37#issuecomment-1654460788), Object.findMax/Min, Map.findMax/Min is also an option to me. What happened to [array grouping](https://github.com/tc39/proposal-array-grouping) seems like a healthy consensus.

---

<div class="post-metadata">

**Author:** ![bakkot](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/bakkot/32/22_2.png) [@bakkot](https://es.discourse.group/u/bakkot)\
**Post date:** [December 8, 2023, 6:16pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/4 "2023-12-08T18:16:55Z")

</div>

The experience of browsers during the array grouping proposal was that it is not practical to predict which names are already polluted without shipping and breaking sites, which they don't want to do. `groupBy` ended up being polluted in a way we could potentially have known about, so we fell back to `group`, and that was also polluted in a different, more subtle way, across several sites. So as a consequence browsers (understandably) don't want to ship any new string-named methods on Array.prototype.

`Object.findMin`/`Map.findMin` are not really suitable here because these methods don't produce an object or map. A reasonable alternative would be on [`Iterator.prototype`](https://github.com/tc39/proposal-iterator-helpers/), which would let you do `Iterator.from(array).findMin(comparator)`.

---

<div class="post-metadata">

**Author:** ![ducin](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/ducin/32/1949_2.png) [@ducin](https://es.discourse.group/u/ducin)\
**Post date:** [December 8, 2023, 6:28pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/5 "2023-12-08T18:28:55Z")

</div>

@bakkot thank you for absolutely great and quick feedback!  
I have updated the proposal to rely on Iterator.prototype. Would appreciate if you could give some more feedback. Thank you so much in advance!

After having some more thought, due to Array prototype pollution and its consequences, going in the direction of array.values().someNewMethod() make a lot of sense and is not vulnerable to locks caused by historical reasons. Moreover, array.someNewMethod() is greedy in its nature, whereas array.values().someNewMethod() is lazy pulled. The direction looks awesome, at least to me.

---

<div class="post-metadata">

**Author:** ![bakkot](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/bakkot/32/22_2.png) [@bakkot](https://es.discourse.group/u/bakkot)\
**Post date:** [December 8, 2023, 6:38pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/6 "2023-12-08T18:38:29Z")

</div>

Only remaining feedback is that the "thisArg" parameter is no longer relevant (iterator methods don't have it). Otherwise, sounds reasonable to me. Realistically I suspect it will be a while before anyone has the time to champion it. The committee is working through a few other followup iterator helper methods (zip and concat at the moment), and I think these are probably top-20 but not top-5 followup methods.

---

<div class="post-metadata">

**Author:** ![ducin](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/ducin/32/1949_2.png) [@ducin](https://es.discourse.group/u/ducin)\
**Post date:** [December 8, 2023, 6:41pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/7 "2023-12-08T18:41:11Z")

</div>

@bakkot the irrelevant `thisArg` has been removed. Again, thank you very much.

Shall I make an official proposal repository with this anywhere? Sorry for a lame question, but it's the first time I'm going through the process.

---

<div class="post-metadata">

**Author:** ![bakkot](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/bakkot/32/22_2.png) [@bakkot](https://es.discourse.group/u/bakkot)\
**Post date:** [December 8, 2023, 6:47pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/8 "2023-12-08T18:47:25Z")

</div>

You can if you want to have a more stable place for the suggestion to live than this thread, but it's not strictly necessary. The next step is to find a TC39 delegate who wants to champion it. I can't volunteer myself; I have a bunch of other stuff I want to work through and can't realistically take on more.

---

<div class="post-metadata">

**Author:** ![michael](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/michael/32/11_2.png) [@michael](https://es.discourse.group/u/michael)\
**Post date:** [December 11, 2023, 4:35pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/9 "2023-12-11T16:35:04Z")

</div>

Personally, I don't feel that these helpers are sufficiently motivated. As mentioned in the OP, this is a _really_ simple abstraction over `reduce`. I don't think it's at all burdensome to just use `reduce` for these use cases.

---

<div class="post-metadata">

**Author:** ![theScottyJam](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/thescottyjam/32/616_2.png) [@theScottyJam](https://es.discourse.group/u/theScottyJam)\
**Post date:** [December 12, 2023, 5:17am UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/10 "2023-12-12T05:17:38Z")

</div>

I'm realizing that having a `.sortBy()` function would get us most of the way there. We take an iterator, and we sort it using the callback function. The callback is in charge of mapping each item to a "rank". The "rank" can be anything that's sortable by "\<", such as a number or string. In other words, I'm talking about a function that's similar to [Python's sorted function, when you use its key parameter](https://docs.python.org/3/library/functions.html#sorted).

So, something like this:

```javascript
var people = [
  {name: "Adam", age: 15},
  {name: "John", age: 40},
  {name: "Lisa", age: 23}
];

// Find min
var theYoungest = people.values().sorted((a, b) => b.age - a.age).take(1)[0]; // {name: "Adam", age: 15}
// Find max
var theOldest = people.values().sorted((a, b) => a.age - b.age).take(1)[0]; // {name: "John", age: 40}

```

(Anytime I use JavaScript's array.sort() function, I find myself always missing the conciseness of Python's `sorted()` - it's really nice to just use a one-line lambda to describe how you want to sort something, as opposed to a three-pronged conditional)

Thinking further - if we had a proper `.sortBy()` function of some sort, maybe people would actually start using that to shuffle an array as opposed to the buggy `array.sort(() => Math.random() > 0.5))` that I've unfortunetally seen get used way too often. (i.e. instead it could be `array.values().sortBy(() => Math.random())`)

---

<div class="post-metadata">

**Author:** ![ljharb](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/ljharb/32/8_2.png) [@ljharb](https://es.discourse.group/u/ljharb)\
**Post date:** [December 12, 2023, 5:28am UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/11 "2023-12-12T05:28:20Z")

</div>

how can you sort an iterator?

---

<div class="post-metadata">

**Author:** ![theScottyJam](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/thescottyjam/32/616_2.png) [@theScottyJam](https://es.discourse.group/u/theScottyJam)\
**Post date:** [December 12, 2023, 6:12am UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/12 "2023-12-12T06:12:00Z")

</div>

A "sorted()" function was listed in the [iterator helpers](https://github.com/tc39/proposal-iterator-helpers) proposal as prior art that both Python and npm itertools had. Having a sort function for an iterator would require consuming the entire iterator up-front, but it doesn't require you to do the entire sort up-front - only enough to yield each item that's needed on-demand.

So, doing an iterator.sort().take(1) on an iterator that yields n items would be an `O(n)` operation, as opposed to the usual - what is it, `O(n log(n))`?

---

<div class="post-metadata">

**Author:** ![ducin](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/ducin/32/1949_2.png) [@ducin](https://es.discourse.group/u/ducin)\
**Post date:** [December 12, 2023, 8:50am UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/13 "2023-12-12T08:50:20Z")

</div>

Honestly I don't think `sort` is a good alternative here, as you need to sort the entire collection just to get the maximum/minimum element. This is so much unnecessary work.

---

<div class="post-metadata">

**Author:** ![theScottyJam](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/thescottyjam/32/616_2.png) [@theScottyJam](https://es.discourse.group/u/theScottyJam)\
**Post date:** [December 12, 2023, 4:06pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/14 "2023-12-12T16:06:50Z")

</div>

It's not actually any more work. Since it's an iterator method and it returns an iterator, it can be implemented in a lazy fashion. If after sorting you do "take(1)", it only has to do enough sorting to figure out what the first item would be. It doesn't have to figure out the sorted position of any more entries unless you do further "take()"s. Hence why I was saying it is O(n) if used with a "take(1)". Just like how the proposed min/max functions are O(n)

---

<div class="post-metadata">

**Author:** ![ljharb](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/ljharb/32/8_2.png) [@ljharb](https://es.discourse.group/u/ljharb)\
**Post date:** [December 12, 2023, 4:19pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/15 "2023-12-12T16:19:11Z")

</div>

That doesn’t make any sense to me; if the item that should sort first is at the end of the iterator, i shouldn’t be able to see any items until i see that last one.

---

<div class="post-metadata">

**Author:** ![ducin](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/ducin/32/1949_2.png) [@ducin](https://es.discourse.group/u/ducin)\
**Post date:** [December 12, 2023, 4:27pm UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/16 "2023-12-12T16:27:02Z")

</div>

It doesn't make sense to me either.

A take from a different perspective:

- `.sort().take(1)` it could be treated as "all sorted so far"
- but that would have to **store all items** , _ **sorted** _, as the iterator progresses - and this is the additional work.  
How can you sort lazily without storing the data?

---

<div class="post-metadata">

**Author:** ![theScottyJam](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/thescottyjam/32/616_2.png) [@theScottyJam](https://es.discourse.group/u/theScottyJam)\
**Post date:** [December 13, 2023, 4:39am UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/17 "2023-12-13T04:39:59Z")

</div>

Ok - it depends on what we mean by "work".

You have to consume the entire iterator and store it in memory for a sort to work. So, it takes more _memory_. I was interpreting "work" as "number of operations", and they both would have the same big-O if you're taking just one item.

If what I'm proposing is still not clear, perhaps let me provide an example implementation:

```javascript
/** Swaps array[index1] with array[index2] if the former is smaller than the latter. */
function sortPairInPlace(array, index1, index2, deriveRank) {
  if (deriveRank(array[index1]) < deriveRank(array[index2])) {
    [array[index1], array[index2]] = [array[index2], array[index1]];
  }
}

const Iterator = Object.getPrototypeOf(Object.getPrototypeOf([].values()))

// A smarter implementation could cache responses of deriveRank()
// so we don't have to do repeated calls.
Iterator.sortBy = function * (deriveRank) {
  // Consume the iterator and store its contents in the "items" array
  // Looks for the smallest item as it does so.
  const items = [];
  while (true) {
    const { value, done } = this.next();
    if (done) break;
    items.push(value);
    if (items.length >= 2) {
      sortPairInPlace(items, items.length - 2, items.length - 1, deriveRank);
    }
  }

  if (items.length === 0) {
    return;
  }
  yield items.pop();

  // Continues to lazily sort and yield results as needed.
  while (items.length >= 2) {
    for (let i = 0; i < items.length - 1; i++) {
      sortPairInPlace(items, i, i + 1, deriveRank);
    }
    yield items.pop();
  }

  yield items.pop();
}

// A quick-and-dirty polyfill for take()
Iterator.take = function (count) {
  const items = [];
  for (let i = 0; i < count; i++) {
    const { value, done } = this.next();
    if (done) break;
    items.push(value);
  }
  return items;
};

const data = [
  'abc',
  'abcdefghi',
  'a',
  'abcde',
];

// Logs out 'a'
console.log(data.values().sortBy(string => string.length).take(1));
// Logs out 'abcdefghi'
console.log(data.values().sortBy(string => -string.length).take(1));

```

So, no, you don't have to pre-sort the entire array to make this work. You can sort as you `.take()`, lazily.

---

<div class="post-metadata">

**Author:** ![aclaymore](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/aclaymore/32/501_2.png) [@aclaymore](https://es.discourse.group/u/aclaymore)\
**Post date:** [December 13, 2023, 5:17am UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/18 "2023-12-13T05:17:56Z")

</div>

This is why it's important to mention both time and space when talking about big O. Two things bring O(n) time are quite different if one is O(1) space and the other is O(n).

FWIW that implementation of sortBy looks like O(n) time only in the best case of `.take(1)`, if the iterator was fully consumed it would be `O(n^2)` as always starts the bubbling from the start of the remaining items.

---

<div class="post-metadata">

**Author:** ![theScottyJam](https://yyz2.discourse-cdn.com/free1/user_avatar/es.discourse.group/thescottyjam/32/616_2.png) [@theScottyJam](https://es.discourse.group/u/theScottyJam)\
**Post date:** [December 13, 2023, 11:56am UTC](https://es.discourse.group/t/iterator-prototype-findmin-iterator-prototype-findmax-methods/1859/19 "2023-12-13T11:56:28Z")

</div>

This is true, I don't know why I was thinking the overall big-o would be the same if the whole thing got consumed. Though there's still ways to fix that - e.g. if I stored the consumed iterator in a heap instead of an array, you would get O(n log n) execution time if you consume the whole iterator (a.k.a. a [heap sort](https://en.m.wikipedia.org/wiki/Heapsort)).

But it does still require the memory overhead. And even though it has a comparable big-o, it is still doing a lot of overhead compared to simply searching an array for the max value.