Merge pull request #946 from ekaitz-zarraga/faster-concatenate!

Reduce iterations in concatenate!

1 files changed, 10 insertions, 7 deletions

diff --git a/lib/srfi/1/misc.scm b/lib/srfi/1/misc.scm
index 843ed19d..e5a7f59e 100644
--- a/lib/srfi/1/misc.scm
+++ b/lib/srfi/1/misc.scm
@@ -15,13 +15,16 @@
 (define (concatenate! lists)
   (if (null? lists)
       '()
-      (fold (lambda (el acc)
-                (cond
-                  ((null? acc) el)
-                  ((null? el) acc)
-                  (else (begin (set-cdr! (last-pair acc) el) acc))))
-              (car lists)
-              (cdr lists))))
+      (let loop ((acc    '())
+                 (prev   '())
+                 (rem    lists))
+          (cond
+            ((null? rem) acc)
+            ((null? acc) (let ((cur (car rem))) (loop cur cur (cdr rem))))
+            ((null? (car rem)) (loop acc prev (cdr rem)))
+            (else (let ((cur (car rem)))
+                    (set-cdr! (last-pair prev) cur)
+                    (loop acc cur (cdr rem))))))))
 
 (define (append-reverse rev tail)
   (if (null? rev) tail (append-reverse (cdr rev) (cons (car rev) tail))))