# [discussion] add array_usearch()

- Thread: https://externals.io/message/72342
- Original archive: https://news-web.php.net/php.internals/72342
- Started by Tjerk Meesters on 2014-02-06T14:38:51+00:00
- Messages: 11
- Reply by email to internals@lists.php.net
- More for agents: search with https://externals.io/search.md?q={query} · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt

---

## #72342 — Tjerk Meesters — 2014-02-06T14:38:51+00:00

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

Hi internals,

To complement `array_search()`, I'm gauging the interest in adding the
following function:

mixed array_usearch(array $haystack, callable $fn, int $flags = 0)

It returns the first array key from a given haystack for which the callback
function returns a truthy value [1] or `false` otherwise. The callback
function receives the array item as its only argument [2].

The flags, described below, can be combined by using a binary or.

[1] the interpretation of the return value can be inverted by using
`ARRAY_USEARCH_INVERT`
[2] the array key is passed as the 2nd argument by using
`ARRAY_USEARCH_USE_KEY`

An implementation of `array_all()` and array_some(), which you may find in
ECMAScript:

 function array_some(array $array, $fn)
 {
   return array_usearch($array, $fn) !== false;
 }

 function array_all(array $array, $fn)
 {
   return array_usearch($array, $fn, ARRAY_USEARCH_INVERT) === false;
 }

Another example:

 echo array_usearch(['a', 'b', 2], 'is_numeric'); // 2

The implementation can be found here:
https://github.com/datibbaw/php-src/compare/master...array-usearch

Let me know your thoughts.


-- 
--
Tjerk

---

## #72344 — Kingsquare.nl - Robin Speekenbrink — 2014-02-06T15:53:21+00:00

URL: https://externals.io/message/72342#72344 · In reply to: #72342

2014-02-06 Tjerk Meesters <tjerk.meesters@gmail.com>:
> Hi internals,
>
> To complement `array_search()`, I'm gauging the interest in adding the
> following function:
>
> mixed array_usearch(array $haystack, callable $fn, int $flags = 0)
>
> It returns the first array key from a given haystack for which the callback
> function returns a truthy value [1] or `false` otherwise. The callback
> function receives the array item as its only argument [2].
>
>

Tjerk,

This feels alot like array_filter.. Do we really want to introduce yet
another way of doing almost the same?

Regards,

Robin Speekenbrink

---

## #72346 — Tjerk Meesters — 2014-02-06T19:55:09+00:00

URL: https://externals.io/message/72342#72346 · In reply to: #72344

Hi Robin,

On Thu, Feb 6, 2014 at 11:53 PM, Kingsquare.nl - Robin Speekenbrink <
robin@kingsquare.nl> wrote:

> 2014-02-06 Tjerk Meesters <tjerk.meesters@gmail.com>:
> > […]
> callback
> > […]
>
> Tjerk,
>
> This feels alot like array_filter.. Do we really want to introduce yet
> another way of doing almost the same?
>

Consider the following examples for finding a value in an array:

array_search($value, $array, true);

current(array_keys($array, $value, true));

key(array_filter($array, function($item) use ($value) {
    return $item === $value;
}));

Perhaps I've overlooked one way, but that's already three ways of doing
something similar; the difference lies in the memory behaviour, the first
being O(1) whereas the other two are O(n).

I initially wanted to extend `array_search()` to support a Closure as the
$needle argument, but that would lead to some BC issues.


>
> Regards,
>
> Robin Speekenbrink
>



-- 
--
Tjerk

---

## #72347 — Chris Wright — 2014-02-06T20:28:19+00:00

URL: https://externals.io/message/72342#72347 · In reply to: #72346

> Consider the following examples for finding a value in an array:
>
> array_search($value, $array, true);
>
> current(array_keys($array, $value, true));
>
> key(array_filter($array, function($item) use ($value) {
>     return $item === $value;
> }));
>
> Perhaps I've overlooked one way, but that's already three ways of doing
> something similar; the difference lies in the memory behaviour, the first
> being O(1) whereas the other two are O(n).

I'm not sure where you got this statement from. `array_search()` is
still O(n) in the worst case (when the needle is not found), which is
the best you can hope for with such an operation. It's true that the
other two are *always* O(n) whereas `array_search()` *could* return
sooner than a complete iteration if the needle is found before the
last element.

My initial reaction to this is one of "ye gods, not another array_*
function", but I wouldn't be against altering the existing
 `array_search()` so that the third parameter is a bitmask of flags, one
of which could indicate that the search should be case insensitive.
This could be done in a BC-compliant manner if the flag that indicates
strict comparisons has a value of 1.

Thanks, Chris

---

## #72355 — Tjerk Meesters — 2014-02-07T00:26:11+00:00

URL: https://externals.io/message/72342#72355 · In reply to: #72347

Hi Chris,




> 
> > […]
>
> I'm not sure where you got this statement from. `array_search()` is
> still O(n) in the worst case (when the needle is not found), which is
> the best you can hope for with such an operation. It's true that the
> other two are *always* O(n) whereas `array_search()` *could* return
> sooner than a complete iteration if the needle is found before the
> last element.
>

I was talking about memory growth, not runtime :)


>
> My initial reaction to this is one of "ye gods, not another array_*
> function", but I wouldn't be against altering the existing
> `array_search()` so that the third parameter is a bitmask of flags, one
> of which could indicate that the search should be case insensitive.
> This could be done in a BC-compliant manner if the flag that indicates
> strict comparisons has a value of 1.
>

I'm not wildly enthusiastic about another magic flags parameter, but it's
an acceptable compromise for me. The slight advantage there is that
`in_array()` would be bestowed upon the ability to take a callback function
as well. Something like:

if (in_array('is_numeric', $array, SEARCH_NEEDLE_IS_CALLBACK)) { ... }




>
> Thanks, Chris
>
> --
> 
> 
>
>


-- 
--
Tjerk

---

## #72362 — Yasuo Ohgaki — 2014-02-07T06:36:34+00:00

URL: https://externals.io/message/72342#72362 · In reply to: #72355

Hi all,

On Fri, Feb 7, 2014 at 9:26 AM, Tjerk Meesters <tjerk.meesters@gmail.com>wrote:

> I'm not wildly enthusiastic about another magic flags parameter, but it's
> an acceptable compromise for me. The slight advantage there is that
> `in_array()` would be bestowed upon the ability to take a callback function
> as well. Something like:
>
> if (in_array('is_numeric', $array, SEARCH_NEEDLE_IS_CALLBACK)) { ... }
>

What we need is 'closure only callback'.
If we have it, then we don't have to worry about string callback functions.

if (in_array(function($elem) {return is_numeric(strstr($elem));}, $array))
{ ... }

Why don't we have 'closure' as signature? It can do more than calling
a function.

bool in_array(closure $callback, array $ary);

Cons would be we cannot search closures in $ary.
Is there any use of searching closure?

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

---

## #72363 — Tjerk Meesters — 2014-02-07T06:54:52+00:00

URL: https://externals.io/message/72342#72363 · In reply to: #72362

Hi,



> Hi all,
>
> On Fri, Feb 7, 2014 at 9:26 AM, Tjerk Meesters <tjerk.meesters@gmail.com>wrote:
>
> > […]
>
> What we need is 'closure only callback'.
> If we have it, then we don't have to worry about string callback functions.
>
> if (in_array(function($elem) {return is_numeric(strstr($elem));}, $array))
> { ... }
>
> Why don't we have 'closure' as signature? It can do more than calling
> a function.
>
> bool in_array(closure $callback, array $ary);
>
> Cons would be we cannot search closures in $ary.
> Is there any use of searching closure?
>

That was my first attempt actually; if the first argument is a closure, use
that as the search callback. A few problems with that:
1) You can't use other types of callback, e.g. string or array.
2) [bc] You can't search through an array of closures.
3) [minor] the $strict argument becomes ambiguous.

The second problem can be mitigated by checking if $strict is given and
`true`, but it becomes rather messy.


> Regards,
>
> --
> Yasuo Ohgaki
> yohgaki@ohgaki.net
>
>


-- 
--
Tjerk

---

## #72365 — Patrick Schaaf — 2014-02-07T07:09:51+00:00

URL: https://externals.io/message/72342#72365 · In reply to: #72363

Hi,

some thoughts on your discussion:

Am 07.02.2014 07:55 schrieb "Tjerk Meesters" <tjerk.meesters@gmail.com>:
>
> That was my first attempt actually; if the first argument is a closure,
use
> that as the search callback. A few problems with that:
> 1) You can't use other types of callback, e.g. string or array.

For that (and possibly other uses), it would be good to have a
cast-to-closure:

$foo = (Closure) 'is_numeric';
$bar = (Closure) [ $that, 'method' ];

That might sometimes even save some work,  when the implementation attempts
to extract the signature of the thing that is to be cast to make a proper
signature for the generated closure. If the callable is then used several
times later (callback in a loop) the callable-as-array-or-string-lookup
would no longer sit in the middle of the loop.

> 2) [bc] You can't search through an array of closures.

That's not good. Could be worked around by using a closure that compares to
the needle closure, but it would still be a BC break.

Code that might be affected would be some kind of registry for lists of
callbacks that, upon insert, wants to check that the thing to be inserted
isn't there already. I wrote something like that two weeks ago,
incidentally :)

In the long run, using an is-closure (not is-callable) vs. is-string branch
in various callback-taking functions, would make for cleaner code, compared
to sprinkling bitmask flag arguments with a DO_IT_CALLBACK_STYLE flag.

best regards
  Patrick

---

## #72412 — Rowan Collins — 2014-02-08T18:22:46+00:00

URL: https://externals.io/message/72342#72412 · In reply to: #72346

> Consider the following examples for finding a value in an array:
>
> array_search($value, $array, true);
>
> current(array_keys($array, $value, true));
>
> key(array_filter($array, function($item) use ($value) {
>      return $item === $value;
> }));
>
> Perhaps I've overlooked one way, but that's already three ways of doing
> something similar; the difference lies in the memory behaviour, the first
> being O(1) whereas the other two are O(n).

I was pondering this, and it occurred to me it could actually be cast as 
an application of `array_reduce()`, except that that function doesn't 
currently provide array keys to the callback function. Assuming a third 
parameter was passed to the callback containing the current key, you 
could define it thus:

function array_usearch($array, $fn) {
     return array_reduce($array, function(&$result, $value, $key) use ( 
$fn ) {
         if ( is_null($result) && $fn($value, $key) ) {
             $result = $key;
         }
     });
}

(The invert flag would make it a little more verbose, but this would be 
enough for parity with `array_filter()` anyway.)

This would presumably have the same memory profile as a dedicated 
implementation (no array needs to be initialised, only the single return 
value), and the same worst-case time performance, but without the 
ability to short-cut once a match has been found.

Incidentally, in your proposal, you mentioned this:

> [2] the array key is passed as the 2nd argument by using
> `ARRAY_USEARCH_USE_KEY`

Is there a particular reason *not* to pass an extra parameter to 
callbacks, even if it's unused?

In the case of an existing function like `array_filter()`, I can see that 
there is a small risk of a BC break if a function was reused as the 
callback that could optionally take an additional parameter, and relied 
on that parameter not being passed in, but that seems like a bit of an 
edge case anyway, and doesn't apply to a brand new function.


Of couse, the proposed function can trivially be implemented with a 
foreach loop as well, even including a short-cut once a match has been 
found:

function array_usearch( $array, $fn ) {
     foreach ( $array as $k => $v ) {
         if ( $fn($k, $v) ) {
             return $k;
         }
     }
     return false;
}

http://codepad.viper-7.com/YM8LSs

Again, I've omitted the ability to invert the matching, but there are 
plenty of efficient ways of adding that.

Regards,

-- 
Rowan Collins
[IMSoP]

---

## #72417 — Tjerk Meesters — 2014-02-09T00:04:30+00:00

URL: https://externals.io/message/72342#72417 · In reply to: #72412

On Sun, Feb 9, 2014 at 2:22 AM, Rowan Collins <rowan.collins@gmail.com>wrote:

> 
>
> > […]
>
> I was pondering this, and it occurred to me it could actually be cast as
> an application of `array_reduce()`, except that that function doesn't
> currently provide array keys to the callback function. Assuming a third
> parameter was passed to the callback containing the current key, you could
> define it thus:
>
> function array_usearch($array, $fn) {
>     return array_reduce($array, function(&$result, $value, $key) use ( $fn
> ) {
>         if ( is_null($result) && $fn($value, $key) ) {
>             $result = $key;
>         }
>     });
> }
>
> (The invert flag would make it a little more verbose, but this would be
> enough for parity with `array_filter()` anyway.)
>
> This would presumably have the same memory profile as a dedicated
> implementation (no array needs to be initialised, only the single return
> value), and the same worst-case time performance, but without the ability
> to short-cut once a match has been found.


> Incidentally, in your proposal, you mentioned this:
>
>
>  [2] the array key is passed as the 2nd argument by using
> > […]
>
> Is there a particular reason *not* to pass an extra parameter to
> callbacks, even if it's unused?
>

Yeah, internal functions don't like extra parameters, e.g.:

  is_numeric('123', 4);

  > Warning: `is_numeric()` expects exactly 1 parameter, 2 given in php shell
code on line 1

This would get in the way when you want to express "give the array key of
the first numeric element".


> In the case of an existing function like `array_filter()`, I can see that
> there is a small risk of a BC break if a function was reused as the
> callback that could optionally take an additional parameter, and relied on
> that parameter not being passed in, but that seems like a bit of an edge
> case anyway, and doesn't apply to a brand new function.
>
>
> Of couse, the proposed function can trivially be implemented with a
> foreach loop as well, even including a short-cut once a match has been
> found:
>
> function array_usearch( $array, $fn ) {
>     foreach ( $array as $k => $v ) {
>         if ( $fn($k, $v) ) {
>             return $k;
>         }
>     }
>     return false;
> }
>

Right; I would personally prefer this over the rather intricate use of
`array_reduce()` ;-) that said, `array_search()` and `in_array()` can also
be easily implemented in this fashion.


>
> http://codepad.viper-7.com/YM8LSs
>
> Again, I've omitted the ability to invert the matching, but there are
> plenty of efficient ways of adding that.
>
> Regards,
>
> --
> Rowan Collins
> [IMSoP]
>
>
>
> --
> 
> 
>
>


-- 
--
Tjerk

---

## #72418 — Rowan Collins — 2014-02-09T02:02:11+00:00

URL: https://externals.io/message/72342#72418 · In reply to: #72417

>
>     Is there a particular reason *not* to pass an extra parameter to
>     callbacks, even if it's unused?
>
>
> Yeah, internal functions don't like extra parameters, e.g.:
>
>   is_numeric('123', 4);
>
> > […]
> shell code on line 1

Ah, yes, I always forget that internal functions behave rather 
differently from user-defined ones when it comes to parameter passing.

:)

-- 
Rowan Collins
[IMSoP]