deno_std
deno_std copied to clipboard
denoland
tracking: support iterables in `@std/collections` APIs
Following on from #4671, it seems there are APIs within @std/collections that could support Iterables rather than just arrays. From a quick scan, these symbols might be able to be tweaked to support iterables:
- [x]
chunk() - [ ]
dropLastWhile() - [ ]
dropWhile() - [ ]
intersect() - [x]
sample() - [ ]
slidingWindows() - [ ]
sortBy() - [ ]
takeLastWhile() - [x]
takeWhile() - [x]
withoutAll()
See #3390 for an example of how with was done for groupBy().
A larger change to consider. Should collections use generators? This would be breaking change.
Generators give lazy evaluation, memory efficiency, and sometimes better performance
Example:
function* takeWhile<T>(
iterable: Iterable<T>,
predicate: (el: T) => boolean,
): Generator<T> {
for (const element of iterable) {
console.log(`takeWhile(): ${element}`);
if (!predicate(element)) {
break;
}
yield element;
}
}
function* map<T, U>(
iterable: Iterable<T>,
transform: (el: T) => U,
): Generator<U> {
for (const element of iterable) {
console.log(`map(): ${element}`);
yield transform(element);
}
}
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const result = takeWhile(map(arr, (n) => n * 100), n => n < 500)
console.log([...result])
I think we should stick to the current approach unless the performance benefits are sufficient. We'd have to measurements before coming to that decision.
The move to iterables means that generators that never return are valid arguments.
function* counter() {
let i = 0;
while (true) {
yield i++;
}
}
Many of these functions would hang
Examples:
takeWhile(counter(), v === 0) // predicate will never be true
chunk(counter(), 10)
dropLastWhile(counter, v => v > 30)
dropWhile(counter, v => v === 0) // predicate will never be true
Here are some options:
- Don't handle the case, onus is on the user to know the generator is infinite. Likely case is throwing an
Uncaught RangeError: Invalid array lengthwhen the result array is too long - Catch the error and rethrow?
- Have a max iterations option available
@iuioiua Would you like to assign this to me, I am happy to commit myself to completing all of these changes
Went with Option 1 Don't handle the case where generators are infinite, onus is on the user to know this
