Re: Re: Adding `final class Deque` to PHP

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 èltž;úS¬žün‡e > Ê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