help-gnu-emacs
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: return first element in list with certain property


From: Drew Adams
Subject: RE: return first element in list with certain property
Date: Mon, 20 Nov 2017 12:12:13 -0800 (PST)

>> cl-find-if
>
> That's it 100%

BTW, I haven't run any tests, but the `cl-find' code, which
is used also by functions such as `cl-find-if', apparently
traverses the list twice: Once when it calls `cl-position'
and a second time when it calls `elt'.

 (defun cl-find (cl-item cl-seq &rest cl-keys)
  (let ((cl-pos (apply 'cl-position cl-item cl-seq cl-keys)))
    (and cl-pos (elt cl-seq cl-pos))))

`cl-position' does this for a list - it cdrs down list CL-P:

(let ((cl-p (nthcdr cl-start cl-seq)))
  (or cl-end (setq cl-end 8000000))
      (let ((cl-res nil))
        (while (and cl-p (< cl-start cl-end)
                    (or (not cl-res) cl-from-end))
          (if (cl--check-test cl-item (car cl-p))
              (setq cl-res cl-start))
          (setq cl-p (cdr cl-p) cl-start (1+ cl-start)))
        cl-res))

Checking the C source for `elt' called on a list (admittedly,
somewhat old C source code, which is all I have at hand), it
does, in effect, (car (nthcdr n list)).  It cdrs down LIST.

Someone might want to profile the difference, for a long list
whose first occurrence for the sought item is near the end of
the list.  Maybe compare, for example, the use of `cl-find-if'
with something simple that traverses the list only once:

(catch '>1
  (dolist (x xs nil) (when (> x 1) (throw '>1 x))))

The idiom of traversing a list only once, throwing to a
`catch', is a pretty good one to learn, I think.  It's
straightforward and transparent, doing just what it says.

Granted, it doesn't shout "Return the first element > 1."

And it's a little more verbose than using a higher
abstraction such as `cl-find-if'.  Anyway, compare the
length of the code above with these - a difference, but
not huge:

(seq-find (apply-partially #'< 1) xs)
(seq-find (lambda (x) (> x 1)) xs)
(cl-find-if (lambda (x) (> x 1)) xs)
(cl-loop for x in xs when (> x 1) return x)
(cl-some (lambda (x) (and (> x 1) x)) xs)

Dunno whether the other functions, besides `cl-find-if',
traverse the list more than once.

Maybe the code defining `cl-find' should be tweaked to
avoid two traversals?  `cl-position' traverses only once,
and so does `elt'.  Maybe getting the position in the list
and then cdring down the list again to that position is
not the smartest way to do `cl-find-if' on a list.



reply via email to

[Prev in Thread] Current Thread [Next in Thread]