Re: return first element in list with certain property

[Emanuel Berg]

Drew Adams wrote:

> You see only one message for each element
> tested because your predicate is called only
> once per element.

Yes, isn't that completely natural?

> `cl-find-if' is implemented by first calling
> `cl-position', which uses your predicate.
> And then, once a satisfactory element is
> found, it calls `elt' to traverse the list
> again, to obtain that element.

By "traverse" you mean go from the first
element, to the second, and so on, until the
element is found (or the list ends)?

Or do you mean the entire thing is gone thru
just like one would traverse a rock or...
a traverse? But that doesn't make any sense WRT
searching (as opposed to logistics)?

If both `cl-position' and `elt' do this
lineary, i.e. if this is the list

    (0 ... n)

and the sought-after element has index e for
(0 <= e <= n) then the worst-case for both are
n, so combined 2n.

However for this

  (cl-dolist (e test-list)
    (when (> e 1) (cl-return e) ))

the worst-case is n! So both are linear, but,
interestingly, the explicit iteration is twice
as fast! I just wrote in another thread

    Using the primitive list-searching
    functions ‘memq’, ‘member’, ‘assq’, or
    ‘assoc’ is even faster than explicit
    iteration. It can be worth rearranging
    a data structure so that one of these
    primitive search functions can be used. [1]

OK, so `cl-find-if' isn't mentioned or even
a primitive, however it sure looks better than
the `cl-dolist' above. But it isn't!

So why does it use `etl'?

[1] (info "(elisp) Compilation Tips")

-- 
underground experts united
http://user.it.uu.se/~embe8573