From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Drew Adams Newsgroups: gmane.emacs.help Subject: RE: return first element in list with certain property Date: Mon, 20 Nov 2017 12:12:13 -0800 (PST) Message-ID: References: <8660a60zjn.fsf@zoho.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: blaine.gmane.org 1511209611 23071 195.159.176.226 (20 Nov 2017 20:26:51 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 20 Nov 2017 20:26:51 +0000 (UTC) To: Philipp Stephani , help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Mon Nov 20 21:26:46 2017 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eGseT-0005gO-Ir for geh-help-gnu-emacs@m.gmane.org; Mon, 20 Nov 2017 21:26:45 +0100 Original-Received: from localhost ([::1]:59577 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eGsea-0004n9-Jq for geh-help-gnu-emacs@m.gmane.org; Mon, 20 Nov 2017 15:26:52 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:35892) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eGsQa-0001YZ-Dn for help-gnu-emacs@gnu.org; Mon, 20 Nov 2017 15:12:25 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eGsQW-0007zl-30 for help-gnu-emacs@gnu.org; Mon, 20 Nov 2017 15:12:24 -0500 Original-Received: from aserp1040.oracle.com ([141.146.126.69]:50546) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1eGsQV-0007yl-Te for help-gnu-emacs@gnu.org; Mon, 20 Nov 2017 15:12:20 -0500 Original-Received: from userv0022.oracle.com (userv0022.oracle.com [156.151.31.74]) by aserp1040.oracle.com (Sentrion-MTA-4.3.2/Sentrion-MTA-4.3.2) with ESMTP id vAKKCFSl009638 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 20 Nov 2017 20:12:15 GMT Original-Received: from aserv0121.oracle.com (aserv0121.oracle.com [141.146.126.235]) by userv0022.oracle.com (8.14.4/8.14.4) with ESMTP id vAKKCEId032245 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 20 Nov 2017 20:12:15 GMT Original-Received: from abhmp0016.oracle.com (abhmp0016.oracle.com [141.146.116.22]) by aserv0121.oracle.com (8.14.4/8.13.8) with ESMTP id vAKKCEAv016358; Mon, 20 Nov 2017 20:12:14 GMT In-Reply-To: X-Priority: 3 X-Mailer: Oracle Beehive Extensions for Outlook 2.0.1.9.1 (1003210) [OL 16.0.4615.0 (x86)] X-Source-IP: userv0022.oracle.com [156.151.31.74] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.4.x-2.6.x [generic] [fuzzy] X-Received-From: 141.146.126.69 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Original-Sender: "help-gnu-emacs" Xref: news.gmane.org gmane.emacs.help:115009 Archived-At: >> 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.