New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Enhanced Hoa\Iterator API #55

Open
Hywan opened this Issue Feb 14, 2017 · 5 comments

Comments

@Hywan
Copy link
Member

Hywan commented Feb 14, 2017

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:

@Hywan Hywan added this to the Roadmap for 2017 milestone Feb 14, 2017

@Hywan Hywan self-assigned this Feb 15, 2017

@Hywan Hywan added the enhancement label Feb 15, 2017

@Hywan

This comment has been minimized.

Copy link
Member

Hywan commented Feb 21, 2017

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 comment has been minimized.

Copy link
Contributor

mathroc commented Feb 21, 2017

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

This comment has been minimized.

Copy link
Member

Hywan commented Feb 21, 2017

@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

This comment has been minimized.

Copy link
Contributor

mathroc commented Feb 21, 2017

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

This comment has been minimized.

Copy link
Member

Hywan commented Feb 22, 2017

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

@Hywan Hywan referenced this issue Aug 17, 2017

Open

steps for next version - bc break #74

0 of 5 tasks complete
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment