Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:116967
User-Agent: Cyrus-JMAP/3.5.0-alpha0-4585-ga9d9773056-fm-20220113.001-ga9d97730
Mime-Version: 1.0
Message-ID: <1c9e79d5-fd79-45a8-9c77-4228d770062d@www.fastmail.com>
In-Reply-To: 
 <DM6PR14MB41556131E6A9D7812854AA75F9269@DM6PR14MB4155.namprd14.prod.outlook.com>
References: 
 <DM6PR07MB66185E23B803C5E5BF858B30F9DF9@DM6PR07MB6618.namprd07.prod.outlook.com>
 <DM6PR14MB41556131E6A9D7812854AA75F9269@DM6PR14MB4155.namprd14.prod.outlook.com>
Date: Tue, 01 Feb 2022 10:26:42 -0600
To: "php internals" <internals@lists.php.net>
Content-Type: text/plain
Subject: Re: [PHP-DEV] Re: Adding `final class Deque` to PHP
From: larry@garfieldtech.com ("Larry Garfield")

On Tue, Feb 1, 2022, at 8:46 AM, tyson andre wrote:


> I plan to start voting on https://wiki.php.net/rfc/deque on Friday, 
> February 4th.
>
> Several changes have been made to https://wiki.php.net/rfc/deque#changelog
> after the feedback in https://externals.io/message/116100
>
> - The class is now named `Collections\Deque`
> - The api documentation in https://wiki.php.net/rfc/deque#proposal was 
> expanded for methods.
> - Benchmarks were updated.
> - Like other standard datastructures, iteration over the deque is now 
> over the original object (instead of creating a copy), 
>   and mutating the deque will be reflected in `$iterator->current()` 
> (and moving the end with push()/pop() will affect where iteration ends).
> - Iteration will account for calls to shift/unshift moving the start of 
> the deque.
>   the offsets will be corrected and values won't be skipped or iterated 
> over multiple times.
>   (no matter how many iterators were created by `Deque->getIterator()`)
>   See https://wiki.php.net/rfc/deque#iteration_behavior
> - The get()/set() methods were removed, after feedback in 
> https://externals.io/message/116100#116214
>
> A WebAssembly demo is available at 
> https://tysonandre.github.io/php-rfc-demo/deque/

Request:

push() and unshift() currently return void.  That's not helpful.  It would be vastly more useful if they both returned $this.  Not as much for chaining, but more so that you can add a value to a queue and pass it as an argument to another call (often recursive, but not necessarily) in a single operation.  

Example: I was doing last year's Advent of Code in functional PHP, and had a stack walker that looked like this:

function parse(string $line, $pos = 0, array $stack = []): Result|string
{
    $next = $line[$pos] ?? null;
    $head = $stack[0] ?? null;

    return match ($next) {
        // Opening brace, push an "expected" onto the stack.
        '{' => parse($line, $pos + 1, ['}', ...$stack]),
        '<' => parse($line, $pos + 1, ['>', ...$stack]),
        '(' => parse($line, $pos + 1, [')', ...$stack]),
        '[' => parse($line, $pos + 1, [']', ...$stack]),
        '}', '>', ')', ']' => $next === $head ? parse($line, $pos + 1, array_slice($stack, 1)) : $next,
        null => count($stack) ? Result::Incomplete : Result::OK,
    };
}

The interesting part is the ['<', ...$stack], to pass on a modified version of an array-as-stack.  That's of course annoyingly slow with arrays right now, and a Deque would be better, but only if it could be "modified and passed" like that.  If not, it would be incompatible with single-expression usages (match statements, short lambdas, etc.)

Returning $this would resolve that, I think.  (Making it return a new, immutable copy of the Deque would be even nicer, but I realize that's probably not an argument I'm going to win at this point on this RFC.)

Also, typo:

"By introducing a data structure (Deque) that's even faster and more memory usage than an array for use as a double-ended queue, even more applications would benefit from it. "

I think you mean "less memory usage", or possibly "more memory efficient", or something like that.

--Larry Garfield