[PATCH] Extensions for SRFI-171 (Transducers)

[PATCH] Extensions for SRFI-171 (Transducers)

[Colin Woodbury]

[-- Attachment #1.1: Type: text/plain, Size: 1122 bytes --]

Happy holidays everyone, I hope everything is going well for you.

Since discovering SRFI-171 (Transducers) I have fallen in love with it. 
Transducers let me "talk the way I want to talk" while knowing that I'm 
being efficient underneath w.r.t. to iteration and allocation. In using 
Guile's implementation, I noticed a few common idioms missing that are 
otherwise present in other languages, so I've added them in a series of 
patches. I've been using these often for a number of weeks without 
issue, but of course have added unit tests as well.

The full details are in the commit messages, but here are the main 
highlights:

  * rfold: The fundamental reducer. This allows the user to turn any
    two-arg function into a valid reducer, so that they don't need to
    worry about hand-writing reducers via case-lambda.
  * rfind: Yields the first item in the transduction that matches some
    predicate. Nice for locating some specific value from a potentially
    large data source (e.g. a port).
  * twindow: Like tsegment, but yields overlapping slices into the data.

Cheers, and have a great holiday.

Colin

[-- Attachment #1.2: Type: text/html, Size: 1450 bytes --]

[-- Attachment #2: 0001-srfi-171-add-twindow-and-various-reducers.patch --]
[-- Type: text/x-patch, Size: 4729 bytes --]

From 3161ce5e653e971c006c8f981a769fc7436f126b Mon Sep 17 00:00:00 2001
From: Colin Woodbury <colin@fosskers.ca>
Date: Mon, 19 Dec 2022 09:39:37 +0900
Subject: [PATCH 1/3] srfi-171: add twindow and various reducers

This adds a number of reduction primitives often seen in other languages
to Guile's SRFI-171 extensions.

Most critical may be `rfold`, which could be called the fundamental
reducer, as it's likely that all other reducers could be defined in
terms of it (though not all are). While `tfold` already exists in
Guile's SRFI-171 extension as a transducer, folding is in essence a
reduction. Also without a primative like `rlast` (also introduced here),
the results of `tfold` are difficult to consume. This is avoided by
providing `rfold` directly as a generalised means to collapse an entire
transduction down into a single value (i.e. the whole point of
reducers). `rfold` is also useful for the creation of ad-hoc reducers,
as any 2-arg function can be passed to it to fold the stream of values.

`rfirst`, `rlast`, and `rfind` are common idioms and so have been added.

The equivalent of `rmax` and `rmin` are easy to write manually via
`rfold`, but they have been provided here as a convenience in the same
spirit as `rcons`.

`rfor-each` also cannot be forgotten as a classic adaptation of its
SRFI-1 cousin.

Also added is `twindow`, handy for analysing groups of adjacent items.
---
 module/srfi/srfi-171/gnu.scm | 77 ++++++++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)

diff --git a/module/srfi/srfi-171/gnu.scm b/module/srfi/srfi-171/gnu.scm
index 45a4e19af..2ee023b4f 100644
--- a/module/srfi/srfi-171/gnu.scm
+++ b/module/srfi/srfi-171/gnu.scm
@@ -15,6 +15,7 @@
 ;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
 (define-module (srfi srfi-171 gnu)
+  #:use-module (ice-9 q)
   #:use-module (srfi srfi-171)
   #:use-module (srfi srfi-171 meta)
   #:export (tbatch tfold))
@@ -63,3 +64,79 @@
          (if (reduced? state)
              (reduced (reducer (unreduce state)))
              (r result state)))))))
+
+(define-public (twindow n)
+  "Yield @var{n}-length windows of overlapping values.  This is different from
+@code{tsegment} which yields non-overlapping windows. If there were
+fewer items in the input than @var{n}, then this yields nothing."
+  (when (not (and (integer? n) (positive? n)))
+        (error "argument to twindow must be a positive integer"))
+  (lambda (reducer)
+    (let ((i 0)
+          (q (make-q)))
+      (case-lambda
+        (() (reducer))
+        ((result) (reducer result))
+        ((result input)
+         (enq! q input)
+         (set! i (1+ i))
+         (cond ((< i n) result)
+               ((= i n) (reducer result (list-copy (car q))))
+               (else (deq! q)
+                     (reducer result (list-copy (car q))))))))))
+
+(define-public rfor-each
+  (case-lambda
+    "Run through every item in a transduction for their side effects but throw away
+all results."
+    (() *unspecified*)
+    ((acc) *unspecified*)
+    ((acc input) *unspecified*)))
+
+(define-public (rfirst seed)
+  "Yield the first value of the transduction, or the @var{seed} value if there is none."
+  (case-lambda
+    (() seed)
+    ((acc) acc)
+    ((_ input) (reduced input))))
+
+(define-public (rlast seed)
+  "Yield the final value of the transduction, or the @var{seed} value if there is none."
+  (case-lambda
+    (() seed)
+    ((acc) acc)
+    ((_ input) input)))
+
+(define-public (rfold f seed)
+  "The fundamental reducer. @code{rfold} creates an ad-hoc reducer based on
+a given 2-argument function. A @var{seed} is also required as the
+initial accumulator value, which also becomes the return value in case
+there was no input left in the transduction.
+
+Functions like @code{+} and @code{*} are automatically valid reducers,
+because they yield sane values even when given 0 or 1 arguments. Other
+functions like @code{max} cannot be used as-is as reducers since they
+require at least 2 arguments. For functions like this, @code{rfold} is
+appropriate."
+  (case-lambda
+    (() seed)
+    ((acc) acc)
+    ((acc input) (f acc input))))
+
+(define-public (rmax seed)
+  "Yield the maximum value of the transduction, or the @var{seed} value if
+there is none."
+  (rfold max seed))
+
+(define-public (rmin seed)
+  "Yield the minimum value of the transduction, or the @var{seed} value if
+there is none."
+  (rfold min seed))
+
+(define-public (rfind pred?)
+  "Find the first element in the transduction that satisfies a given predicate.
+Yields #f if no such element was found."
+  (case-lambda
+    (() #f)
+    ((acc) acc)
+    ((acc input) (if (pred? input) (reduced input) #f))))
-- 
2.39.0


[-- Attachment #3: 0002-doc-add-new-SRFI-171-reducers-to-the-manual.patch --]
[-- Type: text/x-patch, Size: 5703 bytes --]

From e80d6bf5fa010da1c0f8f4a81f92590e8049f4f3 Mon Sep 17 00:00:00 2001
From: Colin Woodbury <colin@fosskers.ca>
Date: Tue, 20 Dec 2022 09:41:51 +0900
Subject: [PATCH 2/3] doc: add new SRFI-171 reducers to the manual

---
 doc/ref/srfi-modules.texi | 96 +++++++++++++++++++++++++++++++++++++--
 1 file changed, 91 insertions(+), 5 deletions(-)

diff --git a/doc/ref/srfi-modules.texi b/doc/ref/srfi-modules.texi
index 0ef136215..23677384d 100644
--- a/doc/ref/srfi-modules.texi
+++ b/doc/ref/srfi-modules.texi
@@ -5836,7 +5836,7 @@ identity in the reduction.
 @cindex transducers reducers
 
 @deffn {Scheme Procedure} rcons
-a simple consing reducer. When called without values, it returns its
+A simple consing reducer. When called without values, it returns its
 identity, @code{'()}.  With one value, which will be a list, it reverses
 the list (using @code{reverse!}).  When called with two values, it conses
 the second value to the first.
@@ -5848,7 +5848,7 @@ the second value to the first.
 @end deffn
 
 @deffn {Scheme Procedure} reverse-rcons
-same as rcons, but leaves the values in their reversed order.
+The same as @code{rcons}, but leaves the values in their reversed order.
 @example
 (list-transduce (tmap (lambda (x) (+ x 1))) reverse-rcons (list 0 1 2 3))
 @result{} (4 3 2 1)
@@ -5856,7 +5856,7 @@ same as rcons, but leaves the values in their reversed order.
 @end deffn
 
 @deffn {Scheme Procedure} rany pred?
-The reducer version of any.  Returns @code{(reduced (pred? value))} if
+The reducer version of @code{any}.  Returns @code{(reduced (pred? value))} if
 any @code{(pred? value)} returns non-#f.  The identity is #f.
 
 @example
@@ -5869,7 +5869,7 @@ any @code{(pred? value)} returns non-#f.  The identity is #f.
 @end deffn
 
 @deffn {Scheme Procedure} revery pred?
-The reducer version of every.  Stops the transduction and returns
+The reducer version of @code{every}.  Stops the transduction and returns
 @code{(reduced #f)} if any @code{(pred? value)} returns #f.  If every
 @code{(pred? value)} returns true, it returns the result of the last
 invocation of @code{(pred? value)}.  The identity is #t.
@@ -5894,6 +5894,77 @@ transduction.
 @end example
 @end deffn
 
+@subheading Guile-specific reducers
+These reducers are available in the @code{(srfi srfi-171 gnu)} module,
+and are provided outside the standard described by the SRFI-171
+document.
+
+@deffn {Scheme Procedure} rfold proc seed
+The fundamental reducer. @code{rfold} creates an ad-hoc reducer based on
+a given 2-argument @var{proc}. A @var{seed} is required as the initial
+accumulator value, which also becomes the final return value in the case
+where there was no input left in the transduction.
+
+The first argument to the @var{proc} is the accumulating value, and the
+second is the current item of the transduction.
+
+Note that functions like @code{+} and @code{*} are automatically valid
+reducers, because they yield sane values even when given 0 or 1
+arguments. Other functions like @code{max} cannot be used as-is as
+reducers since they require at least 2 arguments. For functions like
+this, @code{rfold} is appropriate.
+
+@example
+;; Turning built-ins into reducers. Identical to rmax.
+(list-transduce (tfilter odd?) (rfold max 0) '(1 2 3 4 5))
+@result{} 5
+
+;; Custom lambdas into reducers. Identical to rlast.
+(list-transduce (tmap identity)
+                (rfold (lambda (_ input) input) #f)
+                '("abc" "def" "ghi"))
+@result{} "ghi"
+
+;; Track the 3 largest values in a transduction.
+(define (three-largest acc input)
+  (take (sort (cons input acc) >) 3))
+
+(list-transduce (tfilter odd?)
+                (rfold three-largest '(0 0 0))
+                '(7 1 4 2 13 5 9 2 8))
+@result{} (13 9 7)
+@end example
+@end deffn
+
+@deffn {Scheme Procedure} rfind pred?
+Find the first element in the transduction that satisfies a given
+predicate. Yields #f if no such element was found.
+
+@example
+(list-transduce (tmap identity)
+                (rfind string?)
+                '(1 c #t 4.12 "Jack" ()))
+@result{} "Jack"
+@end example
+@end deffn
+
+@deffn {Scheme Procedure} rfirst seed
+@deffnx {Scheme Procedure} rlast seed
+Yield the first (or last) value of the transduction, or the @var{seed}
+value if there is none.
+@end deffn
+
+@deffn {Scheme Procedure} rfor-each proc
+Apply @var{proc} for its side-effects to every value of the
+transduction, ignoring all results. Like its @ref{SRFI-1} cousin, yields
+@code{*unspecified*}.
+@end deffn
+
+@deffn {Scheme Procedure} rmax seed
+@deffnx {Scheme Procedure} rmin seed
+Yield the maximum (or minimum) value of the transduction, or the
+@var{seed} value if there is none.
+@end deffn
 
 @node SRFI-171 Transducers
 @subsubsection Transducers
@@ -6057,7 +6128,7 @@ Stateless.
 
 @subheading Guile-specific transducers
 These transducers are available in the @code{(srfi srfi-171 gnu)}
-library, and are provided outside the standard described by the SRFI-171
+module, and are provided outside the standard described by the SRFI-171
 document.
 
 @deffn {Scheme Procedure} tbatch reducer
@@ -6085,6 +6156,21 @@ value)}, saving its result between iterations.
 @end example
 @end deffn
 
+@deffn {Scheme Procedure} twindow n
+
+Returns a transducer that yields @var{n}-length windows of overlapping
+values. This is different from @code{tsegment} which yields
+non-overlapping windows. If there were fewer items in the input than
+@var{n}, then this yields nothing.
+
+@example
+(list-transduce (twindow 3) rcons '(1 2 3 4 5))
+@result{} ((1 2 3) (2 3 4) (3 4 5))
+@end example
+
+Stateful.
+@end deffn
+
 
 @node SRFI-171 Helpers
 @subsubsection Helper functions for writing transducers
-- 
2.39.0


[-- Attachment #4: 0003-srfi-171-add-unit-tests-for-new-functions.patch --]
[-- Type: text/x-patch, Size: 2891 bytes --]

From 9e22d0dee6b14b6689815112b202ab4e4621eeac Mon Sep 17 00:00:00 2001
From: Colin Woodbury <colin@fosskers.ca>
Date: Wed, 21 Dec 2022 09:30:50 +0900
Subject: [PATCH 3/3] srfi-171: add unit tests for new functions

These tests mainly match the examples shown in the docs.
---
 test-suite/tests/srfi-171.test | 66 ++++++++++++++++++++++++++++++----
 1 file changed, 60 insertions(+), 6 deletions(-)

diff --git a/test-suite/tests/srfi-171.test b/test-suite/tests/srfi-171.test
index 1ef7bc5f2..d1d54b2ec 100644
--- a/test-suite/tests/srfi-171.test
+++ b/test-suite/tests/srfi-171.test
@@ -207,15 +207,69 @@
             (list-transduce (tenumerate (- 1)) rcons numeric-list)))
 
   (pass-if "tbatch"
-    (equal?
-            '((0 1) (2 3) (4))
+    (equal? '((0 1) (2 3) (4))
             (list-transduce (tbatch (ttake 2) rcons) rcons numeric-list)))
 
   (pass-if "tfold"
-           (equal?
-            '(0 1 3 6 10)
-            (list-transduce (tfold +) rcons numeric-list))))
-
+    (equal? '(0 1 3 6 10)
+            (list-transduce (tfold +) rcons numeric-list)))
+
+  (pass-if "twindow: too wide of a window"
+    (equal? '()
+            (list-transduce (twindow 10) rcons '(1 2 3))))
+
+  (pass-if "twindow: acceptable window"
+    (equal? '((1 2 3) (2 3 4) (3 4 5))
+            (list-transduce (twindow 3) rcons '(1 2 3 4 5)))))
+
+(with-test-prefix "reducers"
+  (pass-if "rfold: builtin"
+    (equal? 5
+            (list-transduce (tfilter odd?) (rfold max 0) '(1 2 3 4 5))))
+
+  (pass-if "rfold: custom lambda"
+    (equal? "ghi"
+            (list-transduce (tmap identity)
+                            (rfold (lambda (_ input) input) #f)
+                            '("abc" "def" "ghi"))))
+
+  (pass-if "rfirst: empty"
+    (equal? 0
+            (list-transduce (tmap identity) (rfirst 0) '())))
+
+  (pass-if "rfirst: non-empty"
+    (equal? 1
+            (list-transduce (tmap identity) (rfirst 0) '(1 2 3))))
+
+  (pass-if "rlast: empty"
+    (equal? 0
+            (list-transduce (tfilter (lambda (_) #f)) (rlast 0) '(1 2 3))))
+
+  (pass-if "rlast: non-empty"
+    (equal? 5
+            (list-transduce (tmap identity) (rlast 0) '(1 2 3 4 5))))
+
+  (pass-if "rmax: empty"
+    (equal? 0
+            (list-transduce (tmap identity) (rmax 0) '())))
+
+  (pass-if "rmax: non-empty"
+    (equal? 31
+            (list-transduce (tmap identity) (rmax 0) '(1 2 31 4 5))))
+
+  (pass-if "rmin: empty"
+    (equal? 0
+            (list-transduce (tmap identity) (rmin 0) '())))
+
+  (pass-if "rmin: non-empty"
+    (equal? 1
+            (list-transduce (tmap identity) (rmin 1000) '(5 3 1 7 6))))
+
+  (pass-if "rfind"
+    (equal? "Jack"
+            (list-transduce (tmap identity)
+                            (rfind string?)
+                            '(1 c #t 4.12 "Jack" ())))))
 
 (with-test-prefix "x-transduce"
   (pass-if "list-transduce" 
-- 
2.39.0

Re: [PATCH] Extensions for SRFI-171 (Transducers)

[Linus Björnstam]

As the author of both the SRFI and the guile code I am very happy you like it. I don't have a computer at the moment, but I looked through the code and it looked great.

All additions should have been included in the original SRFI :)

one comment: your code uses define-public, which the rest of SRFI-171 code does not.

I am not in any position to sign code off for inclusion in guile proper, but if the define-public thing is fixed it very much has my blessing.

Best regards 
  Linus Björnstam

On Wed, 21 Dec 2022, at 01:48, Colin Woodbury wrote:
> Happy holidays everyone, I hope everything is going well for you.
>
> Since discovering SRFI-171 (Transducers) I have fallen in love with it. 
> Transducers let me "talk the way I want to talk" while knowing that I'm 
> being efficient underneath w.r.t. to iteration and allocation. In using 
> Guile's implementation, I noticed a few common idioms missing that are 
> otherwise present in other languages, so I've added them in a series of 
> patches. I've been using these often for a number of weeks without 
> issue, but of course have added unit tests as well.
>
> The full details are in the commit messages, but here are the main highlights:
>
>  * rfold: The fundamental reducer. This allows the user to turn any 
> two-arg function into a valid reducer, so that they don't need to worry 
> about hand-writing reducers via case-lambda. 
>  * rfind: Yields the first item in the transduction that matches some 
> predicate. Nice for locating some specific value from a potentially 
> large data source (e.g. a port). 
>  * twindow: Like tsegment, but yields overlapping slices into the data. 
> Cheers, and have a great holiday.
>
> Colin
>
> Attachments:
> * 0001-srfi-171-add-twindow-and-various-reducers.patch
> * 0002-doc-add-new-SRFI-171-reducers-to-the-manual.patch
> * 0003-srfi-171-add-unit-tests-for-new-functions.patch

Re: [PATCH] Extensions for SRFI-171 (Transducers)

[Damien Mattei]

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

hello,
just trying transducers before using it, i try to understand.
what is wrong with that:
scheme@(guile-user)> (list-transduce (tfilter (λ (x) x))
(tdelete-duplicates) (list 1 2 #f 3 3 4))
ice-9/boot-9.scm:1685:16: In procedure raise-exception:
Wrong number of arguments to #<procedure 10786aa60 at
srfi/srfi-171.scm:338:2 (reducer)>

Entering a new prompt.  Type `,bt' for a backtrace or `,q' to continue.

Regards,
Damien

On Wed, Dec 21, 2022 at 11:01 AM Linus Björnstam <
linus.bjornstam@veryfast.biz> wrote:

> As the author of both the SRFI and the guile code I am very happy you like
> it. I don't have a computer at the moment, but I looked through the code
> and it looked great.
>
> All additions should have been included in the original SRFI :)
>
> one comment: your code uses define-public, which the rest of SRFI-171 code
> does not.
>
> I am not in any position to sign code off for inclusion in guile proper,
> but if the define-public thing is fixed it very much has my blessing.
>
> Best regards
>   Linus Björnstam
>
> On Wed, 21 Dec 2022, at 01:48, Colin Woodbury wrote:
> > Happy holidays everyone, I hope everything is going well for you.
> >
> > Since discovering SRFI-171 (Transducers) I have fallen in love with it.
> > Transducers let me "talk the way I want to talk" while knowing that I'm
> > being efficient underneath w.r.t. to iteration and allocation. In using
> > Guile's implementation, I noticed a few common idioms missing that are
> > otherwise present in other languages, so I've added them in a series of
> > patches. I've been using these often for a number of weeks without
> > issue, but of course have added unit tests as well.
> >
> > The full details are in the commit messages, but here are the main
> highlights:
> >
> >  * rfold: The fundamental reducer. This allows the user to turn any
> > two-arg function into a valid reducer, so that they don't need to worry
> > about hand-writing reducers via case-lambda.
> >  * rfind: Yields the first item in the transduction that matches some
> > predicate. Nice for locating some specific value from a potentially
> > large data source (e.g. a port).
> >  * twindow: Like tsegment, but yields overlapping slices into the data.
> > Cheers, and have a great holiday.
> >
> > Colin
> >
> > Attachments:
> > * 0001-srfi-171-add-twindow-and-various-reducers.patch
> > * 0002-doc-add-new-SRFI-171-reducers-to-the-manual.patch
> > * 0003-srfi-171-add-unit-tests-for-new-functions.patch
>
>

[-- Attachment #2: Type: text/html, Size: 3453 bytes --]

Re: [PATCH] Extensions for SRFI-171 (Transducers)

[Damien Mattei]

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

i just understood the scheme :-)

scheme@(guile-user)> (list-transduce (compose (tfilter (λ (x) x))
(tdelete-duplicates)) rcons (list 1 2 #f 3 3 4))
$12 = (1 2 3 4)

sorry...


On Thu, Dec 22, 2022 at 3:33 PM Damien Mattei <damien.mattei@gmail.com>
wrote:

> hello,
> just trying transducers before using it, i try to understand.
> what is wrong with that:
> scheme@(guile-user)> (list-transduce (tfilter (λ (x) x))
> (tdelete-duplicates) (list 1 2 #f 3 3 4))
> ice-9/boot-9.scm:1685:16: In procedure raise-exception:
> Wrong number of arguments to #<procedure 10786aa60 at
> srfi/srfi-171.scm:338:2 (reducer)>
>
> Entering a new prompt.  Type `,bt' for a backtrace or `,q' to continue.
>
> Regards,
> Damien
>
> On Wed, Dec 21, 2022 at 11:01 AM Linus Björnstam <
> linus.bjornstam@veryfast.biz> wrote:
>
>> As the author of both the SRFI and the guile code I am very happy you
>> like it. I don't have a computer at the moment, but I looked through the
>> code and it looked great.
>>
>> All additions should have been included in the original SRFI :)
>>
>> one comment: your code uses define-public, which the rest of SRFI-171
>> code does not.
>>
>> I am not in any position to sign code off for inclusion in guile proper,
>> but if the define-public thing is fixed it very much has my blessing.
>>
>> Best regards
>>   Linus Björnstam
>>
>> On Wed, 21 Dec 2022, at 01:48, Colin Woodbury wrote:
>> > Happy holidays everyone, I hope everything is going well for you.
>> >
>> > Since discovering SRFI-171 (Transducers) I have fallen in love with it.
>> > Transducers let me "talk the way I want to talk" while knowing that I'm
>> > being efficient underneath w.r.t. to iteration and allocation. In using
>> > Guile's implementation, I noticed a few common idioms missing that are
>> > otherwise present in other languages, so I've added them in a series of
>> > patches. I've been using these often for a number of weeks without
>> > issue, but of course have added unit tests as well.
>> >
>> > The full details are in the commit messages, but here are the main
>> highlights:
>> >
>> >  * rfold: The fundamental reducer. This allows the user to turn any
>> > two-arg function into a valid reducer, so that they don't need to worry
>> > about hand-writing reducers via case-lambda.
>> >  * rfind: Yields the first item in the transduction that matches some
>> > predicate. Nice for locating some specific value from a potentially
>> > large data source (e.g. a port).
>> >  * twindow: Like tsegment, but yields overlapping slices into the data.
>> > Cheers, and have a great holiday.
>> >
>> > Colin
>> >
>> > Attachments:
>> > * 0001-srfi-171-add-twindow-and-various-reducers.patch
>> > * 0002-doc-add-new-SRFI-171-reducers-to-the-manual.patch
>> > * 0003-srfi-171-add-unit-tests-for-new-functions.patch
>>
>>

[-- Attachment #2: Type: text/html, Size: 4365 bytes --]

Re: [PATCH] Extensions for SRFI-171 (Transducers)

[Damien Mattei]

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

i'm interested with transducers to speed up code:

;; 8'21" MacOS Ventura M1
  {unified-minterms-set-2 <+ (filter (λ (x) x) unified-minterms-set-1)} ;;
remove #f results
  (nodebug
   {unified-minterms-set-2-length <+ (length unified-minterms-set-2)}
   (dv unified-minterms-set-2-length))

  {unified-minterms-set <+ (remove-duplicates unified-minterms-set-2)}
;;(remove-duplicates-sorted unified-minterms-set-2)} ;; uniq MODIF
  (nodebug
   {unified-minterms-set-uniq-length <+ (length unified-minterms-set)}
   (dv unified-minterms-set-uniq-length))

with transducers:
;; 7'08" MacOS Ventura M1
  {unified-minterms-set <+ (list-transduce (compose (tfilter (λ (x) x))
(tdelete-duplicates)) rcons unified-minterms-set-1)}

it is an interesting 15% speed up in my code.


On Thu, Dec 22, 2022 at 3:52 PM Damien Mattei <damien.mattei@gmail.com>
wrote:

> i just understood the scheme :-)
>
> scheme@(guile-user)> (list-transduce (compose (tfilter (λ (x) x))
> (tdelete-duplicates)) rcons (list 1 2 #f 3 3 4))
> $12 = (1 2 3 4)
>
> sorry...
>
>
> On Thu, Dec 22, 2022 at 3:33 PM Damien Mattei <damien.mattei@gmail.com>
> wrote:
>
>> hello,
>> just trying transducers before using it, i try to understand.
>> what is wrong with that:
>> scheme@(guile-user)> (list-transduce (tfilter (λ (x) x))
>> (tdelete-duplicates) (list 1 2 #f 3 3 4))
>> ice-9/boot-9.scm:1685:16: In procedure raise-exception:
>> Wrong number of arguments to #<procedure 10786aa60 at
>> srfi/srfi-171.scm:338:2 (reducer)>
>>
>> Entering a new prompt.  Type `,bt' for a backtrace or `,q' to continue.
>>
>> Regards,
>> Damien
>>
>> On Wed, Dec 21, 2022 at 11:01 AM Linus Björnstam <
>> linus.bjornstam@veryfast.biz> wrote:
>>
>>> As the author of both the SRFI and the guile code I am very happy you
>>> like it. I don't have a computer at the moment, but I looked through the
>>> code and it looked great.
>>>
>>> All additions should have been included in the original SRFI :)
>>>
>>> one comment: your code uses define-public, which the rest of SRFI-171
>>> code does not.
>>>
>>> I am not in any position to sign code off for inclusion in guile proper,
>>> but if the define-public thing is fixed it very much has my blessing.
>>>
>>> Best regards
>>>   Linus Björnstam
>>>
>>> On Wed, 21 Dec 2022, at 01:48, Colin Woodbury wrote:
>>> > Happy holidays everyone, I hope everything is going well for you.
>>> >
>>> > Since discovering SRFI-171 (Transducers) I have fallen in love with
>>> it.
>>> > Transducers let me "talk the way I want to talk" while knowing that
>>> I'm
>>> > being efficient underneath w.r.t. to iteration and allocation. In
>>> using
>>> > Guile's implementation, I noticed a few common idioms missing that are
>>> > otherwise present in other languages, so I've added them in a series
>>> of
>>> > patches. I've been using these often for a number of weeks without
>>> > issue, but of course have added unit tests as well.
>>> >
>>> > The full details are in the commit messages, but here are the main
>>> highlights:
>>> >
>>> >  * rfold: The fundamental reducer. This allows the user to turn any
>>> > two-arg function into a valid reducer, so that they don't need to
>>> worry
>>> > about hand-writing reducers via case-lambda.
>>> >  * rfind: Yields the first item in the transduction that matches some
>>> > predicate. Nice for locating some specific value from a potentially
>>> > large data source (e.g. a port).
>>> >  * twindow: Like tsegment, but yields overlapping slices into the
>>> data.
>>> > Cheers, and have a great holiday.
>>> >
>>> > Colin
>>> >
>>> > Attachments:
>>> > * 0001-srfi-171-add-twindow-and-various-reducers.patch
>>> > * 0002-doc-add-new-SRFI-171-reducers-to-the-manual.patch
>>> > * 0003-srfi-171-add-unit-tests-for-new-functions.patch
>>>
>>>

[-- Attachment #2: Type: text/html, Size: 6119 bytes --]

Re: [PATCH] Extensions for SRFI-171 (Transducers)

[Damien Mattei]

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

that is strange but with more ,the same ,tests i have no more speed up:

with Racket versions of srfi 171

{unified-minterms-set-2 <+ (filter (λ (x) x) unified-minterms-set-1)} ;;
remove #f results
  ;; (nodebug
  ;;  {unified-minterms-set-2-length <+ (length unified-minterms-set-2)}
  ;;  (dv unified-minterms-set-2-length))

  {unified-minterms-set <+ (remove-duplicates unified-minterms-set-2)} ;;
(remove-duplicates-sorted unified-minterms-set-2)} ;; uniq MODIF
  ;; C12 in Terminal mode with MacOS Ventura M1 and 32"

  ;; (nodebug
  ;;  {unified-minterms-set-uniq-length <+ (length unified-minterms-set)}
  ;;  (dv unified-minterms-set-uniq-length))

  ;;{unified-minterms-set <+ (remove-duplicates (filter (λ (x) x)
unified-minterms-set-1))} ;; C12 in Terminal mode with MacOS Ventura M1 and
32"

  ;;{unified-minterms-set <+ (list-transduce (compose (tfilter (λ (x) x))
(tdelete-duplicates)) rcons unified-minterms-set-1)} ;; C12 in Terminal
mode with MacOS Ventura M1 and 31"

and Guile:

 ;; 8'04" MacOS Ventura M1 for C12 ,50" for C11
  ;;{unified-minterms-set-2 <+ (filter (λ (x) x) unified-minterms-set-1)}
;; remove #f results
  ;; (nodebug
  ;;  {unified-minterms-set-2-length <+ (length unified-minterms-set-2)}
  ;;  (dv unified-minterms-set-2-length))

  ;;{unified-minterms-set <+ (remove-duplicates unified-minterms-set-2)}
;;(remove-duplicates-sorted unified-minterms-set-2)} ;; uniq MODIF
  ;; (nodebug
  ;;  {unified-minterms-set-uniq-length <+ (length unified-minterms-set)}
  ;;  (dv unified-minterms-set-uniq-length))

  {unified-minterms-set <+ (remove-duplicates (filter (λ (x) x)
unified-minterms-set-1))} ;; 59" for C11, 8'05" for C12

  ;; 7'08" ,8'15" MacOS Ventura M1 for C12 and 56" for C11
  ;;{unified-minterms-set <+ (list-transduce (compose (tfilter (λ (x) x))
(tdelete-duplicates)) rcons unified-minterms-set-1)}

some code is commented because i only run one test at a time.

I suppose the speed up was only because debug mode slowed down other code
but perheaps my test are not reliable, i can only explain some slow down
now due to CPU overloaded by another process in the system at different
moment in tests. I have no idea how to perform more reliable tests.

On Thu, Dec 22, 2022 at 6:32 PM Damien Mattei <damien.mattei@gmail.com>
wrote:

> i'm interested with transducers to speed up code:
>
> ;; 8'21" MacOS Ventura M1
>   {unified-minterms-set-2 <+ (filter (λ (x) x) unified-minterms-set-1)} ;;
> remove #f results
>   (nodebug
>    {unified-minterms-set-2-length <+ (length unified-minterms-set-2)}
>    (dv unified-minterms-set-2-length))
>
>   {unified-minterms-set <+ (remove-duplicates unified-minterms-set-2)}
> ;;(remove-duplicates-sorted unified-minterms-set-2)} ;; uniq MODIF
>   (nodebug
>    {unified-minterms-set-uniq-length <+ (length unified-minterms-set)}
>    (dv unified-minterms-set-uniq-length))
>
> with transducers:
> ;; 7'08" MacOS Ventura M1
>   {unified-minterms-set <+ (list-transduce (compose (tfilter (λ (x) x))
> (tdelete-duplicates)) rcons unified-minterms-set-1)}
>
> it is an interesting 15% speed up in my code.
>
>
> On Thu, Dec 22, 2022 at 3:52 PM Damien Mattei <damien.mattei@gmail.com>
> wrote:
>
>> i just understood the scheme :-)
>>
>> scheme@(guile-user)> (list-transduce (compose (tfilter (λ (x) x))
>> (tdelete-duplicates)) rcons (list 1 2 #f 3 3 4))
>> $12 = (1 2 3 4)
>>
>> sorry...
>>
>>
>> On Thu, Dec 22, 2022 at 3:33 PM Damien Mattei <damien.mattei@gmail.com>
>> wrote:
>>
>>> hello,
>>> just trying transducers before using it, i try to understand.
>>> what is wrong with that:
>>> scheme@(guile-user)> (list-transduce (tfilter (λ (x) x))
>>> (tdelete-duplicates) (list 1 2 #f 3 3 4))
>>> ice-9/boot-9.scm:1685:16: In procedure raise-exception:
>>> Wrong number of arguments to #<procedure 10786aa60 at
>>> srfi/srfi-171.scm:338:2 (reducer)>
>>>
>>> Entering a new prompt.  Type `,bt' for a backtrace or `,q' to continue.
>>>
>>> Regards,
>>> Damien
>>>
>>> On Wed, Dec 21, 2022 at 11:01 AM Linus Björnstam <
>>> linus.bjornstam@veryfast.biz> wrote:
>>>
>>>> As the author of both the SRFI and the guile code I am very happy you
>>>> like it. I don't have a computer at the moment, but I looked through the
>>>> code and it looked great.
>>>>
>>>> All additions should have been included in the original SRFI :)
>>>>
>>>> one comment: your code uses define-public, which the rest of SRFI-171
>>>> code does not.
>>>>
>>>> I am not in any position to sign code off for inclusion in guile
>>>> proper, but if the define-public thing is fixed it very much has my
>>>> blessing.
>>>>
>>>> Best regards
>>>>   Linus Björnstam
>>>>
>>>> On Wed, 21 Dec 2022, at 01:48, Colin Woodbury wrote:
>>>> > Happy holidays everyone, I hope everything is going well for you.
>>>> >
>>>> > Since discovering SRFI-171 (Transducers) I have fallen in love with
>>>> it.
>>>> > Transducers let me "talk the way I want to talk" while knowing that
>>>> I'm
>>>> > being efficient underneath w.r.t. to iteration and allocation. In
>>>> using
>>>> > Guile's implementation, I noticed a few common idioms missing that
>>>> are
>>>> > otherwise present in other languages, so I've added them in a series
>>>> of
>>>> > patches. I've been using these often for a number of weeks without
>>>> > issue, but of course have added unit tests as well.
>>>> >
>>>> > The full details are in the commit messages, but here are the main
>>>> highlights:
>>>> >
>>>> >  * rfold: The fundamental reducer. This allows the user to turn any
>>>> > two-arg function into a valid reducer, so that they don't need to
>>>> worry
>>>> > about hand-writing reducers via case-lambda.
>>>> >  * rfind: Yields the first item in the transduction that matches some
>>>> > predicate. Nice for locating some specific value from a potentially
>>>> > large data source (e.g. a port).
>>>> >  * twindow: Like tsegment, but yields overlapping slices into the
>>>> data.
>>>> > Cheers, and have a great holiday.
>>>> >
>>>> > Colin
>>>> >
>>>> > Attachments:
>>>> > * 0001-srfi-171-add-twindow-and-various-reducers.patch
>>>> > * 0002-doc-add-new-SRFI-171-reducers-to-the-manual.patch
>>>> > * 0003-srfi-171-add-unit-tests-for-new-functions.patch
>>>>
>>>>

[-- Attachment #2: Type: text/html, Size: 9645 bytes --]

Re: [PATCHv2] Extensions for SRFI-171 (Transducers)

[Colin Woodbury]

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

Hi Linus, great to hear from you. Thanks for the feedback. I've attached 
new versions of the patches (with your suggested fix), and also an extra 
4th commit that adds a short guide for how to write one's own Reducers.

Merry Christmas!

Colin

On 12/21/22 19:00, Linus Björnstam wrote:
> As the author of both the SRFI and the guile code I am very happy you like it. I don't have a computer at the moment, but I looked through the code and it looked great.
>
> All additions should have been included in the original SRFI :)
>
> one comment: your code uses define-public, which the rest of SRFI-171 code does not.
>
> I am not in any position to sign code off for inclusion in guile proper, but if the define-public thing is fixed it very much has my blessing.
>
> Best regards
>    Linus Björnstam
>
> On Wed, 21 Dec 2022, at 01:48, Colin Woodbury wrote:
>> Happy holidays everyone, I hope everything is going well for you.
>>
>> Since discovering SRFI-171 (Transducers) I have fallen in love with it.
>> Transducers let me "talk the way I want to talk" while knowing that I'm
>> being efficient underneath w.r.t. to iteration and allocation. In using
>> Guile's implementation, I noticed a few common idioms missing that are
>> otherwise present in other languages, so I've added them in a series of
>> patches. I've been using these often for a number of weeks without
>> issue, but of course have added unit tests as well.
>>
>> The full details are in the commit messages, but here are the main highlights:
>>
>>   * rfold: The fundamental reducer. This allows the user to turn any
>> two-arg function into a valid reducer, so that they don't need to worry
>> about hand-writing reducers via case-lambda.
>>   * rfind: Yields the first item in the transduction that matches some
>> predicate. Nice for locating some specific value from a potentially
>> large data source (e.g. a port).
>>   * twindow: Like tsegment, but yields overlapping slices into the data.
>> Cheers, and have a great holiday.
>>
>> Colin
>>
>> Attachments:
>> * 0001-srfi-171-add-twindow-and-various-reducers.patch
>> * 0002-doc-add-new-SRFI-171-reducers-to-the-manual.patch
>> * 0003-srfi-171-add-unit-tests-for-new-functions.patch

[-- Attachment #2: 0001-srfi-171-add-twindow-and-various-reducers.patch --]
[-- Type: text/x-patch, Size: 4899 bytes --]

From 96856b184a507886db2c5c20323983ae125a6bdb Mon Sep 17 00:00:00 2001
From: Colin Woodbury <colin@fosskers.ca>
Date: Mon, 19 Dec 2022 09:39:37 +0900
Subject: [PATCH 1/4] srfi-171: add twindow and various reducers

This adds a number of reduction primitives often seen in other languages
to Guile's SRFI-171 extensions.

Most critical may be `rfold`, which could be called the fundamental
reducer, as it's likely that all other reducers could be defined in
terms of it (though not all are). While `tfold` already exists in
Guile's SRFI-171 extension as a transducer, folding is in essence a
reduction. Also without a primative like `rlast` (also introduced here),
the results of `tfold` are difficult to consume. This is avoided by
providing `rfold` directly as a generalised means to collapse an entire
transduction down into a single value (i.e. the whole point of
reducers). `rfold` is also useful for the creation of ad-hoc reducers,
as any 2-arg function can be passed to it to fold the stream of values.

`rfirst`, `rlast`, and `rfind` are common idioms and so have been added.

The equivalent of `rmax` and `rmin` are easy to write manually via
`rfold`, but they have been provided here as a convenience in the same
spirit as `rcons`.

`rfor-each` also cannot be forgotten as a classic adaptation of its
SRFI-1 cousin.

Also added is `twindow`, handy for analysing groups of adjacent items.
---
 module/srfi/srfi-171/gnu.scm | 87 +++++++++++++++++++++++++++++++++++-
 1 file changed, 85 insertions(+), 2 deletions(-)

diff --git a/module/srfi/srfi-171/gnu.scm b/module/srfi/srfi-171/gnu.scm
index 45a4e19af..c41925e8a 100644
--- a/module/srfi/srfi-171/gnu.scm
+++ b/module/srfi/srfi-171/gnu.scm
@@ -15,10 +15,17 @@
 ;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
 (define-module (srfi srfi-171 gnu)
+  #:use-module (ice-9 q)
   #:use-module (srfi srfi-171)
   #:use-module (srfi srfi-171 meta)
-  #:export (tbatch tfold))
-
+  #:export (tbatch
+            tfold
+            twindow
+            rfind
+            rfirst rlast
+            rfold
+            rfor-each
+            rmax rmin))
 
 (define tbatch
   (case-lambda
@@ -63,3 +70,79 @@
          (if (reduced? state)
              (reduced (reducer (unreduce state)))
              (r result state)))))))
+
+(define (twindow n)
+  "Yield @var{n}-length windows of overlapping values.  This is different from
+@code{tsegment} which yields non-overlapping windows. If there were
+fewer items in the input than @var{n}, then this yields nothing."
+  (when (not (and (integer? n) (positive? n)))
+        (error "argument to twindow must be a positive integer"))
+  (lambda (reducer)
+    (let ((i 0)
+          (q (make-q)))
+      (case-lambda
+        (() (reducer))
+        ((result) (reducer result))
+        ((result input)
+         (enq! q input)
+         (set! i (1+ i))
+         (cond ((< i n) result)
+               ((= i n) (reducer result (list-copy (car q))))
+               (else (deq! q)
+                     (reducer result (list-copy (car q))))))))))
+
+(define rfor-each
+  (case-lambda
+    "Run through every item in a transduction for their side effects but throw away
+all results."
+    (() *unspecified*)
+    ((acc) *unspecified*)
+    ((acc input) *unspecified*)))
+
+(define (rfirst seed)
+  "Yield the first value of the transduction, or the @var{seed} value if there is none."
+  (case-lambda
+    (() seed)
+    ((acc) acc)
+    ((_ input) (reduced input))))
+
+(define (rlast seed)
+  "Yield the final value of the transduction, or the @var{seed} value if there is none."
+  (case-lambda
+    (() seed)
+    ((acc) acc)
+    ((_ input) input)))
+
+(define (rfold f seed)
+  "The fundamental reducer. @code{rfold} creates an ad-hoc reducer based on
+a given 2-argument function. A @var{seed} is also required as the
+initial accumulator value, which also becomes the return value in case
+there was no input left in the transduction.
+
+Functions like @code{+} and @code{*} are automatically valid reducers,
+because they yield sane values even when given 0 or 1 arguments. Other
+functions like @code{max} cannot be used as-is as reducers since they
+require at least 2 arguments. For functions like this, @code{rfold} is
+appropriate."
+  (case-lambda
+    (() seed)
+    ((acc) acc)
+    ((acc input) (f acc input))))
+
+(define (rmax seed)
+  "Yield the maximum value of the transduction, or the @var{seed} value if
+there is none."
+  (rfold max seed))
+
+(define (rmin seed)
+  "Yield the minimum value of the transduction, or the @var{seed} value if
+there is none."
+  (rfold min seed))
+
+(define (rfind pred?)
+  "Find the first element in the transduction that satisfies a given predicate.
+Yields #f if no such element was found."
+  (case-lambda
+    (() #f)
+    ((acc) acc)
+    ((acc input) (if (pred? input) (reduced input) #f))))
-- 
2.39.0


[-- Attachment #3: 0002-doc-add-new-SRFI-171-reducers-to-the-manual.patch --]
[-- Type: text/x-patch, Size: 5704 bytes --]

From 58e7ca2718a860ca2fb5692684d6d128a7c1ae75 Mon Sep 17 00:00:00 2001
From: Colin Woodbury <colin@fosskers.ca>
Date: Tue, 20 Dec 2022 09:41:51 +0900
Subject: [PATCH 2/4] doc: add new SRFI-171 reducers to the manual

---
 doc/ref/srfi-modules.texi | 96 +++++++++++++++++++++++++++++++++++++--
 1 file changed, 91 insertions(+), 5 deletions(-)

diff --git a/doc/ref/srfi-modules.texi b/doc/ref/srfi-modules.texi
index bce5b4eac..6eb1a563e 100644
--- a/doc/ref/srfi-modules.texi
+++ b/doc/ref/srfi-modules.texi
@@ -5836,7 +5836,7 @@ identity in the reduction.
 @cindex transducers reducers
 
 @deffn {Scheme Procedure} rcons
-a simple consing reducer. When called without values, it returns its
+A simple consing reducer. When called without values, it returns its
 identity, @code{'()}.  With one value, which will be a list, it reverses
 the list (using @code{reverse!}).  When called with two values, it conses
 the second value to the first.
@@ -5848,7 +5848,7 @@ the second value to the first.
 @end deffn
 
 @deffn {Scheme Procedure} reverse-rcons
-same as rcons, but leaves the values in their reversed order.
+The same as @code{rcons}, but leaves the values in their reversed order.
 @example
 (list-transduce (tmap (lambda (x) (+ x 1))) reverse-rcons (list 0 1 2 3))
 @result{} (4 3 2 1)
@@ -5856,7 +5856,7 @@ same as rcons, but leaves the values in their reversed order.
 @end deffn
 
 @deffn {Scheme Procedure} rany pred?
-The reducer version of any.  Returns @code{(reduced (pred? value))} if
+The reducer version of @code{any}.  Returns @code{(reduced (pred? value))} if
 any @code{(pred? value)} returns non-#f.  The identity is #f.
 
 @example
@@ -5869,7 +5869,7 @@ any @code{(pred? value)} returns non-#f.  The identity is #f.
 @end deffn
 
 @deffn {Scheme Procedure} revery pred?
-The reducer version of every.  Stops the transduction and returns
+The reducer version of @code{every}.  Stops the transduction and returns
 @code{(reduced #f)} if any @code{(pred? value)} returns #f.  If every
 @code{(pred? value)} returns true, it returns the result of the last
 invocation of @code{(pred? value)}.  The identity is #t.
@@ -5894,6 +5894,77 @@ transduction.
 @end example
 @end deffn
 
+@subheading Guile-specific reducers
+These reducers are available in the @code{(srfi srfi-171 gnu)} module,
+and are provided outside the standard described by the SRFI-171
+document.
+
+@deffn {Scheme Procedure} rfold proc seed
+The fundamental reducer. @code{rfold} creates an ad-hoc reducer based on
+a given 2-argument @var{proc}. A @var{seed} is required as the initial
+accumulator value, which also becomes the final return value in the case
+where there was no input left in the transduction.
+
+The first argument to the @var{proc} is the accumulating value, and the
+second is the current item of the transduction.
+
+Note that functions like @code{+} and @code{*} are automatically valid
+reducers, because they yield sane values even when given 0 or 1
+arguments. Other functions like @code{max} cannot be used as-is as
+reducers since they require at least 2 arguments. For functions like
+this, @code{rfold} is appropriate.
+
+@example
+;; Turning built-ins into reducers. Identical to rmax.
+(list-transduce (tfilter odd?) (rfold max 0) '(1 2 3 4 5))
+@result{} 5
+
+;; Custom lambdas into reducers. Identical to rlast.
+(list-transduce (tmap identity)
+                (rfold (lambda (_ input) input) #f)
+                '("abc" "def" "ghi"))
+@result{} "ghi"
+
+;; Track the 3 largest values in a transduction.
+(define (three-largest acc input)
+  (take (sort (cons input acc) >) 3))
+
+(list-transduce (tfilter odd?)
+                (rfold three-largest '(0 0 0))
+                '(7 1 4 2 13 5 9 2 8))
+@result{} (13 9 7)
+@end example
+@end deffn
+
+@deffn {Scheme Procedure} rfind pred?
+Find the first element in the transduction that satisfies a given
+predicate. Yields #f if no such element was found.
+
+@example
+(list-transduce (tmap identity)
+                (rfind string?)
+                '(1 c #t 4.12 "Jack" ()))
+@result{} "Jack"
+@end example
+@end deffn
+
+@deffn {Scheme Procedure} rfirst seed
+@deffnx {Scheme Procedure} rlast seed
+Yield the first (or last) value of the transduction, or the @var{seed}
+value if there is none.
+@end deffn
+
+@deffn {Scheme Procedure} rfor-each proc
+Apply @var{proc} for its side-effects to every value of the
+transduction, ignoring all results. Like its @ref{SRFI-1} cousin, yields
+@code{*unspecified*}.
+@end deffn
+
+@deffn {Scheme Procedure} rmax seed
+@deffnx {Scheme Procedure} rmin seed
+Yield the maximum (or minimum) value of the transduction, or the
+@var{seed} value if there is none.
+@end deffn
 
 @node SRFI-171 Transducers
 @subsubsection Transducers
@@ -6057,7 +6128,7 @@ Stateless.
 
 @subheading Guile-specific transducers
 These transducers are available in the @code{(srfi srfi-171 gnu)}
-library, and are provided outside the standard described by the SRFI-171
+module, and are provided outside the standard described by the SRFI-171
 document.
 
 @deffn {Scheme Procedure} tbatch reducer
@@ -6085,6 +6156,21 @@ value)}, saving it's result between iterations.
 @end example
 @end deffn
 
+@deffn {Scheme Procedure} twindow n
+
+Returns a transducer that yields @var{n}-length windows of overlapping
+values. This is different from @code{tsegment} which yields
+non-overlapping windows. If there were fewer items in the input than
+@var{n}, then this yields nothing.
+
+@example
+(list-transduce (twindow 3) rcons '(1 2 3 4 5))
+@result{} ((1 2 3) (2 3 4) (3 4 5))
+@end example
+
+Stateful.
+@end deffn
+
 
 @node SRFI-171 Helpers
 @subsubsection Helper functions for writing transducers
-- 
2.39.0


[-- Attachment #4: 0003-srfi-171-add-unit-tests-for-new-functions.patch --]
[-- Type: text/x-patch, Size: 2891 bytes --]

From 7b7538c61799fa0fa0e2fa18efba98b7de7da1ca Mon Sep 17 00:00:00 2001
From: Colin Woodbury <colin@fosskers.ca>
Date: Wed, 21 Dec 2022 09:30:50 +0900
Subject: [PATCH 3/4] srfi-171: add unit tests for new functions

These tests mainly match the examples shown in the docs.
---
 test-suite/tests/srfi-171.test | 66 ++++++++++++++++++++++++++++++----
 1 file changed, 60 insertions(+), 6 deletions(-)

diff --git a/test-suite/tests/srfi-171.test b/test-suite/tests/srfi-171.test
index 1ef7bc5f2..d1d54b2ec 100644
--- a/test-suite/tests/srfi-171.test
+++ b/test-suite/tests/srfi-171.test
@@ -207,15 +207,69 @@
             (list-transduce (tenumerate (- 1)) rcons numeric-list)))
 
   (pass-if "tbatch"
-    (equal?
-            '((0 1) (2 3) (4))
+    (equal? '((0 1) (2 3) (4))
             (list-transduce (tbatch (ttake 2) rcons) rcons numeric-list)))
 
   (pass-if "tfold"
-           (equal?
-            '(0 1 3 6 10)
-            (list-transduce (tfold +) rcons numeric-list))))
-
+    (equal? '(0 1 3 6 10)
+            (list-transduce (tfold +) rcons numeric-list)))
+
+  (pass-if "twindow: too wide of a window"
+    (equal? '()
+            (list-transduce (twindow 10) rcons '(1 2 3))))
+
+  (pass-if "twindow: acceptable window"
+    (equal? '((1 2 3) (2 3 4) (3 4 5))
+            (list-transduce (twindow 3) rcons '(1 2 3 4 5)))))
+
+(with-test-prefix "reducers"
+  (pass-if "rfold: builtin"
+    (equal? 5
+            (list-transduce (tfilter odd?) (rfold max 0) '(1 2 3 4 5))))
+
+  (pass-if "rfold: custom lambda"
+    (equal? "ghi"
+            (list-transduce (tmap identity)
+                            (rfold (lambda (_ input) input) #f)
+                            '("abc" "def" "ghi"))))
+
+  (pass-if "rfirst: empty"
+    (equal? 0
+            (list-transduce (tmap identity) (rfirst 0) '())))
+
+  (pass-if "rfirst: non-empty"
+    (equal? 1
+            (list-transduce (tmap identity) (rfirst 0) '(1 2 3))))
+
+  (pass-if "rlast: empty"
+    (equal? 0
+            (list-transduce (tfilter (lambda (_) #f)) (rlast 0) '(1 2 3))))
+
+  (pass-if "rlast: non-empty"
+    (equal? 5
+            (list-transduce (tmap identity) (rlast 0) '(1 2 3 4 5))))
+
+  (pass-if "rmax: empty"
+    (equal? 0
+            (list-transduce (tmap identity) (rmax 0) '())))
+
+  (pass-if "rmax: non-empty"
+    (equal? 31
+            (list-transduce (tmap identity) (rmax 0) '(1 2 31 4 5))))
+
+  (pass-if "rmin: empty"
+    (equal? 0
+            (list-transduce (tmap identity) (rmin 0) '())))
+
+  (pass-if "rmin: non-empty"
+    (equal? 1
+            (list-transduce (tmap identity) (rmin 1000) '(5 3 1 7 6))))
+
+  (pass-if "rfind"
+    (equal? "Jack"
+            (list-transduce (tmap identity)
+                            (rfind string?)
+                            '(1 c #t 4.12 "Jack" ())))))
 
 (with-test-prefix "x-transduce"
   (pass-if "list-transduce" 
-- 
2.39.0


[-- Attachment #5: 0004-doc-added-a-guide-for-writing-custom-reducers.patch --]
[-- Type: text/x-patch, Size: 3488 bytes --]

From 87a74d106f11680c4924befb664d7ef685c16b06 Mon Sep 17 00:00:00 2001
From: Colin Woodbury <colin@fosskers.ca>
Date: Thu, 22 Dec 2022 20:32:33 +0900
Subject: [PATCH 4/4] doc: added a guide for writing custom reducers

The guide previously explained what reducers were, but not the specifics
of how to write them yourself. This commits rectifies this.
---
 doc/ref/srfi-modules.texi | 76 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 76 insertions(+)

diff --git a/doc/ref/srfi-modules.texi b/doc/ref/srfi-modules.texi
index 6eb1a563e..e3beb2ff5 100644
--- a/doc/ref/srfi-modules.texi
+++ b/doc/ref/srfi-modules.texi
@@ -5966,6 +5966,82 @@ Yield the maximum (or minimum) value of the transduction, or the
 @var{seed} value if there is none.
 @end deffn
 
+@subheading Writing your own reducers
+If you want to reduce some values via an ordinary function that you
+already have on-hand, then @code{rfold} is all you need:
+
+@example
+;; Same as rmax.
+(list-transduce (tmap identity) (rfold max 0) '(1 2 3 4 5))
+@result{} 5
+@end example
+
+However, if you want more customized behaviour (such as early
+termination and/or arbitrary manipulation of the input values) then
+you're free to write a reducer manually. To do so, we need to write a
+function that can accept one to three arguments. We do this with
+@code{case-lambda}. Let's create a simple reducer that adds all the
+numbers in its input:
+
+@example
+(define rsum
+  (case-lambda
+    ;; This is the first case called. It establishes the on-going
+    ;; accumulator value.
+    (() 0)
+    ;; This is the last case called. Its result is the final output
+    ;; of the reduction.
+    ((result-so-far) result-so-far)
+    ;; This is the normal case. We do something to the accumulator
+    ;; and the current input.
+    ((result-so-far input) (+ result-so-far input)))
+
+(list-transduce (tfilter odd?) rsum '(1 2 3 4))
+@result{} 4
+@end example
+
+You'll notice that @code{rsum} isn't actually included in SRFI-171,
+because @code{+} already behaves exactly this way.
+
+@subsubheading Higher-order reducers
+Of course, the top-level @code{define} can also take arguments, and we
+can use these within the @code{case-lambda}. Here's how @code{rlast} is
+implemented:
+
+@example
+(define (rlast seed)
+  (case-lambda
+    (() seed)
+    ((result-so-far) result-so-far)
+    ((_ input) input)))
+
+(list-transduce (tfilter odd?) (rlast 0) '(1 2 3 4 5 6))
+@result{} 5
+@end example
+
+The @code{seed} here acts as a default for when nothing was left in the
+transduction. You're free of course to pass in whatever arguments you
+wish (including other functions) and use them as you see fit.
+
+@subsubheading Early termination
+Importing @code{(srfi srfi-171 meta)} exposes the @code{reduced}
+function, which we can use to signal to the overall transduction process
+that we're done, and no further input needs to be pulled from the data
+source. Here's @code{rfind} (already included in Guile's SRFI-171
+extensions) which escapes the iteration when some condition is met:
+
+@example
+(define (rfind pred?)
+  (case-lambda
+    (() #f)
+    ((acc) acc)
+    ((acc input) (if (pred? input) (reduced input) #f))))
+@end example
+
+Important note: calling @code{reduced} yourself like this does activate
+the final results-only branch, so any extra effects or manipulations you
+have there will also occur.
+
 @node SRFI-171 Transducers
 @subsubsection Transducers
 @cindex transducers transducers
-- 
2.39.0

Re: [PATCHv2] Extensions for SRFI-171 (Transducers)

[Ludovic Courtès]

Hi Colin and all!

These patches look like a nice addition.

First, you have the option of assigning your copyright for this
contribution (and future Guile contributions if you wish) to the FSF, or
you can choose not to:

  https://lists.gnu.org/archive/html/guile-devel/2022-10/msg00008.html

Please take a look at the message above and let us know what you’d like
to do.  If you choose not to assign copyright, you’ll have to add
copyright lines for you (or whatever entity holds copyright on your
work) in the modified files.

Overall the changes LGTM; I have minor comments and suggestions:

Colin Woodbury <colin@fosskers.ca> skribis:

> From 96856b184a507886db2c5c20323983ae125a6bdb Mon Sep 17 00:00:00 2001
> From: Colin Woodbury <colin@fosskers.ca>
> Date: Mon, 19 Dec 2022 09:39:37 +0900
> Subject: [PATCH 1/4] srfi-171: add twindow and various reducers
>
> This adds a number of reduction primitives often seen in other languages
> to Guile's SRFI-171 extensions.
>
> Most critical may be `rfold`, which could be called the fundamental
> reducer, as it's likely that all other reducers could be defined in
> terms of it (though not all are). While `tfold` already exists in
> Guile's SRFI-171 extension as a transducer, folding is in essence a
> reduction. Also without a primative like `rlast` (also introduced here),
> the results of `tfold` are difficult to consume. This is avoided by
> providing `rfold` directly as a generalised means to collapse an entire
> transduction down into a single value (i.e. the whole point of
> reducers). `rfold` is also useful for the creation of ad-hoc reducers,
> as any 2-arg function can be passed to it to fold the stream of values.
>
> `rfirst`, `rlast`, and `rfind` are common idioms and so have been added.
>
> The equivalent of `rmax` and `rmin` are easy to write manually via
> `rfold`, but they have been provided here as a convenience in the same
> spirit as `rcons`.
>
> `rfor-each` also cannot be forgotten as a classic adaptation of its
> SRFI-1 cousin.
>
> Also added is `twindow`, handy for analysing groups of adjacent items.

[...]

> From 58e7ca2718a860ca2fb5692684d6d128a7c1ae75 Mon Sep 17 00:00:00 2001
> From: Colin Woodbury <colin@fosskers.ca>
> Date: Tue, 20 Dec 2022 09:41:51 +0900
> Subject: [PATCH 2/4] doc: add new SRFI-171 reducers to the manual
>
> ---
>  doc/ref/srfi-modules.texi | 96 +++++++++++++++++++++++++++++++++++++--

[...]

> From 7b7538c61799fa0fa0e2fa18efba98b7de7da1ca Mon Sep 17 00:00:00 2001
> From: Colin Woodbury <colin@fosskers.ca>
> Date: Wed, 21 Dec 2022 09:30:50 +0900
> Subject: [PATCH 3/4] srfi-171: add unit tests for new functions
>
> These tests mainly match the examples shown in the docs.
> ---
>  test-suite/tests/srfi-171.test | 66 ++++++++++++++++++++++++++++++----

We’d squash these three commits together to provide a single
self-contained commit with code and the corresponding tests and doc.

The convention in Guile is for commit logs to follow the ChangeLog style
(see ‘git log’ for examples).  If you’re not sure how to do that, I can
do it on your behalf as a welcome present.  ;-)

> From 87a74d106f11680c4924befb664d7ef685c16b06 Mon Sep 17 00:00:00 2001
> From: Colin Woodbury <colin@fosskers.ca>
> Date: Thu, 22 Dec 2022 20:32:33 +0900
> Subject: [PATCH 4/4] doc: added a guide for writing custom reducers
>
> The guide previously explained what reducers were, but not the specifics
> of how to write them yourself. This commits rectifies this.

Nice!

> +++ b/doc/ref/srfi-modules.texi
> @@ -5966,6 +5966,82 @@ Yield the maximum (or minimum) value of the transduction, or the
>  @var{seed} value if there is none.
>  @end deffn
>  
> +@subheading Writing your own reducers
> +If you want to reduce some values via an ordinary function that you

Please capitalize section titles and leave a blank line below it (same
for the section that follows).

> +However, if you want more customized behaviour (such as early
> +termination and/or arbitrary manipulation of the input values) then
> +you're free to write a reducer manually. To do so, we need to write a

Normally we leave two spaces after end-of-sentence periods, to ease
navigation in Emacs and please Texinfo (info "(texinfo) Ending a
Sentence").

Could you send updated patches?

Thanks for your work!

Ludo’.

Re: [PATCHv3] Extensions for SRFI-171 (Transducers)

[Colin Woodbury]

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

Hi Ludovic, thanks for getting back to me! I've updated the patches as 
you've suggested. I think I've gotten the commit format correct this time.

Also, I'll opt to assign copyright to the FSF, as I've already done so 
for Emacs (and signed the papers, etc.).

Let there be transduction! Cheers,

Colin

On 1/15/23 00:09, Ludovic Courtès wrote:
> Hi Colin and all!
>
> These patches look like a nice addition.
>
> First, you have the option of assigning your copyright for this
> contribution (and future Guile contributions if you wish) to the FSF, or
> you can choose not to:
>
>    https://lists.gnu.org/archive/html/guile-devel/2022-10/msg00008.html
>
> Please take a look at the message above and let us know what you’d like
> to do.  If you choose not to assign copyright, you’ll have to add
> copyright lines for you (or whatever entity holds copyright on your
> work) in the modified files.
>
> Overall the changes LGTM; I have minor comments and suggestions:
>
> Colin Woodbury <colin@fosskers.ca> skribis:
>
>>  From 96856b184a507886db2c5c20323983ae125a6bdb Mon Sep 17 00:00:00 2001
>> From: Colin Woodbury <colin@fosskers.ca>
>> Date: Mon, 19 Dec 2022 09:39:37 +0900
>> Subject: [PATCH 1/4] srfi-171: add twindow and various reducers
>>
>> This adds a number of reduction primitives often seen in other languages
>> to Guile's SRFI-171 extensions.
>>
>> Most critical may be `rfold`, which could be called the fundamental
>> reducer, as it's likely that all other reducers could be defined in
>> terms of it (though not all are). While `tfold` already exists in
>> Guile's SRFI-171 extension as a transducer, folding is in essence a
>> reduction. Also without a primative like `rlast` (also introduced here),
>> the results of `tfold` are difficult to consume. This is avoided by
>> providing `rfold` directly as a generalised means to collapse an entire
>> transduction down into a single value (i.e. the whole point of
>> reducers). `rfold` is also useful for the creation of ad-hoc reducers,
>> as any 2-arg function can be passed to it to fold the stream of values.
>>
>> `rfirst`, `rlast`, and `rfind` are common idioms and so have been added.
>>
>> The equivalent of `rmax` and `rmin` are easy to write manually via
>> `rfold`, but they have been provided here as a convenience in the same
>> spirit as `rcons`.
>>
>> `rfor-each` also cannot be forgotten as a classic adaptation of its
>> SRFI-1 cousin.
>>
>> Also added is `twindow`, handy for analysing groups of adjacent items.
> [...]
>
>>  From 58e7ca2718a860ca2fb5692684d6d128a7c1ae75 Mon Sep 17 00:00:00 2001
>> From: Colin Woodbury <colin@fosskers.ca>
>> Date: Tue, 20 Dec 2022 09:41:51 +0900
>> Subject: [PATCH 2/4] doc: add new SRFI-171 reducers to the manual
>>
>> ---
>>   doc/ref/srfi-modules.texi | 96 +++++++++++++++++++++++++++++++++++++--
> [...]
>
>>  From 7b7538c61799fa0fa0e2fa18efba98b7de7da1ca Mon Sep 17 00:00:00 2001
>> From: Colin Woodbury <colin@fosskers.ca>
>> Date: Wed, 21 Dec 2022 09:30:50 +0900
>> Subject: [PATCH 3/4] srfi-171: add unit tests for new functions
>>
>> These tests mainly match the examples shown in the docs.
>> ---
>>   test-suite/tests/srfi-171.test | 66 ++++++++++++++++++++++++++++++----
> We’d squash these three commits together to provide a single
> self-contained commit with code and the corresponding tests and doc.
>
> The convention in Guile is for commit logs to follow the ChangeLog style
> (see ‘git log’ for examples).  If you’re not sure how to do that, I can
> do it on your behalf as a welcome present.  ;-)
>
>>  From 87a74d106f11680c4924befb664d7ef685c16b06 Mon Sep 17 00:00:00 2001
>> From: Colin Woodbury <colin@fosskers.ca>
>> Date: Thu, 22 Dec 2022 20:32:33 +0900
>> Subject: [PATCH 4/4] doc: added a guide for writing custom reducers
>>
>> The guide previously explained what reducers were, but not the specifics
>> of how to write them yourself. This commits rectifies this.
> Nice!
>
>> +++ b/doc/ref/srfi-modules.texi
>> @@ -5966,6 +5966,82 @@ Yield the maximum (or minimum) value of the transduction, or the
>>   @var{seed} value if there is none.
>>   @end deffn
>>   
>> +@subheading Writing your own reducers
>> +If you want to reduce some values via an ordinary function that you
> Please capitalize section titles and leave a blank line below it (same
> for the section that follows).
>
>> +However, if you want more customized behaviour (such as early
>> +termination and/or arbitrary manipulation of the input values) then
>> +you're free to write a reducer manually. To do so, we need to write a
> Normally we leave two spaces after end-of-sentence periods, to ease
> navigation in Emacs and please Texinfo (info "(texinfo) Ending a
> Sentence").
>
> Could you send updated patches?
>
> Thanks for your work!
>
> Ludo’.

[-- Attachment #2: 0001-srfi-171-Add-twindow-and-various-reducers.patch --]
[-- Type: text/x-patch, Size: 13023 bytes --]

From f17a7480b972e192a21c67965ce5597cb3d4379d Mon Sep 17 00:00:00 2001
From: Colin Woodbury <colin@fosskers.ca>
Date: Mon, 19 Dec 2022 09:39:37 +0900
Subject: [PATCH 1/2] srfi-171: Add twindow and various reducers

This adds a number of reduction primitives often seen in other languages
to Guile's SRFI-171 extensions.

Most critical may be `rfold`, which could be called the fundamental
reducer, as it's likely that all other reducers could be defined in
terms of it (though not all are). While `tfold` already exists in
Guile's SRFI-171 extension as a transducer, folding is in essence a
reduction. Also without a primative like `rlast` (also introduced here),
the results of `tfold` are difficult to consume. This is avoided by
providing `rfold` directly as a generalised means to collapse an entire
transduction down into a single value (i.e. the whole point of
reducers). `rfold` is also useful for the creation of ad-hoc reducers,
as any 2-arg function can be passed to it to fold the stream of values.

`rfirst`, `rlast`, and `rfind` are common idioms and so have been added.

The equivalent of `rmax` and `rmin` are easy to write manually via
`rfold`, but they have been provided here as a convenience in the same
spirit as `rcons`.

`rfor-each` also cannot be forgotten as a classic adaptation of its
SRFI-1 cousin.

Also added is `twindow`, handy for analysing groups of adjacent items.

* module/srfi/srfi-171.scm: Add new functions.
* test-suite/tests/srfi-171.test: Add tests for new functions.
* doc/ref/srfi-modules.texi: Document new functions.
---
 doc/ref/srfi-modules.texi      | 96 ++++++++++++++++++++++++++++++++--
 module/srfi/srfi-171/gnu.scm   | 87 +++++++++++++++++++++++++++++-
 test-suite/tests/srfi-171.test | 66 ++++++++++++++++++++---
 3 files changed, 236 insertions(+), 13 deletions(-)

diff --git a/doc/ref/srfi-modules.texi b/doc/ref/srfi-modules.texi
index bce5b4eac..6eb1a563e 100644
--- a/doc/ref/srfi-modules.texi
+++ b/doc/ref/srfi-modules.texi
@@ -5836,7 +5836,7 @@ identity in the reduction.
 @cindex transducers reducers
 
 @deffn {Scheme Procedure} rcons
-a simple consing reducer. When called without values, it returns its
+A simple consing reducer. When called without values, it returns its
 identity, @code{'()}.  With one value, which will be a list, it reverses
 the list (using @code{reverse!}).  When called with two values, it conses
 the second value to the first.
@@ -5848,7 +5848,7 @@ the second value to the first.
 @end deffn
 
 @deffn {Scheme Procedure} reverse-rcons
-same as rcons, but leaves the values in their reversed order.
+The same as @code{rcons}, but leaves the values in their reversed order.
 @example
 (list-transduce (tmap (lambda (x) (+ x 1))) reverse-rcons (list 0 1 2 3))
 @result{} (4 3 2 1)
@@ -5856,7 +5856,7 @@ same as rcons, but leaves the values in their reversed order.
 @end deffn
 
 @deffn {Scheme Procedure} rany pred?
-The reducer version of any.  Returns @code{(reduced (pred? value))} if
+The reducer version of @code{any}.  Returns @code{(reduced (pred? value))} if
 any @code{(pred? value)} returns non-#f.  The identity is #f.
 
 @example
@@ -5869,7 +5869,7 @@ any @code{(pred? value)} returns non-#f.  The identity is #f.
 @end deffn
 
 @deffn {Scheme Procedure} revery pred?
-The reducer version of every.  Stops the transduction and returns
+The reducer version of @code{every}.  Stops the transduction and returns
 @code{(reduced #f)} if any @code{(pred? value)} returns #f.  If every
 @code{(pred? value)} returns true, it returns the result of the last
 invocation of @code{(pred? value)}.  The identity is #t.
@@ -5894,6 +5894,77 @@ transduction.
 @end example
 @end deffn
 
+@subheading Guile-specific reducers
+These reducers are available in the @code{(srfi srfi-171 gnu)} module,
+and are provided outside the standard described by the SRFI-171
+document.
+
+@deffn {Scheme Procedure} rfold proc seed
+The fundamental reducer. @code{rfold} creates an ad-hoc reducer based on
+a given 2-argument @var{proc}. A @var{seed} is required as the initial
+accumulator value, which also becomes the final return value in the case
+where there was no input left in the transduction.
+
+The first argument to the @var{proc} is the accumulating value, and the
+second is the current item of the transduction.
+
+Note that functions like @code{+} and @code{*} are automatically valid
+reducers, because they yield sane values even when given 0 or 1
+arguments. Other functions like @code{max} cannot be used as-is as
+reducers since they require at least 2 arguments. For functions like
+this, @code{rfold} is appropriate.
+
+@example
+;; Turning built-ins into reducers. Identical to rmax.
+(list-transduce (tfilter odd?) (rfold max 0) '(1 2 3 4 5))
+@result{} 5
+
+;; Custom lambdas into reducers. Identical to rlast.
+(list-transduce (tmap identity)
+                (rfold (lambda (_ input) input) #f)
+                '("abc" "def" "ghi"))
+@result{} "ghi"
+
+;; Track the 3 largest values in a transduction.
+(define (three-largest acc input)
+  (take (sort (cons input acc) >) 3))
+
+(list-transduce (tfilter odd?)
+                (rfold three-largest '(0 0 0))
+                '(7 1 4 2 13 5 9 2 8))
+@result{} (13 9 7)
+@end example
+@end deffn
+
+@deffn {Scheme Procedure} rfind pred?
+Find the first element in the transduction that satisfies a given
+predicate. Yields #f if no such element was found.
+
+@example
+(list-transduce (tmap identity)
+                (rfind string?)
+                '(1 c #t 4.12 "Jack" ()))
+@result{} "Jack"
+@end example
+@end deffn
+
+@deffn {Scheme Procedure} rfirst seed
+@deffnx {Scheme Procedure} rlast seed
+Yield the first (or last) value of the transduction, or the @var{seed}
+value if there is none.
+@end deffn
+
+@deffn {Scheme Procedure} rfor-each proc
+Apply @var{proc} for its side-effects to every value of the
+transduction, ignoring all results. Like its @ref{SRFI-1} cousin, yields
+@code{*unspecified*}.
+@end deffn
+
+@deffn {Scheme Procedure} rmax seed
+@deffnx {Scheme Procedure} rmin seed
+Yield the maximum (or minimum) value of the transduction, or the
+@var{seed} value if there is none.
+@end deffn
 
 @node SRFI-171 Transducers
 @subsubsection Transducers
@@ -6057,7 +6128,7 @@ Stateless.
 
 @subheading Guile-specific transducers
 These transducers are available in the @code{(srfi srfi-171 gnu)}
-library, and are provided outside the standard described by the SRFI-171
+module, and are provided outside the standard described by the SRFI-171
 document.
 
 @deffn {Scheme Procedure} tbatch reducer
@@ -6085,6 +6156,21 @@ value)}, saving it's result between iterations.
 @end example
 @end deffn
 
+@deffn {Scheme Procedure} twindow n
+
+Returns a transducer that yields @var{n}-length windows of overlapping
+values. This is different from @code{tsegment} which yields
+non-overlapping windows. If there were fewer items in the input than
+@var{n}, then this yields nothing.
+
+@example
+(list-transduce (twindow 3) rcons '(1 2 3 4 5))
+@result{} ((1 2 3) (2 3 4) (3 4 5))
+@end example
+
+Stateful.
+@end deffn
+
 
 @node SRFI-171 Helpers
 @subsubsection Helper functions for writing transducers
diff --git a/module/srfi/srfi-171/gnu.scm b/module/srfi/srfi-171/gnu.scm
index 45a4e19af..c41925e8a 100644
--- a/module/srfi/srfi-171/gnu.scm
+++ b/module/srfi/srfi-171/gnu.scm
@@ -15,10 +15,17 @@
 ;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
 (define-module (srfi srfi-171 gnu)
+  #:use-module (ice-9 q)
   #:use-module (srfi srfi-171)
   #:use-module (srfi srfi-171 meta)
-  #:export (tbatch tfold))
-
+  #:export (tbatch
+            tfold
+            twindow
+            rfind
+            rfirst rlast
+            rfold
+            rfor-each
+            rmax rmin))
 
 (define tbatch
   (case-lambda
@@ -63,3 +70,79 @@
          (if (reduced? state)
              (reduced (reducer (unreduce state)))
              (r result state)))))))
+
+(define (twindow n)
+  "Yield @var{n}-length windows of overlapping values.  This is different from
+@code{tsegment} which yields non-overlapping windows. If there were
+fewer items in the input than @var{n}, then this yields nothing."
+  (when (not (and (integer? n) (positive? n)))
+        (error "argument to twindow must be a positive integer"))
+  (lambda (reducer)
+    (let ((i 0)
+          (q (make-q)))
+      (case-lambda
+        (() (reducer))
+        ((result) (reducer result))
+        ((result input)
+         (enq! q input)
+         (set! i (1+ i))
+         (cond ((< i n) result)
+               ((= i n) (reducer result (list-copy (car q))))
+               (else (deq! q)
+                     (reducer result (list-copy (car q))))))))))
+
+(define rfor-each
+  (case-lambda
+    "Run through every item in a transduction for their side effects but throw away
+all results."
+    (() *unspecified*)
+    ((acc) *unspecified*)
+    ((acc input) *unspecified*)))
+
+(define (rfirst seed)
+  "Yield the first value of the transduction, or the @var{seed} value if there is none."
+  (case-lambda
+    (() seed)
+    ((acc) acc)
+    ((_ input) (reduced input))))
+
+(define (rlast seed)
+  "Yield the final value of the transduction, or the @var{seed} value if there is none."
+  (case-lambda
+    (() seed)
+    ((acc) acc)
+    ((_ input) input)))
+
+(define (rfold f seed)
+  "The fundamental reducer. @code{rfold} creates an ad-hoc reducer based on
+a given 2-argument function. A @var{seed} is also required as the
+initial accumulator value, which also becomes the return value in case
+there was no input left in the transduction.
+
+Functions like @code{+} and @code{*} are automatically valid reducers,
+because they yield sane values even when given 0 or 1 arguments. Other
+functions like @code{max} cannot be used as-is as reducers since they
+require at least 2 arguments. For functions like this, @code{rfold} is
+appropriate."
+  (case-lambda
+    (() seed)
+    ((acc) acc)
+    ((acc input) (f acc input))))
+
+(define (rmax seed)
+  "Yield the maximum value of the transduction, or the @var{seed} value if
+there is none."
+  (rfold max seed))
+
+(define (rmin seed)
+  "Yield the minimum value of the transduction, or the @var{seed} value if
+there is none."
+  (rfold min seed))
+
+(define (rfind pred?)
+  "Find the first element in the transduction that satisfies a given predicate.
+Yields #f if no such element was found."
+  (case-lambda
+    (() #f)
+    ((acc) acc)
+    ((acc input) (if (pred? input) (reduced input) #f))))
diff --git a/test-suite/tests/srfi-171.test b/test-suite/tests/srfi-171.test
index 1ef7bc5f2..d1d54b2ec 100644
--- a/test-suite/tests/srfi-171.test
+++ b/test-suite/tests/srfi-171.test
@@ -207,15 +207,69 @@
             (list-transduce (tenumerate (- 1)) rcons numeric-list)))
 
   (pass-if "tbatch"
-    (equal?
-            '((0 1) (2 3) (4))
+    (equal? '((0 1) (2 3) (4))
             (list-transduce (tbatch (ttake 2) rcons) rcons numeric-list)))
 
   (pass-if "tfold"
-           (equal?
-            '(0 1 3 6 10)
-            (list-transduce (tfold +) rcons numeric-list))))
-
+    (equal? '(0 1 3 6 10)
+            (list-transduce (tfold +) rcons numeric-list)))
+
+  (pass-if "twindow: too wide of a window"
+    (equal? '()
+            (list-transduce (twindow 10) rcons '(1 2 3))))
+
+  (pass-if "twindow: acceptable window"
+    (equal? '((1 2 3) (2 3 4) (3 4 5))
+            (list-transduce (twindow 3) rcons '(1 2 3 4 5)))))
+
+(with-test-prefix "reducers"
+  (pass-if "rfold: builtin"
+    (equal? 5
+            (list-transduce (tfilter odd?) (rfold max 0) '(1 2 3 4 5))))
+
+  (pass-if "rfold: custom lambda"
+    (equal? "ghi"
+            (list-transduce (tmap identity)
+                            (rfold (lambda (_ input) input) #f)
+                            '("abc" "def" "ghi"))))
+
+  (pass-if "rfirst: empty"
+    (equal? 0
+            (list-transduce (tmap identity) (rfirst 0) '())))
+
+  (pass-if "rfirst: non-empty"
+    (equal? 1
+            (list-transduce (tmap identity) (rfirst 0) '(1 2 3))))
+
+  (pass-if "rlast: empty"
+    (equal? 0
+            (list-transduce (tfilter (lambda (_) #f)) (rlast 0) '(1 2 3))))
+
+  (pass-if "rlast: non-empty"
+    (equal? 5
+            (list-transduce (tmap identity) (rlast 0) '(1 2 3 4 5))))
+
+  (pass-if "rmax: empty"
+    (equal? 0
+            (list-transduce (tmap identity) (rmax 0) '())))
+
+  (pass-if "rmax: non-empty"
+    (equal? 31
+            (list-transduce (tmap identity) (rmax 0) '(1 2 31 4 5))))
+
+  (pass-if "rmin: empty"
+    (equal? 0
+            (list-transduce (tmap identity) (rmin 0) '())))
+
+  (pass-if "rmin: non-empty"
+    (equal? 1
+            (list-transduce (tmap identity) (rmin 1000) '(5 3 1 7 6))))
+
+  (pass-if "rfind"
+    (equal? "Jack"
+            (list-transduce (tmap identity)
+                            (rfind string?)
+                            '(1 c #t 4.12 "Jack" ())))))
 
 (with-test-prefix "x-transduce"
   (pass-if "list-transduce" 
-- 
2.39.0


[-- Attachment #3: 0002-doc-added-a-guide-for-writing-custom-reducers.patch --]
[-- Type: text/x-patch, Size: 3571 bytes --]

From 767c58c96c8ec63727fa8508017979ca5d64ad99 Mon Sep 17 00:00:00 2001
From: Colin Woodbury <colin@fosskers.ca>
Date: Thu, 22 Dec 2022 20:32:33 +0900
Subject: [PATCH 2/2] doc: added a guide for writing custom reducers

The guide previously explained what reducers were, but not the specifics
of how to write them yourself. This commits rectifies this.

* doc/ref/srfi-modules.texi: Explain how to write one's own reducers.
---
 doc/ref/srfi-modules.texi | 79 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 79 insertions(+)

diff --git a/doc/ref/srfi-modules.texi b/doc/ref/srfi-modules.texi
index 6eb1a563e..cb4cef5a5 100644
--- a/doc/ref/srfi-modules.texi
+++ b/doc/ref/srfi-modules.texi
@@ -5966,6 +5966,85 @@ Yield the maximum (or minimum) value of the transduction, or the
 @var{seed} value if there is none.
 @end deffn
 
+@subheading Writing your own Reducers
+
+If you want to reduce some values via an ordinary function that you
+already have on-hand, then @code{rfold} is all you need:
+
+@example
+;; Same as rmax.
+(list-transduce (tmap identity) (rfold max 0) '(1 2 3 4 5))
+@result{} 5
+@end example
+
+However, if you want more customized behaviour (such as early
+termination and/or arbitrary manipulation of the input values) then
+you're free to write a reducer manually.  To do so, we need to write a
+function that can accept one to three arguments.  We do this with
+@code{case-lambda}.  Let's create a simple reducer that adds all the
+numbers in its input:
+
+@example
+(define rsum
+  (case-lambda
+    ;; This is the first case called. It establishes the on-going
+    ;; accumulator value.
+    (() 0)
+    ;; This is the last case called. Its result is the final output
+    ;; of the reduction.
+    ((result-so-far) result-so-far)
+    ;; This is the normal case. We do something to the accumulator
+    ;; and the current input.
+    ((result-so-far input) (+ result-so-far input)))
+
+(list-transduce (tfilter odd?) rsum '(1 2 3 4))
+@result{} 4
+@end example
+
+You'll notice that @code{rsum} isn't actually included in SRFI-171,
+because @code{+} already behaves exactly this way.
+
+@subsubheading Higher-order Reducers
+
+Of course, the top-level @code{define} can also take arguments, and we
+can use these within the @code{case-lambda}.  Here's how @code{rlast} is
+implemented:
+
+@example
+(define (rlast seed)
+  (case-lambda
+    (() seed)
+    ((result-so-far) result-so-far)
+    ((_ input) input)))
+
+(list-transduce (tfilter odd?) (rlast 0) '(1 2 3 4 5 6))
+@result{} 5
+@end example
+
+The @code{seed} here acts as a default for when nothing was left in the
+transduction.  You're free of course to pass in whatever arguments you
+wish (including other functions) and use them as you see fit.
+
+@subsubheading Early Termination
+
+Importing @code{(srfi srfi-171 meta)} exposes the @code{reduced}
+function, which we can use to signal to the overall transduction process
+that we're done, and no further input needs to be pulled from the data
+source.  Here's @code{rfind} (already included in Guile's SRFI-171
+extensions) which escapes the iteration when some condition is met:
+
+@example
+(define (rfind pred?)
+  (case-lambda
+    (() #f)
+    ((acc) acc)
+    ((acc input) (if (pred? input) (reduced input) #f))))
+@end example
+
+Important note: calling @code{reduced} yourself like this does activate
+the final results-only branch, so any extra effects or manipulations you
+have there will also occur.
+
 @node SRFI-171 Transducers
 @subsubsection Transducers
 @cindex transducers transducers
-- 
2.39.0

Re: [PATCHv3] Extensions for SRFI-171 (Transducers)

[Ludovic Courtès]

Hi Colin,

Colin Woodbury <colin@fosskers.ca> skribis:

> Hi Ludovic, thanks for getting back to me! I've updated the patches as
> you've suggested. I think I've gotten the commit format correct this
> time.

Yup, it’s looks perfect!

> Also, I'll opt to assign copyright to the FSF, as I've already done so
> for Emacs (and signed the papers, etc.).

Alright.  In that case, could you send the form at
<https://git.savannah.gnu.org/cgit/gnulib.git/plain/doc/Copyright/request-assign.future>
to assign@gnu.org (as noted at the top).  If you don’t get a reply
within two weeks, please let Andy and/or myself know and we’ll ping
them.

I know this is frustrating but I’ll wait for their notification to push
the changes (on the bright side, it’s a one-time delay).

> Let there be transduction! Cheers,

Definitely.  :-)

Thanks!

Ludo’.

Re: [PATCHv3] Extensions for SRFI-171 (Transducers)

[Colin Woodbury]

Hi Ludovic,

Sorry if I wasn't clear - I have alright assigned copyright to the FSF 
(about 1.5 years ago). Things should be good to go, unless I've 
misunderstood.

Cheers,

Colin

On 1/24/23 07:17, Ludovic Courtès wrote:
> Hi Colin,
>
> Colin Woodbury <colin@fosskers.ca> skribis:
>
>> Hi Ludovic, thanks for getting back to me! I've updated the patches as
>> you've suggested. I think I've gotten the commit format correct this
>> time.
> Yup, it’s looks perfect!
>
>> Also, I'll opt to assign copyright to the FSF, as I've already done so
>> for Emacs (and signed the papers, etc.).
> Alright.  In that case, could you send the form at
> <https://git.savannah.gnu.org/cgit/gnulib.git/plain/doc/Copyright/request-assign.future>
> to assign@gnu.org (as noted at the top).  If you don’t get a reply
> within two weeks, please let Andy and/or myself know and we’ll ping
> them.
>
> I know this is frustrating but I’ll wait for their notification to push
> the changes (on the bright side, it’s a one-time delay).
>
>> Let there be transduction! Cheers,
> Definitely.  :-)
>
> Thanks!
>
> Ludo’.

Re: [PATCHv3] Extensions for SRFI-171 (Transducers)

[Ludovic Courtès]

Hi Colin,

Colin Woodbury <colin@fosskers.ca> skribis:

> Sorry if I wasn't clear - I have alright assigned copyright to the FSF
> (about 1.5 years ago). Things should be good to go, unless I've
> misunderstood.

I checked the records on fencepost.gnu.org and AFAICS, you assigned
copyright for Emacs only (copyright assignments are for a single GNU
package), so you will need to do the paperwork for Guile this time.

Thanks in advance.  :-)

Ludo’.

Re: [PATCHv3] Extensions for SRFI-171 (Transducers)

[Colin Woodbury]

Hi! Forgive the delay; my copyright assignment for Guile has finally 
gone through. Please let me know if the patches are still good!

Colin

On 1/24/23 18:07, Ludovic Courtès wrote:
> Hi Colin,
>
> Colin Woodbury <colin@fosskers.ca> skribis:
>
>> Sorry if I wasn't clear - I have alright assigned copyright to the FSF
>> (about 1.5 years ago). Things should be good to go, unless I've
>> misunderstood.
> I checked the records on fencepost.gnu.org and AFAICS, you assigned
> copyright for Emacs only (copyright assignments are for a single GNU
> package), so you will need to do the paperwork for Guile this time.
>
> Thanks in advance.  :-)
>
> Ludo’.

Re: [PATCHv3] Extensions for SRFI-171 (Transducers)

[Colin Woodbury]

Hi again, any thoughts on these SRFI-171 extensions?

On 5/18/23 09:36, Colin Woodbury wrote:
> Hi! Forgive the delay; my copyright assignment for Guile has finally 
> gone through. Please let me know if the patches are still good!
>
> Colin
>
> On 1/24/23 18:07, Ludovic Courtès wrote:
>> Hi Colin,
>>
>> Colin Woodbury <colin@fosskers.ca> skribis:
>>
>>> Sorry if I wasn't clear - I have alright assigned copyright to the FSF
>>> (about 1.5 years ago). Things should be good to go, unless I've
>>> misunderstood.
>> I checked the records on fencepost.gnu.org and AFAICS, you assigned
>> copyright for Emacs only (copyright assignments are for a single GNU
>> package), so you will need to do the paperwork for Guile this time.
>>
>> Thanks in advance.  :-)
>>
>> Ludo’.

Re: [PATCHv3] Extensions for SRFI-171 (Transducers)

[Linus Björnstam]

Hi!

I have finally started getting some computer time again, and I will make sure to get this into some kind of extra library in the official SRFI repo. 

It will not be official, but maybe for a future SRFI based on SRFI 171.
 

-- 
  Linus Björnstam

On Wed, 28 Jun 2023, at 14:27, Colin Woodbury wrote:
> Hi again, any thoughts on these SRFI-171 extensions?
>
> On 5/18/23 09:36, Colin Woodbury wrote:
>> Hi! Forgive the delay; my copyright assignment for Guile has finally 
>> gone through. Please let me know if the patches are still good!
>>
>> Colin
>>
>> On 1/24/23 18:07, Ludovic Courtès wrote:
>>> Hi Colin,
>>>
>>> Colin Woodbury <colin@fosskers.ca> skribis:
>>>
>>>> Sorry if I wasn't clear - I have alright assigned copyright to the FSF
>>>> (about 1.5 years ago). Things should be good to go, unless I've
>>>> misunderstood.
>>> I checked the records on fencepost.gnu.org and AFAICS, you assigned
>>> copyright for Emacs only (copyright assignments are for a single GNU
>>> package), so you will need to do the paperwork for Guile this time.
>>>
>>> Thanks in advance.  :-)
>>>
>>> Ludo’.

Re: [PATCHv3] Extensions for SRFI-171 (Transducers)

[Colin Woodbury]

On 8/13/23 04:37, Linus Björnstam wrote:
> Hi!
> 
> I have finally started getting some computer time again, and I will make sure to get this into some kind of extra library in the official SRFI repo.
> 
> It will not be official, but maybe for a future SRFI based on SRFI 171.
>   
> 

Hi Linus, good to hear from you. See also my recent work on Transducers 
in general here:

https://sr.ht/~fosskers/transducers/sources

My goal is to unify the Transducers interface across as many Lisps as 
possible. Note that I've added more primitives there than what I 
proposed to add to Guile with these patches. Eventually my hope is that 
my unification work can identify all the main primitives and expected 
behaviour of Transducers, and thus become the basis for a successor to 
SFRI-171 for Scheme.

Cheers!

Re: [PATCHv3] Extensions for SRFI-171 (Transducers)

[Ludovic Courtès]

Hi Colin,

Colin Woodbury <colin@fosskers.ca> skribis:

> Hi again, any thoughts on these SRFI-171 extensions?

Looong ago, before we waited for copyright assignment to be on file, I
made minor suggestions on the patch, which I think you haven’t responded
to:

  https://lists.gnu.org/archive/html/guile-devel/2023-01/msg00044.html

Could you take a look?

Apologies for the delays, we’re pioneering “slow dev” I guess.  :-)

Thanks,
Ludo’.

Re: [PATCHv3] Extensions for SRFI-171 (Transducers)

[Colin Woodbury]

On 8/18/23 19:03, Ludovic Courtès wrote:
> Apologies for the delays, we’re pioneering “slow dev” I guess.  :-)

Haha no issue at all!

 > Could you take a look?

In that case, please hold on the patch. I am currently "rounding out" 
the "one true Transducer API" in several other Lisps, and am close to 
what I consider a representative set of the desirable primitives a 
developer would want out-of-the-box. One I'm done there, I will return 
to this and a few things that are currently missing.

The other Lisps have also achieved a zip-like pattern (i.e. passing 
multiple collections to `transduce` at the same time, thus allowing 
functions like `map` to operate on multiple inputs).

There is also the issue of SRFI-171's disambiguated `transduce-list`, 
`transduce-vector`, etc., since Scheme has no `defgeneric` by default. 
Guile _does_ however, so we could write a generic `transduce` in Guile's 
own extensions. In general though it would be nice if SRFI-XYZ 
"Transducers Redux" could depend on a standardized generics system, but 
alas.

Anyway, thanks for getting back to me. I'll return to this effort in due 
time.

Cheers,

Colin

Re: [PATCHv3] Extensions for SRFI-171 (Transducers)

[Ludovic Courtès]

Hello,

Colin Woodbury <colin@fosskers.ca> skribis:

> In that case, please hold on the patch. I am currently "rounding out"
> the "one true Transducer API" in several other Lisps, and am close to
> what I consider a representative set of the desirable primitives a
> developer would want out-of-the-box. One I'm done there, I will return
> to this and a few things that are currently missing.
>
> The other Lisps have also achieved a zip-like pattern (i.e. passing
> multiple collections to `transduce` at the same time, thus allowing
> functions like `map` to operate on multiple inputs).
>
> There is also the issue of SRFI-171's disambiguated `transduce-list`,
> `transduce-vector`, etc., since Scheme has no `defgeneric` by
> default. Guile _does_ however, so we could write a generic `transduce`
> in Guile's own extensions. In general though it would be nice if
> SRFI-XYZ "Transducers Redux" could depend on a standardized generics
> system, but alas.
>
> Anyway, thanks for getting back to me. I'll return to this effort in
> due time.

Alright, ping me when you feel ready!

Thanks,
Ludo’.