[Guile-commits] 01/10: srfi-1: Rewrite 'find' in Scheme.

[Ludovic Courtès]

civodul pushed a commit to branch master
in repository guile.

commit 0360843acee98f26598d8f77eda880a03ea3be93
Author: Ludovic Courtès <ludo@gnu.org>
AuthorDate: Wed Jun 17 16:59:50 2020 +0200

    srfi-1: Rewrite 'find' in Scheme.
    
    This halves the wall-clock time of:
    
      guile -c '(use-modules (srfi srfi-1)) (define lst (make-list 100000000 
1)) (find zero? lst)'
    
    and yields an 18% speedup on:
    
      guile -c '(use-modules (srfi srfi-1)) (define lst (make-list 100000000 
1)) (find (lambda (x) (= 2 x)) lst)'
    
    * libguile/srfi-1.c (scm_srfi1_find): Remove.
    * libguile/srfi-1.h (scm_srfi1_find): Likewise.
    * module/srfi/srfi-1.scm (find): New procedure.
    * doc/ref/srfi-modules.texi (SRFI-1 Searching): Adjust docstring.
---
 doc/ref/srfi-modules.texi |  4 ++--
 libguile/srfi-1.c         | 25 +------------------------
 libguile/srfi-1.h         |  3 +--
 module/srfi/srfi-1.scm    | 13 ++++++++++++-
 4 files changed, 16 insertions(+), 29 deletions(-)

diff --git a/doc/ref/srfi-modules.texi b/doc/ref/srfi-modules.texi
index 9de8396..2e66baf 100644
--- a/doc/ref/srfi-modules.texi
+++ b/doc/ref/srfi-modules.texi
@@ -1,6 +1,6 @@
 @c -*-texinfo-*-
 @c This is part of the GNU Guile Reference Manual.
-@c Copyright (C) 1996, 1997, 2000-2004, 2006, 2007-2014, 2017, 2018, 2019
+@c Copyright (C) 1996, 1997, 2000-2004, 2006, 2007-2014, 2017, 2018, 2019, 2020
 @c   Free Software Foundation, Inc.
 @c See the file guile.texi for copying conditions.
 
@@ -824,7 +824,7 @@ predicate or a comparison object for determining which 
elements are to
 be searched.
 
 @deffn {Scheme Procedure} find pred lst
-Return the first element of @var{lst} which satisfies the predicate
+Return the first element of @var{lst} that satisfies the predicate
 @var{pred} and @code{#f} if no such element is found.
 @end deffn
 
diff --git a/libguile/srfi-1.c b/libguile/srfi-1.c
index ca81293..39291a4 100644
--- a/libguile/srfi-1.c
+++ b/libguile/srfi-1.c
@@ -1,6 +1,6 @@
 /* srfi-1.c --- SRFI-1 procedures for Guile
 
-   Copyright 1995-1997,2000-2003,2005-2006,2008-2011,2013-2014,2018
+   Copyright 1995-1997,2000-2003,2005-2006,2008-2011,2013-2014,2018,2020
      Free Software Foundation, Inc.
 
    This file is part of Guile.
@@ -575,29 +575,6 @@ SCM_DEFINE (scm_srfi1_delete_duplicates_x, 
"delete-duplicates!", 1, 1, 0,
 }
 #undef FUNC_NAME
 
-
-SCM_DEFINE (scm_srfi1_find, "find", 2, 0, 0,
-            (SCM pred, SCM lst),
-           "Return the first element of @var{lst} which satisfies the\n"
-           "predicate @var{pred}, or return @code{#f} if no such element is\n"
-           "found.")
-#define FUNC_NAME s_scm_srfi1_find
-{
-  SCM_VALIDATE_PROC (SCM_ARG1, pred);
-
-  for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
-    {
-      SCM elem = SCM_CAR (lst);
-      if (scm_is_true (scm_call_1 (pred, elem)))
-        return elem;
-    }
-  SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
-
-  return SCM_BOOL_F;
-}
-#undef FUNC_NAME
-
-
 SCM_DEFINE (scm_srfi1_find_tail, "find-tail", 2, 0, 0,
             (SCM pred, SCM lst),
            "Return the first pair of @var{lst} whose @sc{car} satisfies the\n"
diff --git a/libguile/srfi-1.h b/libguile/srfi-1.h
index 82efaef..fa21dc4 100644
--- a/libguile/srfi-1.h
+++ b/libguile/srfi-1.h
@@ -1,5 +1,5 @@
 /* srfi-1.h --- SRFI-1 procedures for Guile
-   Copyright 2002-2003,2005-2006,2010-2011,2018
+   Copyright 2002-2003,2005-2006,2010-2011,2018,2020
      Free Software Foundation, Inc.
 
    This file is part of Guile.
@@ -33,7 +33,6 @@ SCM_INTERNAL SCM scm_srfi1_delete (SCM x, SCM lst, SCM pred);
 SCM_INTERNAL SCM scm_srfi1_delete_x (SCM x, SCM lst, SCM pred);
 SCM_INTERNAL SCM scm_srfi1_delete_duplicates (SCM lst, SCM pred);
 SCM_INTERNAL SCM scm_srfi1_delete_duplicates_x (SCM lst, SCM pred);
-SCM_INTERNAL SCM scm_srfi1_find (SCM pred, SCM lst);
 SCM_INTERNAL SCM scm_srfi1_find_tail (SCM pred, SCM lst);
 SCM_INTERNAL SCM scm_srfi1_length_plus (SCM lst);
 SCM_INTERNAL SCM scm_srfi1_lset_difference_x (SCM equal, SCM lst, SCM rest);
diff --git a/module/srfi/srfi-1.scm b/module/srfi/srfi-1.scm
index c0ee535..e5b28e7 100644
--- a/module/srfi/srfi-1.scm
+++ b/module/srfi/srfi-1.scm
@@ -1,6 +1,6 @@
 ;;; srfi-1.scm --- List Library
 
-;;     Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2009, 2010, 2011, 
2014 Free Software Foundation, Inc.
+;;     Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2009, 2010, 2011, 
2014, 2020 Free Software Foundation, Inc.
 ;;
 ;; This library is free software; you can redistribute it and/or
 ;; modify it under the terms of the GNU Lesser General Public
@@ -720,6 +720,17 @@ the list returned."
 
 ;;; Searching
 
+(define (find pred lst)
+  "Return the first element of @var{lst} that satisfies the predicate
+@var{pred}, or return @code{#f} if no such element is found."
+  (check-arg procedure? pred find)
+  (let loop ((lst lst))
+    (and (not (null? lst))
+         (let ((head (car lst)))
+           (if (pred head)
+               head
+               (loop (cdr lst)))))))
+
 (define (take-while pred ls)
   "Return a new list which is the longest initial prefix of LS whose
 elements all satisfy the predicate PRED."