bug#9883: R6RS fold-left

bug#9883: R6RS fold-left

[Ian Price]

[-- Attachment #1: Type: text/plain, Size: 668 bytes --]


Hi guilers,

According to the R6RS the accumulator should be the first argument of
the combiner[0], not the last as in SRFI 1[1].

I've attached a patch to fix this, and the use of fold-left in
define-record-type.

Currently, it terminates on the first null (as in SRFI 1). If you would
prefer, I can change it to check the lengths of the lists before-hand,
and do the same for fold-right.

Cheers.

0. http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-4.html#node_idx_212
1. http://srfi.schemers.org/srfi-1/srfi-1.html#fold
-- 
Ian Price

"Programming is like pinball. The reward for doing it well is
the opportunity to do it again" - from "The Wizardy Compiled"

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: fold-left fix --]
[-- Type: text/x-patch, Size: 4257 bytes --]

From 31b964c85ba45d72e4ec047e7d0420146a12941c Mon Sep 17 00:00:00 2001
From: Ian Price <ianprice90@googlemail.com>
Date: Wed, 26 Oct 2011 20:24:05 +0100
Subject: [PATCH] Fix R6RS `fold-left'

* module/rnrs/lists.scm (fold-left) : Wrote R6RS compliant
  version with accumulator as first argument to the combiner.

* module/rnrs/records/syntactic.scm (define-record-type): Fix to use
  corrected fold-left.

* test-suite/tests/r6rs-lists.test: Add tests.
---
 module/rnrs/lists.scm             |   12 +++++++++---
 module/rnrs/records/syntactic.scm |    4 ++--
 test-suite/tests/r6rs-lists.test  |   26 ++++++++++++++++++++++++++
 3 files changed, 37 insertions(+), 5 deletions(-)

diff --git a/module/rnrs/lists.scm b/module/rnrs/lists.scm
index 812ce5f..0671e77 100644
--- a/module/rnrs/lists.scm
+++ b/module/rnrs/lists.scm
@@ -22,8 +22,7 @@
 	  remv remq memp member memv memq assp assoc assv assq cons*)
   (import (rnrs base (6))
           (only (guile) filter member memv memq assoc assv assq cons*)
-	  (rename (only (srfi srfi-1) fold 
-			              any 
+	  (rename (only (srfi srfi-1) any 
 				      every 
 				      remove 
 				      member 
@@ -32,7 +31,6 @@
 				      partition
 				      fold-right 
 				      filter-map)
-		  (fold fold-left) 
 		  (any exists) 
 		  (every for-all)
 		  (remove remp)
@@ -40,6 +38,14 @@
 		  (member memp-internal)
 		  (assoc assp-internal)))
 
+  (define (fold-left combine nil list . lists)
+    (define (fold nil lists)
+      (if (exists null? lists)
+          nil
+          (fold (apply combine nil (map car lists))
+                (map cdr lists))))
+    (fold nil (cons list lists)))
+
   (define (remove obj list) (remp (lambda (elt) (equal? obj elt)) list))
   (define (remv obj list) (remp (lambda (elt) (eqv? obj elt)) list))
   (define (remq obj list) (remp (lambda (elt) (eq? obj elt)) list))
diff --git a/module/rnrs/records/syntactic.scm b/module/rnrs/records/syntactic.scm
index a497b90..bde6f93 100644
--- a/module/rnrs/records/syntactic.scm
+++ b/module/rnrs/records/syntactic.scm
@@ -134,13 +134,13 @@
               (let* ((fields (if (unspecified? _fields) '() _fields))
                      (field-names (list->vector (map car fields)))
                      (field-accessors
-                      (fold-left (lambda (x c lst)
+                      (fold-left (lambda (lst x c)
                                    (cons #`(define #,(cadr x)
                                              (record-accessor record-name #,c))
                                          lst))
                                  '() fields (sequence (length fields))))
                      (field-mutators
-                      (fold-left (lambda (x c lst)
+                      (fold-left (lambda (lst x c)
                                    (if (caddr x)
                                        (cons #`(define #,(caddr x)
                                                  (record-mutator record-name
diff --git a/test-suite/tests/r6rs-lists.test b/test-suite/tests/r6rs-lists.test
index ba645ed..030091f 100644
--- a/test-suite/tests/r6rs-lists.test
+++ b/test-suite/tests/r6rs-lists.test
@@ -30,3 +30,29 @@
     (let ((d '((3 a) (1 b) (4 c))))
       (equal? (assp even? d) '(4 c)))))
 
+(with-test-prefix "fold-left"
+  (pass-if "fold-left sum"
+    (equal? (fold-left + 0 '(1 2 3 4 5))
+            15))
+  (pass-if "fold-left reverse"
+    (equal? (fold-left (lambda (a e) (cons e a)) '() '(1 2 3 4 5))
+            '(5 4 3 2 1)))
+  (pass-if "fold-left max-length"
+    (equal? (fold-left (lambda (max-len s)
+                         (max max-len (string-length s)))
+                       0
+                       '("longest" "long" "longer"))
+            7))
+  (pass-if "fold-left with-cons"
+    (equal? (fold-left cons '(q) '(a b c))
+            '((((q) . a) . b) . c)))
+  (pass-if "fold-left sum-multiple"
+    (equal? (fold-left + 0 '(1 2 3) '(4 5 6))
+            21))
+  (pass-if "fold-left pairlis"
+    (equal? (fold-left (lambda (accum e1 e2)
+                         (cons (cons e1 e2) accum))
+                       '((d . 4))
+                       '(a b c)
+                       '(1 2 3))
+            '((c . 3) (b . 2) (a . 1) (d  . 4)))))
-- 
1.7.6.4

bug#9883: R6RS fold-left

[Ludovic Courtès]

Hi Ian,

Ian Price <ianprice90@googlemail.com> skribis:

> According to the R6RS the accumulator should be the first argument of
> the combiner[0], not the last as in SRFI 1[1].
>
> I've attached a patch to fix this, and the use of fold-left in
> define-record-type.

Applied with minor changes in the commit log.  Thanks!

Ludo’.