# Any interest in a list type?

- Thread: https://externals.io/message/109760
- Original archive: https://news-web.php.net/php.internals/109760
- Started by Matthew Brown on 2020-04-21T19:00:03+00:00
- Messages: 23
- RFC: Add array_is_list(array $array): bool (Implemented (PHP 8.1)) — https://externals.io/rfc/is_list.md
- RFC: final class Vector (Inactive) — https://externals.io/rfc/vector.md
- Reply by email to internals@lists.php.net
- More for agents: search with https://externals.io/search.md?q={query} · RFCs at https://externals.io/rfc.md · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt

---

## #109760 — Matthew Brown — 2020-04-21T19:00:03+00:00

URL: https://externals.io/message/109760#109760

Before I create an RFC or attempt a reference implementation, is there any
interest in adding (and then obviously supporting in perpetuity) a list
type?

The first line of PHP's documentation for "array" states: "An array in PHP
is actually an ordered map". There are some optimisations that make arrays
with ordered integer keys faster, but I'd be interested in a separate type
dedicated to *sequential* integer keys. Such a type would presumably
consume a little less memory.

Why "list" and not "vec" or similar? "list" is also a reserved word – I'm
imagining that you'd construct a list like

$l = list["a", "b", "c"];

I imagine such a "list" type would be a subtype of "array" – everywhere
that array was accepted, a list would be also, and it would have the same
copy-on-write behaviour.

If people are interested in having that type, there's a question of what to
do with

$some_list["a"] = 5;

Would you convert the $some_list to an array, or throw an exception?
Converting to an array would seem the more PHP-like thing to do.

Similarly, the behaviour of

$some_list[$key_out_of_current_range] = 5

would be a matter of debate too – would that turn $some_list into an array,
or would it fill up any preceding entries in the array with null?

What other questions are there? Is a "list" type even a good fit for PHP,
given most of its users seem pretty content with the current
swiss-army-knife array type?

Best wishes,

Matt

---

## #109761 — Andrea Faulds — 2020-04-21T19:49:49+00:00

URL: https://externals.io/message/109760#109761 · In reply to: #109760

Hi,

Matthew Brown wrote:
> I imagine such a "list" type would be a subtype of "array" – everywhere
> that array was accepted, a list would be also, and it would have the same
> copy-on-write behaviour.

IIRC with the modern implementation of arrays in the Zend Engine, you 
can check that an array has no string keys, has keys in the right order, 
and possibly even that they are all numbered 0 through (count($arr) - 1) 
without gaps. I recall someone previously suggesting (not formally 
proposing IIRC) we could have a standard library is_ function to check 
these, but it didn't go anywhere. Anyway, someone who has touched the 
code more recently than me would have to confirm (please do!), but I 
think we could cheaply add a `list` type declaration that just checks 
for an array fulfilling some or all of these criteria.

Making a special kind of array _value_ that must stay a “list” sounds 
more problematic… I think without automatic casting back and forth from 
regular “arrays” it might play badly with existing code, but then there 
would be no point…

Thanks for the interesting idea!
Andrea

---

## #109763 — Marcio Almada — 2020-04-21T20:17:04+00:00

URL: https://externals.io/message/109760#109763 · In reply to: #109760

Hello!

>
> Before I create an RFC or attempt a reference implementation, is there any
> interest in adding (and then obviously supporting in perpetuity) a list
> type?
>
> The first line of PHP's documentation for "array" states: "An array in PHP
> is actually an ordered map". There are some optimisations that make arrays
> with ordered integer keys faster, but I'd be interested in a separate type
> dedicated to *sequential* integer keys. Such a type would presumably
> consume a little less memory.
>
> Why "list" and not "vec" or similar? "list" is also a reserved word – I'm
> imagining that you'd construct a list like
>
> $l = list["a", "b", "c"];
>
> I imagine such a "list" type would be a subtype of "array" – everywhere
> that array was accepted, a list would be also, and it would have the same
> copy-on-write behaviour.
>
> If people are interested in having that type, there's a question of what to
> do with
>
> $some_list["a"] = 5;
>
> Would you convert the $some_list to an array, or throw an exception?
> Converting to an array would seem the more PHP-like thing to do.
>
> Similarly, the behaviour of
>
> $some_list[$key_out_of_current_range] = 5
>
> would be a matter of debate too – would that turn $some_list into an array,
> or would it fill up any preceding entries in the array with null?
>
> What other questions are there? Is a "list" type even a good fit for PHP,
> given most of its users seem pretty content with the current
> swiss-army-knife array type?
>
> Best wishes,
>
> Matt

First, thanks for taking your time to bring some ideas.

One of the biggest problems with PHP arrays IMMO is that they are
suited to everything therefore
optimized for nothing. At least a contiguous list type, AKA real
array, could give us some opportunities.

But AFAIK adding another real type (not just a pseudo type) on the
engine comes with a cost. So,
it would make no sense to add a list type and incur in the same type
juggling array already has.

I'm not sure if I'm in favor of having this new type, but certainly
not in favor of allowing the list to
become an hash map by key assignments. One could always `$array =
[...$list]` or even `(array) $list`
explicitly, perhaps.

Ty,
Márcio

---

## #109764 — Matthew Brown — 2020-04-21T21:06:21+00:00

URL: https://externals.io/message/109760#109764

>
> Making a special kind of array _value_ that must stay a “list” sounds
> more problematic… I think without automatic casting back and forth from
> regular “arrays” it might play badly with existing code, but then there
> would be no point…
>

Makes sense – then conversion from lists to arrays would happen the same way

$some_int += $some_float

converts $some_int to a float.

_If_ there was a list type then it would make sense to add a corresponding
is_list runtime check, and users would be able to typehint their functions
as returning a list, and get an error if the function actually returned a
(non-list) array.

---

## #109765 — Andrea Faulds — 2020-04-21T21:52:48+00:00

URL: https://externals.io/message/109760#109765 · In reply to: #109761

Hello again,

Andrea Faulds wrote:
> Hi,
> 
> Matthew Brown wrote:
> > […]
> 
> IIRC with the modern implementation of arrays in the Zend Engine, you 
> can check that an array has no string keys, has keys in the right order, 
> and possibly even that they are all numbered 0 through (count($arr) - 1) 
> without gaps.

Sorry, what I meant to say was “you can check [quickly in O(1) time] 
that an array has no string keys [etc]”. This is because of the Zend 
Engine's “packed arrays”.

Thanks,
Andrea

---

## #109766 — Max Semenik — 2020-04-21T22:42:03+00:00

URL: https://externals.io/message/109760#109766 · In reply to: #109760

On Tue, Apr 21, 2020 at 10:00 PM Matthew Brown <matthewmatthew@gmail.com>
wrote:

> Why "list" and not "vec" or similar? "list" is also a reserved word – I'm
> imagining that you'd construct a list like
>
> $l = list["a", "b", "c"];
>

"List" usually means linked list, "vector" would be much clearer and
consistent with many other languages


> I imagine such a "list" type would be a subtype of "array" – everywhere
> that array was accepted, a list would be also, and it would have the same
> copy-on-write behaviour.
>
> If people are interested in having that type, there's a question of what to
> do with
>
> $some_list["a"] = 5;
>
> Would you convert the $some_list to an array, or throw an exception?
> Converting to an array would seem the more PHP-like thing to do.
>
> Similarly, the behaviour of
>
> $some_list[$key_out_of_current_range] = 5
>
> would be a matter of debate too – would that turn $some_list into an array,
> or would it fill up any preceding entries in the array with null?
>

I personally would prefer as little implicit magic as possible. Just throw
exceptions instead of allowing people to accidentally shoot themselves on
the foot.

What other questions are there? Is a "list" type even a good fit for PHP,
> given most of its users seem pretty content with the current
> swiss-army-knife array type?


If we're to dream about some bright distant future of data structures, my
dream would be to have a set of structures that make their big O behavior
clear, à la C++ STL or many other languages' standard libraries. Some of
them are already present in SPL, but notably not what you're proposing.
Additionally, it would be wonderful to have generic versions, e.g.
List<int> would not just accept only ints, but would store them internally
as zend_long, avoiding the overhead of zvals.

>
-- 
Best regards,
Max Semenik

---

## #109767 — tyson andre — 2020-04-22T00:18:28+00:00

URL: https://externals.io/message/109760#109767 · In reply to: #109760

Miscellaneous thoughts on this:

- Working to have a vote on https://github.com/php/php-src/pull/4886 might be a good first step, and something I was personally interested in seeing in 8.0-dev.
  However, in the event you can't rule out that is_array($listParam) might not return true in the final implementation you decide on, maybe wait. (you said it'd be a subtype, and it seems like a lot of code would break, so that seems unlikely)
- How would `array_shift()`, array_merge(array, list), array_intersect, etc., `preg_match()`, etc be handled? Would they return lists or arrays?
- I'd really have liked to see data structures such as sets, variable-length vectors, etc. in core natively available as objects (or other types, but objects seemed the most practical).
  Right now, there's php-ds https://www.php.net/manual/en/book.ds.php , but if I wanted to use vec/list in an application/library that was used in a wide variety of places, I'd really rather have something in core. (the drawbacks of using a polyfill would outweigh the performance benefits for a small fraction of adopters)
- If those data types were natively available, maybe opcache and/or the jit could use specialized opcodes to reduce the overhead of offsetGet, etc., if the class was known.
- References to list iyped properties `class X { public list $list; } $x->list = &$localVar; unset($localVar[1]);` may cause problems in implementation details if they're a subtype of arrays.
   Forbidding them in typed properties and limiting the type to params and return types may work.
- Having them limited to param type and return type checks (including some internal global function return types) would be how I'd prefer it (instead of adding a separate type elsewhere)
  PHP already has special handling for iterable/callable.
- Future scope of a list type hint might be to add a deprecation notice for `list ($x, $y) = $array` or `foreach ($x as list($y)) to avoid confusion
  (even though it's currently unambiguous, and that probably will remain unambiguous)

- Tyson

---

## #109777 — Matthew Brown — 2020-04-22T16:01:20+00:00

URL: https://externals.io/message/109760#109777 · In reply to: #109767

Thanks for your comments!

> How would `array_shift()`, array_merge(array, list) ... be handled? Would
they return lists or arrays?

I think they would return lists where appropriate – Psalm & Phan already
infer some of that behaviour, adding runtime support would be an
undertaking, but not impossible.

> References to list typed properties may cause problems...

I don't see this as being any different to how integer typed properties
work under float addition (as below) – we'd just not allow any modification
that violated the list type.

class X { public int $i = 0; }
$x = new X();
$x->i += 2.3;
echo $x->i; // 2, not 2.3

With declare(strict_types=1), the above is a fatal error – the same would
be true for operations that violated list typed properties

> Having them limited to param type and return type checks

Would be happy for that compromise if the above proved confusing, or
difficult to implement





> Miscellaneous thoughts on this:
>
> - Working to have a vote on https://github.com/php/php-src/pull/4886
> might be a good first step, and something I was personally interested in
> seeing in 8.0-dev.
>   However, in the event you can't rule out that is_array($listParam) might
> not return true in the final implementation you decide on, maybe wait. (you
> said it'd be a subtype, and it seems like a lot of code would break, so
> that seems unlikely)
> - How would `array_shift()`, array_merge(array, list), array_intersect,
> etc., `preg_match()`, etc be handled? Would they return lists or arrays?
> - I'd really have liked to see data structures such as sets,
> variable-length vectors, etc. in core natively available as objects (or
> other types, but objects seemed the most practical).
>   Right now, there's php-ds https://www.php.net/manual/en/book.ds.php ,
> but if I wanted to use vec/list in an application/library that was used in
> a wide variety of places, I'd really rather have something in core. (the
> drawbacks of using a polyfill would outweigh the performance benefits for a
> small fraction of adopters)
> - If those data types were natively available, maybe opcache and/or the
> jit could use specialized opcodes to reduce the overhead of offsetGet,
> etc., if the class was known.
> - References to list iyped properties `class X { public list $list; }
> $x->list = &$localVar; unset($localVar[1]);` may cause problems in
> implementation details if they're a subtype of arrays.
>    Forbidding them in typed properties and limiting the type to params and
> return types may work.
> - Having them limited to param type and return type checks (including some
> internal global function return types) would be how I'd prefer it (instead
> of adding a separate type elsewhere)
>   PHP already has special handling for iterable/callable.
> - Future scope of a list type hint might be to add a deprecation notice
> for `list ($x, $y) = $array` or `foreach ($x as list($y)) to avoid confusion
>   (even though it's currently unambiguous, and that probably will remain
> unambiguous)
>
> - Tyson

---

## #109781 — Larry Garfield — 2020-04-22T17:28:00+00:00

URL: https://externals.io/message/109760#109781 · In reply to: #109760

> Before I create an RFC or attempt a reference implementation, is there any
> interest in adding (and then obviously supporting in perpetuity) a list
> type?
> 
> The first line of PHP's documentation for "array" states: "An array in PHP
> is actually an ordered map". There are some optimisations that make arrays
> with ordered integer keys faster, but I'd be interested in a separate type
> dedicated to *sequential* integer keys. Such a type would presumably
> consume a little less memory.
> 
> Why "list" and not "vec" or similar? "list" is also a reserved word – I'm
> imagining that you'd construct a list like
> 
> $l = list["a", "b", "c"];
> 
> I imagine such a "list" type would be a subtype of "array" – everywhere
> that array was accepted, a list would be also, and it would have the same
> copy-on-write behaviour.
> 
> If people are interested in having that type, there's a question of what to
> do with
> 
> $some_list["a"] = 5;
> 
> Would you convert the $some_list to an array, or throw an exception?
> Converting to an array would seem the more PHP-like thing to do.
> 
> Similarly, the behaviour of
> 
> $some_list[$key_out_of_current_range] = 5
> 
> would be a matter of debate too – would that turn $some_list into an array,
> or would it fill up any preceding entries in the array with null?
> 
> What other questions are there? Is a "list" type even a good fit for PHP,
> given most of its users seem pretty content with the current
> swiss-army-knife array type?

Most users don't realize that PHP's arrays-not-really-arrays have caused millions of dollars in security breaches in the past. :-)  They're dangerous and to be avoided whenever possible.

I'm very open to a list/sequence type, but as others have noted there's a whole crapload of details to sort out to make it viable.  In particular:

* Is it an effective subclass of array?  IMO, no.  It should have absolutely no auto-conversion to/from an array whatsoever of any kind, period.  Keep them as separate as possible.

* Should it even have random-access indexes?  Honestly I'd say no; Just support adding, removing, and iteration and generate the indexes on the fly when iterating if necessary.

* Should they pass like arrays or like objects?  Many questions here.

* Should they be mutable or immutable?  I could argue for either one effectively, I think, though I'd honestly favor immutable.

* Are they iterable?  Presumably, but does that have any weird implications for iterables that implicitly assume there are keys?  How's that work?

* Does it make sense to add them without type enforcement via generics?  Lists + Generics would be lovely, but as we've seen Generics are Hard(tm) and Not Imminent(tm).  But would adding them now make a generic version harder in the future?  (I've no idea.)

* Besides add/remove/iterate, what other baked-in functionality should they have?  Eg, can they be mapped/filtered/reduced?  It would really suck to revisit lists and not fix that disconnect in the API.  (Insert me talking about comprehensions and stuff here.)  Ideally this would happen as part of a larger review of how collections work at various levels, which are currently highly clunky.

Those are all solvable problems (and I've likely forgotten several), but they would have to be thought through extensively before an implementation could be viable.

--Larry Garfield

---

## #109788 — Matthew Brown — 2020-04-22T18:49:17+00:00

URL: https://externals.io/message/109760#109788 · In reply to: #109781

> Is it an effective subtype of array?

I was thinking it should be (with the auto-conversion mentioned above), but
I can see a compelling case to not have the auto-conversion when
manipulating – while it would bloat the stdlib a little (we'd need a whole
bunch of list_* functions) the separation would simplify things a lot (e.g.
list_filter would return a list with sequential keys, whereas array_filter
returns an array with possibly non-sequential keys)

And then you could cast between the two like "(list) $some_array" (which
would preserve order but remove keys) and "(array) $some_list" as
necessary. There could even be some automatic list <-> array casting when
calling functions not in strict_types mode.

> Should they pass like arrays or like objects

Definitely like arrays – I want them to be a drop-in-replacement for people
who currently use arrays in places lists are more appropriate.

> Should they be mutable or immutable

Definitely mutable, like arrays are

> Are they iterable

Yes, the keys are sequential integers

> Does it make sense to add them without type enforcement via generics

Absolutely – this shouldn't be tied to generics landing (which I'd imagine
is a PHP 9 feature at this point, whereas this could be a PHP 8.x feature).

> can they be mapped/filtered/reduced

Absolutely – I think we'd have list_map, list_filter, list_reduce functions
to provide that functionality.



> 
> > […]
> any
> > […]
> PHP
> > […]
> arrays
> > […]
> type
> > […]
> to
> > […]
> array,
> > […]
>
> Most users don't realize that PHP's arrays-not-really-arrays have caused
> millions of dollars in security breaches in the past. :-)  They're
> dangerous and to be avoided whenever possible.
>
> I'm very open to a list/sequence type, but as others have noted there's a
> whole crapload of details to sort out to make it viable.  In particular:
>
> * Is it an effective subclass of array?  IMO, no.  It should have
> absolutely no auto-conversion to/from an array whatsoever of any kind,
> period.  Keep them as separate as possible.
>
> * Should it even have random-access indexes?  Honestly I'd say no; Just
> support adding, removing, and iteration and generate the indexes on the fly
> when iterating if necessary.
>
> * Should they pass like arrays or like objects?  Many questions here.
>
> * Should they be mutable or immutable?  I could argue for either one
> effectively, I think, though I'd honestly favor immutable.
>
> * Are they iterable?  Presumably, but does that have any weird
> implications for iterables that implicitly assume there are keys?  How's
> that work?
>
> * Does it make sense to add them without type enforcement via generics?
> Lists + Generics would be lovely, but as we've seen Generics are Hard(tm)
> and Not Imminent(tm).  But would adding them now make a generic version
> harder in the future?  (I've no idea.)
>
> * Besides add/remove/iterate, what other baked-in functionality should
> they have?  Eg, can they be mapped/filtered/reduced?  It would really suck
> to revisit lists and not fix that disconnect in the API.  (Insert me
> talking about comprehensions and stuff here.)  Ideally this would happen as
> part of a larger review of how collections work at various levels, which
> are currently highly clunky.
>
> Those are all solvable problems (and I've likely forgotten several), but
> they would have to be thought through extensively before an implementation
> could be viable.
>
> --Larry Garfield

---

## #109789 — Larry Garfield — 2020-04-22T19:00:46+00:00

URL: https://externals.io/message/109760#109789 · In reply to: #109788

> > […]
> 
> I was thinking it should be (with the auto-conversion mentioned above), but
> I can see a compelling case to not have the auto-conversion when
> manipulating – while it would bloat the stdlib a little (we'd need a whole
> bunch of list_* functions) the separation would simplify things a lot (e.g.
> list_filter would return a list with sequential keys, whereas array_filter
> returns an array with possibly non-sequential keys)
> 
> And then you could cast between the two like "(list) $some_array" (which
> would preserve order but remove keys) and "(array) $some_list" as
> necessary. There could even be some automatic list <-> array casting when
> calling functions not in strict_types mode.
> 
> > […]
> 
> Definitely like arrays – I want them to be a drop-in-replacement for people
> who currently use arrays in places lists are more appropriate.
> 
> > […]
> 
> Definitely mutable, like arrays are

That has a long list of possible issues with it relating to spooky action at a distance, depending on the passing semantics.  In some languages lists are immutable, and with PHP's copy-on-write it may make more sense to just go immutable.

> > […]
> 
> Yes, the keys are sequential integers
> 
> > […]
> 
> Absolutely – this shouldn't be tied to generics landing (which I'd imagine
> is a PHP 9 feature at this point, whereas this could be a PHP 8.x feature).
> 
> > […]
> 
> Absolutely – I think we'd have list_map, list_filter, list_reduce functions
> to provide that functionality.

Why duplicate all of them?  Rather, map/filter/reduce need to be recast to work on any iterable, which would then include lists.  Or, if lists are an object they would be methods on the object.

Hence my point.  Lists would only make sense if we're also rethinking how collections work generally, for which we're already overdue.  Just tossing them in as yet-another-different-thing would make the situation worse, not better.

--Larry Garfield

---

## #109790 — Matthew Brown — 2020-04-22T20:44:58+00:00

URL: https://externals.io/message/109760#109790 · In reply to: #109789

> map/filter/reduce need to be recast to work on any iterable, which would
then include lists
> Lists would only make sense if we're also rethinking how collections work
generally

I disagree – I think the most successful PHP language additions have been
those that allow PHP developers to improve their code without having to
think too hard – for example, property, return and param types can be added
to existing code without changing its behaviour at runtime, as long as the
added types align with actual behaviour.

If list types work in a wholly different fashion to arrays, they won't be a
drop-in-replacement, they won't feel familiar to the average PHP developer,
and I imagine few people would update existing code to use them, because
it'd be too risky.



> 
> > […]
> but
> > […]
> whole
> > […]
> (e.g.
> > […]
> array_filter
> > […]
> people
> > […]
>
> That has a long list of possible issues with it relating to spooky action
> at a distance, depending on the passing semantics.  In some languages lists
> are immutable, and with PHP's copy-on-write it may make more sense to just
> go immutable.
>
> > […]
> imagine
> > […]
> feature).
> > […]
> functions
> > […]
>
> Why duplicate all of them?  Rather, map/filter/reduce need to be recast to
> work on any iterable, which would then include lists.  Or, if lists are an
> object they would be methods on the object.
>
> Hence my point.  Lists would only make sense if we're also rethinking how
> collections work generally, for which we're already overdue.  Just tossing
> them in as yet-another-different-thing would make the situation worse, not
> better.
>
> --Larry Garfield

---

## #109792 — Larry Garfield — 2020-04-22T22:47:08+00:00

URL: https://externals.io/message/109760#109792 · In reply to: #109790

> > […]
> then include lists
> > […]
> generally
> 
> I disagree – I think the most successful PHP language additions have been
> those that allow PHP developers to improve their code without having to
> think too hard – for example, property, return and param types can be added
> to existing code without changing its behaviour at runtime, as long as the
> added types align with actual behaviour.
> 
> If list types work in a wholly different fashion to arrays, they won't be a
> drop-in-replacement, they won't feel familiar to the average PHP developer,
> and I imagine few people would update existing code to use them, because
> it'd be too risky.

1) Please don't top-post.

2) I don't mean "make them as unlike arrays as possible".  I mean "think through the implications of having a *third* type of iterable; what other functions would be affected?  Should we reconsider how map/filter/reduce work generally instead of just throwing a bunch more random functions at it?  What are the knock-on effects?  Should we also be adding a dedicated dictionary type as well?  Why or why not?"

This is the *design* process for a language, and it's important.  "Let's just throw a numeric-only list type into the pool and see what happens" is a very bad idea.  Stepping back to reconsider how collections work generally, and how we can improve them in a graceful way that leads to a clean end-state, would be very valuable.

--Larry Garfield

---

## #109793 — Andrea Faulds — 2020-04-22T22:51:04+00:00

URL: https://externals.io/message/109760#109793 · In reply to: #109765

Hello again everyone,

Andrea Faulds wrote:
> Hello again,
> 
> Andrea Faulds wrote:
> > […]
> 
> Sorry, what I meant to say was “you can check [quickly in O(1) time] 
> that an array has no string keys [etc]”. This is because of the Zend 
> Engine's “packed arrays”.
> 
> Thanks,
> Andrea

Since it's pretty simple, I decided to write a proof-of-concept 
implementation of such a check. For simplicity's sake I haven't 
implemented a type declaration right now, just an is_list() function, 
but it could easily be extended to one. The implementation can be found 
at 
https://github.com/php/php-src/compare/master...hikari-no-yume:is_list 
(and here's a direct commit link to the current version as of this 
writing for the sake of historical record: 
https://github.com/php/php-src/commit/f6fc94fae8d97743d23d276d66071dac1d240a05)

As I hoped, it can in several common cases give a `TRUE` result in O(1):

   $ sapi/cli/php -r 'var_dump(is_list([]));'
   No elements
   bool(true)

   $ sapi/cli/php -r 'var_dump(is_list([3, 2, 1]));'
   Packed and without holes!
   bool(true)

   $ sapi/cli/php -r '$x = [3,2,1]; sort($x); var_dump(is_list($x));'
   Packed and without holes!
   bool(true)

   $ sapi/cli/php -r '$x = [1,2,3,4]; unset($x[3]); var_dump($x, 
is_list($x));'
   Packed and without holes!
   bool(true)

Unfortunately, it turns out that it can't always be fast! :(

The problem is that while an array can have the “packed” and “without 
holes” flags IFF it has no string keys and all keys are in order without 
gaps, that does not mean the reverse is true: that if an array lacks 
those flags, it must have string keys, out-of-order keys or gaps. The 
result is there are several cases where we must foreach over the array 
to check if it's a “list”, which unfortunately means as bad as O(n) time 
complexity depending on the array content.

For example we can't be sure if it has string keys without foreaching 
over it:

   $ sapi/cli/php -r 'var_dump(is_list(["foo"=>"bar","bar"=>"baz"]));'
   Foreaching
   Hit string key
   bool(false)

I want to say that this used to be possible in the common case without 
foreaching due to some flag on the HashTable, I think Dmitry added that. 
But it might have been a proposed patch that didn't get in, or it was 
reverted.

If this is check will only be used as a type declaration on 
functions/return-types/properties and not as a general-purpose is_list() 
function, we might decide that the O(n) worst-case is acceptable so long 
as it only affects cases where the array is not a valid list, i.e. when 
a TypeError would be thrown, because in production code, values being 
type-checked should only rarely have the wrong type, so it should only 
cause slowness during debugging. It is not like we are trying to make 
throwing type errors fast… at least so I assume?

Unfortunately, this O(n) worst-case applies even to some valid lists. 
For example:

   $ sapi/cli/php -r '$x = [0=>1,2=>3,1=>2]; unset($x[2]); var_dump($x, 
is_list($x));'
   Foreaching
   No irregularities encountered, true by slowest path
   array(2) {
     [0]=>
     int(1)
     [1]=>
     int(2)
   }
   bool(true)

   $ sapi/cli/php -r '$x = [1,2,3]; $x["foo"] = "bar"; unset($x["foo"]); 
var_dump(is_list($x));'
   Foreaching
   No irregularities encountered, true by slowest path
   bool(true)

Maybe these kinds of cases are uncommon enough that we could deem the 
slowness acceptable. We could also use list type-checks as an 
opportunity to optimise valid lists that aren't already “packed” to be 
“packed” behind-the-scenes, speeding up subsequent checks. Also, it may 
be the case that the Zend Engine's hashtable implementation could be 
changed slightly to allow O(1) checks in more cases.

Anyway, I hope this was interesting and can help inform discussion and 
perhaps provide inspiration!

Thanks,
Andrea

---

## #109794 — Dusk — 2020-04-22T22:53:10+00:00

URL: https://externals.io/message/109760#109794 · In reply to: #109760

> I recall someone previously suggesting (not formally proposing IIRC) we could have a standard library is_ function to check these, but it didn't go anywhere.

That would be me, and I had a draft implementation for it:

https://github.com/php/php-src/pull/4886

My proposal was more oriented towards adding a function to test whether an array was list-like (all keys are sequential integers), though, not adding it as a formal type.

---

## #109795 — tyson andre — 2020-04-22T23:07:27+00:00

URL: https://externals.io/message/109760#109795

Hi Andrea,

> Since it's pretty simple, I decided to write a proof-of-concept
> implementation of such a check. For simplicity's sake I haven't
> implemented a type declaration right now, just an is_list() function,
> but it could easily be extended to one. The implementation can be found
> at https://github.com/php/php-src/compare/master...hikari-no-yume:is_list

I wrote in a different response to the original email:

> Working to have a vote on https://github.com/php/php-src/pull/4886 might be a good first step, and something I was personally interested in seeing in 8.0-dev.

I thought I mentioned that there was a PR that implemented is_list() in another email in that thread, but it turns out I was mistaken - I just mentioned the URL. Sorry.

That PR "Add is_list function" (https://github.com/php/php-src/pull/4886) copies the is_list implementation that the JSON extension uses internally for efficient serialization of lists.

I'm glad to see the interest in support for is_list(), list types, or working on potential implementations.

Thanks,
- Tyson

---

## #109796 — Matthew Brown — 2020-04-23T04:32:03+00:00

URL: https://externals.io/message/109760#109796 · In reply to: #109795

> For simplicity's sake I haven't
> implemented a type declaration right now, just an is_list() function,
> but it could easily be extended to one

This is a crucial question – should is_list function like
is_numeric($some_string), where is_list just tells you about the keys in
the array at a given point in the program, or should it function like
is_int, where it tells you about the type. I lean towards the latter (which
would make the implementation of is_list simpler, but would complicate
everything else.

---

## #109797 — Matthew Brown — 2020-04-23T04:35:47+00:00

URL: https://externals.io/message/109760#109797

>
> Anyway, I hope this was interesting and can help inform discussion and
> perhaps provide inspiration!
>

This was very useful, and it makes me feel more strongly that list should
be an entirely separate type so that checking for packed keys is rarely
necessary.

---

## #109798 — Matthew Brown — 2020-04-23T05:02:29+00:00

URL: https://externals.io/message/109760#109798 · In reply to: #109792

> This is the *design* process for a language, and it's important...
Stepping back to reconsider how collections work generally, and how we can
improve them in a graceful way that leads to a clean end-state, would be
very valuable.

Though you have much more experience with internals than I do, I think that
building a consensus around a bold new vision for PHP collections would be
a near-Sisyphean task.

Adding a list/vector type would be a much smaller, more easily definable
task – it was one of the first new types that Hack added, and by all
accounts they're pretty happy with that decision.

> Should we also be adding a dedicated dictionary type as well?

Maybe? I think there'd be less to gain from a performance standpoint
though, so I didn't want to lump that in with any list proposal and risk
derailment.

---

## #109799 — Levi Morrison via internals — 2020-04-23T05:33:14+00:00

URL: https://externals.io/message/109760#109799 · In reply to: #109798

>
> > […]
> Stepping back to reconsider how collections work generally, and how we can
> improve them in a graceful way that leads to a clean end-state, would be
> very valuable.
>
> Though you have much more experience with internals than I do, I think that
> building a consensus around a bold new vision for PHP collections would be
> a near-Sisyphean task.
>
> Adding a list/vector type would be a much smaller, more easily definable
> task – it was one of the first new types that Hack added, and by all
> accounts they're pretty happy with that decision.

IIRC, they switched from object semantics to value semantics (like PHP
arrays). Can someone more knowledgeable confirm?

>
> > […]
>
> Maybe? I think there'd be less to gain from a performance standpoint
> though, so I didn't want to lump that in with any list proposal and risk
> derailment.

---

## #109812 — Matthew Brown — 2020-04-23T14:16:14+00:00

URL: https://externals.io/message/109760#109812 · In reply to: #109799

>
> IIRC, they switched from object semantics to value semantics (like PHP
> arrays). Can someone more knowledgeable confirm?
>

Yes, sorry – Hack introduced the vec type (with value semantics) in 2016
after they'd experimented first with Vector (object semantics). Use of
Vector is now discouraged.

Details here: https://github.com/facebook/hhvm/issues/6451

FB/Hack appears to be in the multi-year process of moving all PHP arrays to
one of [vec/dict/keyset]. That's likely not an option for PHP itself, but
having the _option_ of a vec equivalent (in this proposal "list") would
make sense, I think.

---

## #109814 — Levi Morrison via internals — 2020-04-23T14:19:32+00:00

URL: https://externals.io/message/109760#109814 · In reply to: #109812

> > […]
>
>
> Yes, sorry – Hack introduced the vec type (with value semantics) in 2016 after they'd experimented first with Vector (object semantics). Use of Vector is now discouraged.
>
> Details here: https://github.com/facebook/hhvm/issues/6451
>
> FB/Hack appears to be in the multi-year process of moving all PHP arrays to one of [vec/dict/keyset]. That's likely not an option for PHP itself, but having the _option_ of a vec equivalent (in this proposal "list") would make sense, I think.

Yeah, I already figured that value semantics would be preferred for
this. From the engine perspective, we probably wouldn't want to
special case these 3 types and would probably want to figure out some
way for at least internal classes to have value semantics. Any
contrarian opinions there, especially from main php-src contributors
like Nikita and Dmitry?

---

## #109816 — Larry Garfield — 2020-04-23T15:58:08+00:00

URL: https://externals.io/message/109760#109816 · In reply to: #109798

> > […]
> Stepping back to reconsider how collections work generally, and how we can
> improve them in a graceful way that leads to a clean end-state, would be
> very valuable.
> 
> Though you have much more experience with internals than I do, I think that
> building a consensus around a bold new vision for PHP collections would be
> a near-Sisyphean task.

Disclosure: I've been around the list for over a decade and talked a lot, but the recent pipe RFC is my first core patch. I'm still one of the little people around here. :-)  Though I have successfully engaged in Sisyphean tasks before.  (GoPHP5, Drupal 8, FIG, etc.)

> Adding a list/vector type would be a much smaller, more easily definable
> task – it was one of the first new types that Hack added, and by all
> accounts they're pretty happy with that decision.

I think we may be talking past each other.  I don't mean "rewrite all the things."  Just taking the time to think through "if we have a list type, generators, and array/dicts, what should all of the ancillary bits around them be to make them as smooth as possible?"  Viz, how do we NOT have array_map, list_map, and generator_map as 3 separate functions, because that would be awful.  Are list generators and array/dict generators different things or the same thing, or...?  Would comprehensions make sense as part of such a plan?  (IMO yes.)  But then, do comprehensions produce lists or dicts or...?  

That's the sort of knock-on effects that should be thought through before we commit code, because in the long run it would reduce the amount of code to commit (and the amount of WTF for users).

--Larry Garfield
