Enhanced Hoa\Iterator API

[Hywan]

Hello fellow @hoaproject/hoackers and users!

This RFC aims at enhancing the Hoa\Iterator API.

Introduction

PHP has a lot of iterators, but the API for a daily usage is quite limited from my point of view. Other languages, like Rust, define nice and powerful API (see Trait std::iter::Iterator).

Goals

Let's start by an example:

$hasEven = false;

foreach ($data as $datum) {
    if (0 === $item % 2) {
        $hasEven = true;

        break;
    }
}

can be rewritten:

$hasEven = (new Hoa\Iterator\Map($data))->any(function ($item) { return 0 === $item % 2; })

With the PHP RFC about short function notation, we will have something like:

$hasEven = (new Hoa\Iterator\Map($data))->any($item => 0 === $item % 2);

The former is harder to read and to understand, and it is much more error-prone. Moreover, this is harder to chain with another operations, like a filter or a map just before having the any.

Goals are:

1. Less error-prone,
2. Easier to read and to write,
3. Avoid iterator invalidations as most as possible,
4. Allow safe iterator mutation if needed,
5. Uniform and simple API to replace most of the (our) foreach loops,
6. Better performances than foreach.

Vocabulary

This is important to agree on a vocabulary. An iterator iterates over a collection of items.

In the case of PHP, the items are heterogeneous, i.e. they can have different types. This is defined by the collection type.

Proposed API

Basis:

• current(): Option<mixed> to get the current item (see #56 for Option),
• key(): Option<int> to get the current key of the item (see #56 for Option),
• next(): void to move the internal pointer to the next item,
• rewind(): void to rewind the iterator,
• valid(): bool to check if the current internal pointer is valid or not.

In a perfect world, next would be defined as next(): Option<mixed>, and thus valid could be dropped, but let's fit in the current PHP API.

More:

• count(): int to count the number of items, iterates over all the collection if necessary, i.e. consumes the iterator if necessary,
• last(): Option<mixed> to get the last item, consumes the iterator if necessary, restore the internal pointer,
• nth(): Option<mixed>' to get the nth item, can be an alias to offsetGetbut it implies to implement theArrayAccessinterface, and thus to implementoffsetSet, offsetUnsetandoffsetIsset` methods, and we don't want them,
• chain(Iterator): Iterator to append one iterator to another one, produce a new iterator (this is equivalent to Hoa\Iterator\Append),
• zip(Iterator): Iterator to zip to iterators, produce a new iterator where items are a pair of item from both iterators (this is equivalent to Hoa\Iterator\Multiple); when either iterator reachs its end, it will stop,
• map(Callable): Iterator to transform an iterator into another one, i.e. takes a callable and creates an iterator which calls that callable on each element,
• filter(Callable): Iterator to produce another iterators with items satisfying the callable predicate,
• peekable(): Iterator to get an iterator with the peek(): Option<mixed> method (this is equivalent to Hoa\Iterator\Lookahead),
• buffer(int): Iterator to get an iterator with the previous method (this is equivalent to Hoa\Iterator\Buffer),
• skipWhile(Callable): Iterator to skip all items that satisfy the predicate; once the predicate has returned false at least once, then all others items are yielded normally,
• takeWhile(Callable): Iterator to yield all items that satisfy the predicate; once the predicate has returned false at least once, then all other items are ignored,
• skip(int): Iterator to skip the first n items,
• take(int): Iterator to take the first n items and ignored the others,
• flatMap(Callable): Iterator not very clear yet (should we restrict it to some types? to flatten only on iterator),
• inspect(Callable): Iterator works like tee,
• collect(): Collection transforms an iterator into a collection,
• partition(Callable): pair of Iterators partition an iterator into two iterators: The former where all items satisfy the callable, the second for the other items,
• fold(mixed $init, Callable): mixed apply a callable on each item of the iterator and produce a single value, the accumulator is initialised to the value of $init,
• all(Callable): bool check that all items match the predicate,
• any(Callable): bool check that at least one item matches the predicate,
• find(Callable): Option<mixed> search the first item matching the predicate,
• position(Callable): Option<mixed> search the first item matching the predicate and returns in index,
• rightPosition(Callable): Option<mixed> same as position but searches from the right (the end) of the iterator,
• max(): Option<mixed> to get the maximum value of an iterator, will be based on the spaceship operator,
• min(): Option<mixed> to get the minimum value of an iterator, same mechanism than max,
• maxBy(Callable): Option<mixed> to get maximum value of an iterator based on the callable to compare two values, return the right most value in the collection in case of equality,
• minBy(Callable): Option<mixed> same as maxBy but for the minimum value,
• reverse(): Iterator reverse the iterator,
• cloned(): Iterator create an iterator from an iterator where each item is cloned from the former,
• cycle(): Iterator to repeat the same iterator again and again and again (this is equivalent to Hoa\Iterator\Infinite),
• repeat(int): Iterator to repeat the same iterator n times (this is equivalent to Hoa\Iterator\Repeater),
• sum(): int to sum all elements in an iterator, this is a shortcut to fold with a special callable, 0 if the collection is empty,
• product(): int to multiply all elements in an iterator, this is a shortcut to fold with a special callable, 1 if the collection is empty,

Bounded vs. unbounded iterators

What to do if the iterator is unbounded?

Producer-consumer model

Put in other words, all the API is lazy. It means that:

$iterator->map(…)->filter(…)->collect();

Will not be equivalent to:

$mapped = $iterator->map(…);
$filtered = new Iterator\…($mapped)->filter(…);
$out = new Iterator\…($filtered)->collect();

But it will be much more like this:

foreach ($iterator as $item) {
    $mappedItem = $mapCallable($item);

    if (true !== $filterCallable($mappedItem)) {
        continue;
    }

    $out[] = $mappedItem;
}

So, when we describe the map API as map(Callable): Iterator, this is wrong. It would more accurate to describe it as map(Callable): Map, where Map is a special Iterator.

A nice effect is that:

$iterator->map(…)->filter(…);

will execute nothing. Why, Because map and filter are producers, not consumers. However, count, collect, fold etc. are consumers.

Another name for this pattern is the “adapter pattern”.

Outro

Most of the API can re-use the work we did with existing Hoa\Iterator classes. Most of them are extending PHP SPL. However, we can re-implement everything from scratch with generators, thanks to generator delegation. That's my strategy.

Thoughts?

Edits:

• Fix API based on https://github.com/hoaproject/Central/issues/55#issuecomment-281342682.

[Hywan]

Note: This is somewhat very similar to nikic/iter cc @nikic if you have a feedback about your library (would you do something differently for instance? any performance issues?).

Main difference is that we are going to be full object instead of being functional.

[mathroc]

this seems nice, it's always a PITA to come working with iterator in php back from rust (or javascript with lodash)

• find(Callable): mixed search the first item matching the predicate,
• position(Callable): mixed search the first item matching the predicate and returns in index,
• rightPosition(Callable): mixed same as position but searches from the right (the end) of the iterator,
• max(): int to get the maximum value of an iterator, will be based on the spaceship operator,
• min(): int to get the minimum value of an iterator, same mechanism than max, sum(): int to sum all elements in an iterator, this is a shortcut to fold with a special callable, product(): int to multiply all elements in an iterator, this is a shortcut to fold with a special callable,

shouldn't those return Options ? (not really sure about the last 2)

[Hywan]

@mathroc I guess sum and product must return 0 if the collection is empty. But max and min must return an option, correct! Them for find & co. I am fixing it. Thanks for the detailed look!

[mathroc]

I'm ok for sum returning 0, however I'm not sure about product, I think it should return 1 (the identity element)

so that $a->product() * $b->product() === $a->chain($b)->product() is always true (as it is for sum)

[Hywan]

You're correct! I reckon I should sleep more…