Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:113066
MIME-Version: 1.0
References: <CAFMT4Np4JCB+cSEdEWKXWXUX83fq0kt+P6F-F=LvfktpjLf=3w@mail.gmail.com>
 <CAF+90c_g9+4UEsBshZ-G_KUTgYbJZNAS597JDD-FrfZPwTsW4g@mail.gmail.com> <CAFMT4NranPYqX5239EOBP5AH5o85FnYno-AAo67YBffbDBe=hw@mail.gmail.com>
In-Reply-To: <CAFMT4NranPYqX5239EOBP5AH5o85FnYno-AAo67YBffbDBe=hw@mail.gmail.com>
Date: Wed, 3 Feb 2021 17:28:54 +0100
Message-ID: <CAF+90c88M8NZd=ji0b-HSTh7onaM-tYy8h4MsrL6XKnb-wofeA@mail.gmail.com>
To: Levi Morrison <levim@php.net>
Cc: internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="0000000000003d7e9205ba71161f"
Subject: Re: [PHP-DEV] Proposal: Add ReverseArrayIterator and
 ForwardArrayIterator to SPL
From: nikita.ppv@gmail.com (Nikita Popov)

--0000000000003d7e9205ba71161f
Content-Type: text/plain; charset="UTF-8"

On Wed, Feb 3, 2021 at 5:09 PM Levi Morrison <levim@php.net> wrote:

> On Wed, Feb 3, 2021 at 8:50 AM Nikita Popov <nikita.ppv@gmail.com> wrote:
> >
> > On Wed, Feb 3, 2021 at 4:38 PM Levi Morrison <levim@php.net> wrote:
> >>
> >> Hello, everyone!
> >>
> >> This proposal adds two new classes to the SPL:
> >>
> >>   - `Spl\ReverseArrayIterator`. It iterates over an array in reverse
> >> order. It does not duplicate the array.
> >>   - `Spl\ForwardArrayIterator`. It iterates over an array in forward
> >> (normal) order. It does not duplicate the array.
> >>
> >> They both implement Countable which returns the `count()` of the
> >> array. The [PR][1] has some examples and discusses why I am proposing
> >> `ForwardArrayIterator` when there is already `ArrayIterator`, the
> >> short of which is for performance. There are timing numbers in [one of
> >> the comments][2].
> >>
> >> When it comes time to vote I may merge this into another RFC with
> >> [`CachedIterable` by Tyson Andre][3], which I recommend readers also
> >> take a look at. Whether we team up for the RFC vote or not, I wanted
> >> to get this out there for discussion and review.
> >>
> >>   [1]: https://github.com/php/php-src/pull/6535
> >>   [2]: https://github.com/php/php-src/pull/6535#issuecomment-769179450
> >>   [3]: https://github.com/php/php-src/pull/6655
> >
> >
> > Hey Levi,
> >
> > I like the general idea of having an "ArrayIterator but sane".
> >
> > That said, I don't think that the ReverseArrayIterator +
> ForwardArrayIterator pair of iterators approaches this problem correctly.
> There are plenty of iterators that could be run in reverse, and I think it
> would be silly to create two classes for each of them. E.g. if we introduce
> an ObjectPropertyIterator, should there be both
> ForwardObjectPropertyIterator and ReverseObjectPropertyIterator? I don't
> think so.
> >
> > I think the correct abstraction for bidirectional iterators is to
> introduce an interface
> >
> > // Or "ReversibleIterator"
> > interface BidrectionalIterator extends Iterator {
> >     public function prev(): void;
> >     public function end(): void;
> > }
> >
> > and then a class along the lines of:
> >
> > class ReverseIterator implements BidirectionalIterator {
> >     public function __construct(private BidirectionalIterator $iter) {}
> >
> >     public function next() { $this->iter->prev(); }
> >     // etc.
> > }
> >
> > This would replace "new ReverseArrayIterator($array)" with "new
> ReverseIterator(new ArrayIterator($array))", but in a way that is general,
> and composes.
> >
> > Regards,
> > Nikita
>
> I wrote an implementation of this idea two years ago:
>
> https://github.com/php/php-src/compare/master...morrisonlevi:BidirectionalArrayIterator
>
> It's fine for arrays, but not all structures that you can iterate
> through forward or reverse. For instance, tree structures can be
> traversed forward or reverse, but bidirectionally is far more
> difficult (and I did not find any pre-existing solutions in this
> space, btw). I do have repositories with tree structures, so it's not
> just theoretical.
>

I don't really view this as a problem, in the sense that you always have
the option of implementing two iterators. But for most cases, if you can
iterate in reverse, you can also iterate bi-directionally.


> Another factor for abandonment was ergonomics. This is not great: `new
> ReverseIterator(new BidirectionalArrayIterator($array))`. It's mildly
> less performant as well, having to create two objects, and then having
> delegation through methods.
>

It is slightly less ergonomic in isolation, but I think it makes more sense
conceptually. Iterating an array in reverse is not exactly common (to the
point that I'm not even sure this is a problem worth solving), so I don't
think it needs to be optimized for minimum characters.

Regards,
Nikita

--0000000000003d7e9205ba71161f--