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

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 67456 in the body.
You can then email your comments to 67456 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Okamsn <okamsn <at> protonmail.com>
To: bug-gnu-emacs <at> gnu.org, Nicolas Petton <nicolas <at> petton.fr>
Subject: [PATCH] seq.el: Add functions for mapping over subsequences
Date: Sun, 26 Nov 2023 17:17:35 +0000

[Message part 1 (text/plain, inline)]

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.

[0001-Create-seq-functions-for-mapping-over-subsequences.patch (text/x-patch, attachment)]

Message #8 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Okamsn <okamsn <at> protonmail.com>
To: bug-gnu-emacs <at> gnu.org, Nicolas Petton <nicolas <at> petton.fr>
Subject: Re: [PATCH] seq.el: Add functions for mapping over subsequences
Date: Tue, 28 Nov 2023 01:29:14 +0000

[Message part 1 (text/plain, inline)]

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.

[v2-0001-Create-function-seq-mapsub-for-mapping-over-subse.patch (text/x-patch, attachment)]

Message #11 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Augusto Stoffel <arstoffel <at> gmail.com>
To: Okamsn via "Bug reports for GNU Emacs, the Swiss army knife of text
 editors" <bug-gnu-emacs <at> gnu.org>
Cc: Okamsn <okamsn <at> protonmail.com>, nicolas <at> petton.fr, 67456 <at> debbugs.gnu.org
Subject: Re: bug#67456: [PATCH] seq.el: Add functions for mapping over
 subsequences
Date: Fri, 01 Dec 2023 21:14:13 +0100

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...

Message #17 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Okamsn <okamsn <at> protonmail.com>
To: Augusto Stoffel <arstoffel <at> gmail.com>,
 "Okamsn via \"Bug reports for GNU Emacs,
 the Swiss army knife of text editors\"" <bug-gnu-emacs <at> gnu.org>
Cc: nicolas <at> petton.fr, 67456 <at> debbugs.gnu.org
Subject: Re: bug#67456: [PATCH] seq.el: Add functions for mapping over
 subsequences
Date: Sun, 03 Dec 2023 01:25:25 +0000

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?

Message #23 received at 67456 <at> debbugs.gnu.org (full text, mbox):

From: Philip Kaludercic <philipk <at> posteo.net>
To: Okamsn <okamsn <at> protonmail.com>
Cc: nicolas <at> petton.fr, 67456 <at> debbugs.gnu.org
Subject: Re: bug#67456: [PATCH] seq.el: Add functions for mapping over
 subsequences
Date: Mon, 25 Dec 2023 20:26:18 +0000

Okamsn <okamsn <at> 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.

Message #28 received at 67456 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Kangas <stefankangas <at> gmail.com>
To: Okamsn <okamsn <at> protonmail.com>
Cc: nicolas <at> petton.fr, arstoffel <at> gmail.com, 67456 <at> debbugs.gnu.org
Subject: Re: bug#67456: [PATCH] seq.el: Add functions for mapping over
 subsequences
Date: Sun, 23 Feb 2025 01:04:21 +0000

Okamsn <okamsn <at> protonmail.com> writes:

> 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?

Hmm, it seems like this issue got stuck due to problems with algorithmic
complexity.  Performance is a real issue in seq.el, so I think we should
solve that before we consider installing anything.

Are you still working on this?

Message #33 received at 67456 <at> debbugs.gnu.org (full text, mbox):

From: Okamsn <okamsn <at> protonmail.com>
To: Stefan Kangas <stefankangas <at> gmail.com>
Cc: nicolas <at> petton.fr, arstoffel <at> gmail.com, 67456 <at> debbugs.gnu.org
Subject: Re: bug#67456: [PATCH] seq.el: Add functions for mapping over
 subsequences
Date: Tue, 25 Feb 2025 02:16:01 +0000

Stefan Kangas wrote:
> Okamsn <okamsn <at> protonmail.com> writes:
> 
>> 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?
> 
> Hmm, it seems like this issue got stuck due to problems with algorithmic
> complexity.  Performance is a real issue in seq.el, so I think we should
> solve that before we consider installing anything.
> 
> Are you still working on this?

I am no longer working on this.  For some things, I opted to use the 
Stream package from ELPA, which now better supports arrays.  Although it 
has the same problem when first traversing a seq.el sequence, it avoids 
recreating things for the sub-sequence.

I am fine with this bug being closed.

Message #38 received at 67456-done <at> debbugs.gnu.org (full text, mbox):

From: Stefan Kangas <stefankangas <at> gmail.com>
To: Okamsn <okamsn <at> protonmail.com>
Cc: nicolas <at> petton.fr, arstoffel <at> gmail.com, 67456-done <at> debbugs.gnu.org
Subject: Re: bug#67456: [PATCH] seq.el: Add functions for mapping over
 subsequences
Date: Mon, 24 Feb 2025 20:39:31 -0600

Okamsn <okamsn <at> protonmail.com> writes:

> Stefan Kangas wrote:
>> Okamsn <okamsn <at> protonmail.com> writes:
>>
>>> 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?
>>
>> Hmm, it seems like this issue got stuck due to problems with algorithmic
>> complexity.  Performance is a real issue in seq.el, so I think we should
>> solve that before we consider installing anything.
>>
>> Are you still working on this?
>
> I am no longer working on this.  For some things, I opted to use the
> Stream package from ELPA, which now better supports arrays.  Although it
> has the same problem when first traversing a seq.el sequence, it avoids
> recreating things for the sub-sequence.
>
> I am fine with this bug being closed.

Thanks, I guess that means that it's unlikely that we'll make more
progress here.  I'm therefore closing this bug report.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.