bug#67456: [PATCH] seq.el: Add functions for mapping over subsequences

bug#67456: [PATCH] seq.el: Add functions for mapping over subsequences

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

Hello,

The attached features work like `cl-maplist` and `cl-mapl`, applying 
functions to a sequence and to the remaining parts of a sequence.  For 
example, `(seq-mapsub #'identity [1 2 3])` returns `([1 2 3] [2 3] [3])`.

The patch adds a `seq-mapsub`, `seq-dosub`, and a `seq-doseqsub`, 
similar to `seq-map`, `seq-do`, and `seq-doseq`, respectively.

I was looking for an equivalent for vectors of `cl-maplist`, `cl-mapl`, 
and `cl-loop`'s `for VAR on LIST`, and think that these would be useful 
additions.

To get the sub-sequences, the code uses `seq-rest` and stops when the 
returned sub-sequence is empty according to `seq-empty-p`.  This is 
similar to how I would do it for a list, using `cdr` and `null`, but is 
that a good way to do it for arrays and other sequences?

Thank you.

[-- Attachment #2: 0001-Create-seq-functions-for-mapping-over-subsequences.patch --]
[-- Type: text/x-patch, Size: 6463 bytes --]

From 2f07383470b90009c78b0459ee09fcc513e0e12f Mon Sep 17 00:00:00 2001
From: Earl Hyatt <okamsn@protonmail.com>
Date: Sun, 26 Nov 2023 11:20:28 -0500
Subject: [PATCH] Create seq functions for mapping over subsequences.

These functions are similar to 'cl-maplist' and 'cl-mapl'.

* lisp/emacs-lisp/seq.el (seq-mapsub, seq-dosub, seq-doseqsub):
Add functions for mapping over sub-sequences, like in 'cl-maplist',
similar to the existing 'seq-map', 'seq-do', and 'seq-doseq'.

* test/lisp/emacs-lisp/seq-tests.el (test-seq-mapsub, test-seq-dosub)
(test-seq-doseqsub): Add tests for the above functions.

* doc/lispref/sequences.texi (Sequence Functions): Describe the
functions.
---
 doc/lispref/sequences.texi        | 27 ++++++++++++++++++++
 lisp/emacs-lisp/seq.el            | 41 +++++++++++++++++++++++++++++++
 test/lisp/emacs-lisp/seq-tests.el | 36 +++++++++++++++++++++++++++
 3 files changed, 104 insertions(+)

diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi
index c9c6bb31350..e42f84be2b5 100644
--- a/doc/lispref/sequences.texi
+++ b/doc/lispref/sequences.texi
@@ -594,6 +594,15 @@ Sequence Functions
 @var{sequence}.
 @end defun
 
+@defun seq-dosub function sequence
+  This function applies @var{function} to @var{sequence} and its
+sub-sequences in turn (presumably for side effects), and returns
+@var{sequence}.  The first sequence used is @var{sequence}, the second
+sequence used is everything in @var{sequence} after the first element,
+the third sequence used is everything after the second element, and so
+on.
+@end defun
+
 @defun seq-map function sequence
   This function returns the result of applying @var{function} to each
 element of @var{sequence}.  The returned value is a list.
@@ -610,6 +619,19 @@ Sequence Functions
 @end example
 @end defun
 
+@defun seq-mapsub function sequence
+  This function returns the result of applying @var{function} to
+@var{sequence} and its sub-sequences, like in @code{seq-dosub}.  The
+returned value is a list.
+
+@example
+@group
+(seq-mapsub #'identity [1 2 3])
+@result{} ([1 2 3] [2 3] [3])
+@end group
+@end example
+@end defun
+
 @defun seq-map-indexed function sequence
   This function returns the result of applying @var{function} to each
 element of @var{sequence} and its index within @var{seq}.  The
@@ -1152,6 +1174,11 @@ Sequence Functions
 primarily useful for side-effects.
 @end defmac
 
+@defmac seq-doseqsub (var sequence) body@dots{}
+  This macro is like @code{seq-doseq}, except that it iterates
+over the sequence and its sub-sequences, like in @code{seq-mapsub}.
+@end defmac
+
 @anchor{seq-let}
 @defmac seq-let var-sequence val-sequence body@dots{}
 @cindex sequence destructuring
diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
index 346250c1d35..5b9eb29a3e2 100644
--- a/lisp/emacs-lisp/seq.el
+++ b/lisp/emacs-lisp/seq.el
@@ -235,6 +235,47 @@ seq-mapn
       (setq sequences (seq-map #'cdr sequences)))
     (nreverse result)))
 
+(cl-defgeneric seq-mapsub (function sequence)
+  "Return the result of applying FUNCTION to SEQUENCE and its sub-sequences.
+
+The first sequence is the entire sequence, the second sequence
+is everything after the first element, the third sequence
+is everything after the second element, and so on."
+  (let ((result nil))
+    (while (not (seq-empty-p sequence))
+      (push (funcall function sequence)
+            result)
+      (setq sequence (seq-rest sequence)))
+    (nreverse result)))
+
+(cl-defgeneric seq-dosub (function sequence)
+  "Loop over SEQUENCE and its sub-sequences.
+
+Presumably, FUNCTION has useful side effects.
+Return SEQUENCE.
+
+The first sequence is the entire sequence, the second sequence
+is everything after the first element, the third sequence
+is everything after the second element, and so on."
+  (let ((orig sequence))
+    (while (not (seq-empty-p sequence))
+      (funcall function sequence)
+      (setq sequence (seq-rest sequence)))
+    orig))
+
+(defmacro seq-doseqsub (spec &rest body)
+  "Loop over SEQUENCE, evaluating BODY with VAR bound to its sub-sequences.
+
+The first sequence is the entire sequence, the second sequence
+is everything after the first element, the third sequence
+is everything after the second element, and so on.
+
+\(fn (VAR SEQUENCE) BODY...)"
+  (declare (indent 1) (debug ((symbolp form &optional form) body)))
+  `(seq-dosub (lambda (,(car spec))
+                ,@body)
+              ,(cadr spec)))
+
 (cl-defgeneric seq-drop (sequence n)
   "Remove the first N elements of SEQUENCE and return the resulting sequence.
 The result is a sequence of the same type as SEQUENCE.
diff --git a/test/lisp/emacs-lisp/seq-tests.el b/test/lisp/emacs-lisp/seq-tests.el
index 71ff991c215..1c117d06974 100644
--- a/test/lisp/emacs-lisp/seq-tests.el
+++ b/test/lisp/emacs-lisp/seq-tests.el
@@ -121,6 +121,42 @@ test-seq-do-indexed
       (should (equal (seq-elt result 1) '(5 1)))
       (should (equal (seq-elt result 2) '(4 0))))))
 
+(ert-deftest test-seq-mapsub ()
+  (should (equal (seq-mapsub #'identity [1 2 3])
+                 '([1 2 3] [2 3] [3])))
+  (should (equal (seq-mapsub #'identity '(1 2 3))
+                 '((1 2 3) (2 3) (3)))))
+
+(ert-deftest test-seq-dosub ()
+  (should (equal (seq-dosub #'identity [1 2 3])
+                 [1 2 3]))
+  (should (equal (seq-dosub #'identity '(1 2 3))
+                 '(1 2 3)))
+  (should (equal (let ((res (list)))
+                   (seq-dosub (lambda (x)
+                                (push x res))
+                              [1 2 3])
+                   (nreverse res))
+                 '([1 2 3] [2 3] [3])))
+  (should (equal (let ((res (list)))
+                   (seq-dosub (lambda (x)
+                                (push x res))
+                              '(1 2 3))
+                   (nreverse res))
+                 '((1 2 3) (2 3) (3)))))
+
+(ert-deftest test-seq-doseqsub ()
+  (should (equal (let ((res (list)))
+                   (seq-doseqsub (x [1 2 3])
+                     (push x res))
+                   (nreverse res))
+                 '([1 2 3] [2 3] [3])))
+  (should (equal (let ((res (list)))
+                   (seq-doseqsub (x '(1 2 3))
+                     (push x res))
+                   (nreverse res))
+                 '((1 2 3) (2 3) (3)))))
+
 (ert-deftest test-seq-filter ()
   (with-test-sequences (seq '(6 7 8 9 10))
     (should (equal (seq-filter #'test-sequences-evenp seq) '(6 8 10)))
-- 
2.34.1

bug#67456: [PATCH] seq.el: Add functions for mapping over subsequences

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

Okamsn wrote:
> Hello,
> 
> The attached features work like `cl-maplist` and `cl-mapl`, applying
> functions to a sequence and to the remaining parts of a sequence.  For
> example, `(seq-mapsub #'identity [1 2 3])` returns `([1 2 3] [2 3] [3])`.
> 
> The patch adds a `seq-mapsub`, `seq-dosub`, and a `seq-doseqsub`,
> similar to `seq-map`, `seq-do`, and `seq-doseq`, respectively.
> 
> I was looking for an equivalent for vectors of `cl-maplist`, `cl-mapl`,
> and `cl-loop`'s `for VAR on LIST`, and think that these would be useful
> additions.
> 
> To get the sub-sequences, the code uses `seq-rest` and stops when the
> returned sub-sequence is empty according to `seq-empty-p`.  This is
> similar to how I would do it for a list, using `cdr` and `null`, but is
> that a good way to do it for arrays and other sequences?
> 
> Thank you.

I've updated the patch to only add the one `seq-mapsub` function, to be 
more like `seq-mapn` and `seq-mapcat`, and to add an optimized version 
for lists.

Would you like anything changed?

Thank you.

[-- Attachment #2: v2-0001-Create-function-seq-mapsub-for-mapping-over-subse.patch --]
[-- Type: text/x-patch, Size: 4132 bytes --]

From ea8ee51977c0a583bc374856af633945144bc7dd Mon Sep 17 00:00:00 2001
From: Earl Hyatt <okamsn@protonmail.com>
Date: Sun, 26 Nov 2023 11:20:28 -0500
Subject: [PATCH v2] Create function 'seq-mapsub' for mapping over
 subsequences.

This function is similar to 'cl-maplist'.

* lisp/emacs-lisp/seq.el (seq-mapsub): Add generic function for
mapping over sub-sequences, like in 'cl-maplist'.  Add optimized
implementation for lists.

* test/lisp/emacs-lisp/seq-tests.el (test-seq-mapsub): Add tests for
the above functions.

* doc/lispref/sequences.texi (Sequence Functions): Describe the
function.
---
 doc/lispref/sequences.texi        | 20 ++++++++++++++++++++
 lisp/emacs-lisp/seq.el            | 25 +++++++++++++++++++++++++
 test/lisp/emacs-lisp/seq-tests.el | 10 ++++++++++
 3 files changed, 55 insertions(+)

diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi
index c9c6bb31350..1234f51e188 100644
--- a/doc/lispref/sequences.texi
+++ b/doc/lispref/sequences.texi
@@ -644,6 +644,26 @@ Sequence Functions
 @end example
 @end defun
 
+@defun seq-mapsub function sequence
+  This function returns the result of applying @var{function} to
+@var{sequence} and its sub-sequences.  The first sequence used is
+@var{sequence}, the second sequence used is everything in
+@var{sequence} after the first element, the third sequence used is
+everything after the second element, and so on. The returned value is
+a list. If @var{sequence} is empty, then the returned list is empty.
+
+@example
+@group
+(seq-mapsub #'identity [1 2 3])
+@result{} ([1 2 3] [2 3] [3])
+@end group
+@group
+(seq-mapsub #'identity [])
+@result{} nil
+@end group
+@end example
+@end defun
+
 @defun seq-filter predicate sequence
 @cindex filtering sequences
   This function returns a list of all the elements in @var{sequence}
diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
index 346250c1d35..e9421d7a5db 100644
--- a/lisp/emacs-lisp/seq.el
+++ b/lisp/emacs-lisp/seq.el
@@ -235,6 +235,22 @@ seq-mapn
       (setq sequences (seq-map #'cdr sequences)))
     (nreverse result)))
 
+(cl-defgeneric seq-mapsub (function sequence)
+  "Return the result of applying FUNCTION to SEQUENCE and its sub-sequences.
+
+If SEQUENCE is empty, nil is returned.
+
+The first sequence used is SEQUENCE, the second sequence used is
+everything in SEQUENCE after the first element, the third
+sequence used is everything after the second element, and so
+on."
+  (let ((result nil))
+    (while (not (seq-empty-p sequence))
+      (push (funcall function sequence)
+            result)
+      (setq sequence (seq-rest sequence)))
+    (nreverse result)))
+
 (cl-defgeneric seq-drop (sequence n)
   "Remove the first N elements of SEQUENCE and return the resulting sequence.
 The result is a sequence of the same type as SEQUENCE.
@@ -671,6 +687,15 @@ seq-drop-while
 (cl-defmethod seq-empty-p ((list list))
   "Optimized implementation of `seq-empty-p' for lists."
   (null list))
+
+(cl-defmethod seq-mapsub (function (list list))
+  "Optimized implementation of `seq-mapsub' for lists."
+  (let ((result nil))
+    (while list
+      (push (funcall function list)
+            result)
+      (setq list (cdr list)))
+    (nreverse result)))
 \f
 
 (defun seq--into-list (sequence)
diff --git a/test/lisp/emacs-lisp/seq-tests.el b/test/lisp/emacs-lisp/seq-tests.el
index 71ff991c215..fa6f9efa762 100644
--- a/test/lisp/emacs-lisp/seq-tests.el
+++ b/test/lisp/emacs-lisp/seq-tests.el
@@ -121,6 +121,16 @@ test-seq-do-indexed
       (should (equal (seq-elt result 1) '(5 1)))
       (should (equal (seq-elt result 2) '(4 0))))))
 
+(ert-deftest test-seq-mapsub ()
+  (should (equal (seq-mapsub #'identity [1 2 3])
+                 '([1 2 3] [2 3] [3])))
+  (should (equal (seq-mapsub #'identity '(1 2 3))
+                 '((1 2 3) (2 3) (3))))
+  (should (equal (seq-mapsub #'identity nil)
+                 nil))
+  (should (equal (seq-mapsub #'identity [])
+                 nil)))
+
 (ert-deftest test-seq-filter ()
   (with-test-sequences (seq '(6 7 8 9 10))
     (should (equal (seq-filter #'test-sequences-evenp seq) '(6 8 10)))
-- 
2.34.1

bug#67456: [PATCH] seq.el: Add functions for mapping over subsequences

[Augusto Stoffel]

On Tue, 28 Nov 2023 at 01:29, Okamsn via "Bug reports for GNU Emacs, the Swiss army knife of text editors" wrote:

> Okamsn wrote:
>> Hello,
>> 
>> The attached features work like `cl-maplist` and `cl-mapl`, applying
>> functions to a sequence and to the remaining parts of a sequence.  For
>> example, `(seq-mapsub #'identity [1 2 3])` returns `([1 2 3] [2 3] [3])`.
>> 
>> The patch adds a `seq-mapsub`, `seq-dosub`, and a `seq-doseqsub`,
>> similar to `seq-map`, `seq-do`, and `seq-doseq`, respectively.
>> 
>> I was looking for an equivalent for vectors of `cl-maplist`, `cl-mapl`,
>> and `cl-loop`'s `for VAR on LIST`, and think that these would be useful
>> additions.
>> 
>> To get the sub-sequences, the code uses `seq-rest` and stops when the
>> returned sub-sequence is empty according to `seq-empty-p`.  This is
>> similar to how I would do it for a list, using `cdr` and `null`, but is
>> that a good way to do it for arrays and other sequences?
>> 
>> Thank you.
>
> I've updated the patch to only add the one `seq-mapsub` function, to be 
> more like `seq-mapn` and `seq-mapcat`, and to add an optimized version 
> for lists.
>
> Would you like anything changed?
>
> Thank you.

This operation has quadratic complexity for anything other than regular
linked lists.  I'm not sure it's a good idea to add it to a generic
sequence library...

bug#67456: [PATCH] seq.el: Add functions for mapping over subsequences

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Augusto Stoffel wrote:
> This operation has quadratic complexity for anything other than regular
> linked lists.  I'm not sure it's a good idea to add it to a generic
> sequence library...


Thank you for the feedback.

Do you know whether there is a better way to implement the idea for 
arrays? Is there a way to apply a function to a portion of the array 
without copying the sub-sequences, if that is what you mean?

bug#67456: [PATCH] seq.el: Add functions for mapping over subsequences

[Philip Kaludercic]

Okamsn <okamsn@protonmail.com> writes:

> Hello,
>
> The attached features work like `cl-maplist` and `cl-mapl`, applying 
> functions to a sequence and to the remaining parts of a sequence.  For 
> example, `(seq-mapsub #'identity [1 2 3])` returns `([1 2 3] [2 3] [3])`.
>
> The patch adds a `seq-mapsub`, `seq-dosub`, and a `seq-doseqsub`, 
> similar to `seq-map`, `seq-do`, and `seq-doseq`, respectively.

How about adding a custom sequence type, that operates on sub-sequences
as elements?

--8<---------------cut here---------------start------------->8---
(cl-defstruct (subseq (:constructor seq-make-subseq (seq))) seq)

(cl-defmethod seq-elt ((seq subseq) n)
  (seq-subseq (subseq-seq seq) n (seq-length seq)))

(cl-defmethod seq-length ((seq subseq))
  (seq-length (subseq-seq seq)))

(cl-defmethod seq-do (fn (seq subseq))
  (seq-do fn (subseq-seq seq)))

;; etc.
--8<---------------cut here---------------end--------------->8---

It might not be that efficient either, but at least it doesn't require
more functions.