GNU bug report logs - #78656
[PATCH] Add new reduction primitives `fold-left' and `fold-right'

Previous Next

To reply to this bug, email your comments to 78656 AT debbugs.gnu.org.

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

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

From: Zach Shaftel <zach <at> shaf.tel>
To: bug-gnu-emacs <at> gnu.org
Subject: [PATCH] Add new reduction primitives `fold-left' and `fold-right'
Date: Sat, 31 May 2025 22:35:20 -0400

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

Tags: patch

this patch adds left and right sequence reduction functions in C, along
with tests for them. i don't know if this is the sort of thing the
maintainers actually would want to merge, but i figured i would just
submit it and hear your feedback. would also appreciate any stylistic
feedback, for future patch submissions.


In GNU Emacs 31.0.50 (build 1, x86_64-pc-linux-gnu, GTK+ Version
 3.24.49, cairo version 1.18.4) of 2025-05-27 built on bigbox
Repository revision: 75acd19b011febb3eb35ee1bec1552b96e1bb25a
Repository branch: HEAD
System Description: Arch Linux

Configured using:
 'configure --with-modules --without-xwidgets --with-native-compilation
 --with-tree-sitter --without-gsettings --without-gconf --without-gpm
 --with-pgtk --without-compress-install --with-mps --without-xaw3d
 'CFLAGS=-mtune=native -march=native -O2 -g''

[0001-Add-new-reduction-primitives-fold-left-and-fold-righ.patch (text/patch, attachment)]

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Zach Shaftel <zach <at> shaf.tel>
Cc: 78656 <at> debbugs.gnu.org
Subject: Re: bug#78656: [PATCH] Add new reduction primitives `fold-left' and
 `fold-right'
Date: Sun, 01 Jun 2025 08:47:21 +0300

> Date: Sat, 31 May 2025 22:35:20 -0400
> From:  Zach Shaftel via "Bug reports for GNU Emacs,
>  the Swiss army knife of text editors" <bug-gnu-emacs <at> gnu.org>
> 
> this patch adds left and right sequence reduction functions in C, along
> with tests for them. i don't know if this is the sort of thing the
> maintainers actually would want to merge, but i figured i would just
> submit it and hear your feedback. would also appreciate any stylistic
> feedback, for future patch submissions.

Thanks.

We already have seq-reduce, so fold-left seems to be unneeded?  As to
fold-right, couldn't we just add another function to seq.el?  Or are
there good reasons to have these implemented in C?

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

From: Pip Cet <pipcet <at> protonmail.com>
To: 78656 <at> debbugs.gnu.org, Zach Shaftel <zach <at> shaf.tel>
Subject: Re: bug#78656: [PATCH] Add new reduction primitives `fold-left' and
 `fold-right'
Date: Sun, 01 Jun 2025 07:15:54 +0000

"Zach Shaftel via \"Bug reports for GNU Emacs, the Swiss army knife of text editors\"" <bug-gnu-emacs <at> gnu.org> writes:

> Tags: patch
>
> this patch adds left and right sequence reduction functions in C, along
> with tests for them. i don't know if this is the sort of thing the

We have cl-reduce, which can be made to behave like fold-right using the
:from-end argument.  The old implementation doesn't look particularly
efficient in that case, but is it bad enough to warrant a different API?

In particular, I believe the new function has quadratic complexity when
called on multibyte strings, while cl-reduce has linear complexity.

> maintainers actually would want to merge, but i figured i would just
> submit it and hear your feedback. would also appreciate any stylistic
> feedback, for future patch submissions.

Well, you asked, so a few things I would have done differently:

I think it's a good idea to mention function arguments in order in the
docstring, where doing so doesn't make it totally unreadable.  Right
now, we have

+DEFUN ("fold-left", Ffold_left, Sfold_left, 3, 3, 0,

+       doc: /* Reduce SEQUENCE from the left with FUNCTION, starting from

+INIT-VALUE.

+  (Lisp_Object function, Lisp_Object init_value, Lisp_Object sequence)

Ffold_left should CHECK_LIST_END after the FOR_EACH_TAIL loop so it
throws an error when called on a dotted list.

Two entirely stylistic remarks:

+      result = calln (function, result, Faref (sequence, make_fixnum(i)));

I would have preferred "make_fixnum (i)" here, with a space.


+static Lisp_Object
+fold_right_array (Lisp_Object fn, Lisp_Object value, Lisp_Object *elts, EMACS_INT len)
+{

Emacs source code usually puts the length first, then the pointer to the
first element:

static EMACS_INT
mapcar1 (EMACS_INT leni, Lisp_Object *vals, Lisp_Object fn, Lisp_Object seq)

Pip

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

From: Zach Shaftel <zach <at> shaf.tel>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 78656 <at> debbugs.gnu.org
Subject: Re: bug#78656: [PATCH] Add new reduction primitives `fold-left' and
 `fold-right'
Date: Sun, 01 Jun 2025 13:38:41 -0400

Eli Zaretskii <eliz <at> gnu.org> writes:

> We already have seq-reduce, so fold-left seems to be unneeded? 

i don't disagree. the intent was to simply have `seq-reduce' provide a
generic wrapper over `fold-left', the way `seq-do' and `seq-map' do for
`mapc' and `mapcar'. but i really only added `fold-left' because i was
already adding `fold-right', and it kinda felt weird to have one without
the other.

> As to fold-right, couldn't we just add another function to seq.el? Or
> are there good reasons to have these implemented in C?

the main reason was for `fold-right' to use a C array to temporarily
hold list elements, instead of needing to `vconcat' or `reverse' the
list first. that's not hugely problematic, and i think an elisp
implementation would also be fine.

more generally, my thinking is that reduction is a core operator in
functional programming, which has become a dominant style in the elisp
ecosystem, so it would be nice to have a speed/space efficient
implementation. i assumed that's why `mapcar' is in C.

but, ultimately i knew this might not be a good fit. i was just curious,
and also wanted to see how well i understood the C internals.

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

From: Zach Shaftel <zach <at> shaf.tel>
To: Pip Cet <pipcet <at> protonmail.com>
Cc: 78656 <at> debbugs.gnu.org
Subject: Re: bug#78656: [PATCH] Add new reduction primitives `fold-left' and
 `fold-right'
Date: Sun, 01 Jun 2025 19:53:03 -0400

Pip Cet <pipcet <at> protonmail.com> writes:

> We have cl-reduce, which can be made to behave like fold-right using the
> :from-end argument.  The old implementation doesn't look particularly
> efficient in that case, but is it bad enough to warrant a different
> API?

not necessarily. i don't particularly like to use the cl seq functions
due to their verbosity, but that's just preference. i would love a
`seq-reduce-right' added to seq.el though.

> In particular, I believe the new function has quadratic complexity when
> called on multibyte strings, while cl-reduce has linear complexity.

yeah i just wrote a generic loop for non-vector arrays, but specialized
implementations could be added for other array types too of course.

> Well, you asked, so a few things I would have done differently:
>
> I think it's a good idea to mention function arguments in order in the
> docstring, where doing so doesn't make it totally unreadable.  

that makes sense. i think the documentation as a whole could be
improved.

> Ffold_left should CHECK_LIST_END after the FOR_EACH_TAIL loop so it
> throws an error when called on a dotted list.

i missed that, thanks for the heads up

> Two entirely stylistic remarks:
>
> +      result = calln (function, result, Faref (sequence, make_fixnum(i)));
>
> I would have preferred "make_fixnum (i)" here, with a space.

damn, thought i corrected all those :-)

> +static Lisp_Object
> +fold_right_array (Lisp_Object fn, Lisp_Object value, Lisp_Object *elts, EMACS_INT len)
> +{
>
> Emacs source code usually puts the length first, then the pointer to the
> first element:
>
> static EMACS_INT
> mapcar1 (EMACS_INT leni, Lisp_Object *vals, Lisp_Object fn, Lisp_Object seq)

good to know, thank you

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Zach Shaftel <zach <at> shaf.tel>
Cc: 78656 <at> debbugs.gnu.org
Subject: Re: bug#78656: [PATCH] Add new reduction primitives `fold-left' and
 `fold-right'
Date: Mon, 02 Jun 2025 08:49:53 +0300

> From: Zach Shaftel <zach <at> shaf.tel>
> Cc: 78656 <at> debbugs.gnu.org
> Date: Sun, 01 Jun 2025 13:38:41 -0400
> 
> Eli Zaretskii <eliz <at> gnu.org> writes:
> 
> > As to fold-right, couldn't we just add another function to seq.el? Or
> > are there good reasons to have these implemented in C?
> 
> the main reason was for `fold-right' to use a C array to temporarily
> hold list elements, instead of needing to `vconcat' or `reverse' the
> list first. that's not hugely problematic, and i think an elisp
> implementation would also be fine.
> 
> more generally, my thinking is that reduction is a core operator in
> functional programming, which has become a dominant style in the elisp
> ecosystem, so it would be nice to have a speed/space efficient
> implementation. i assumed that's why `mapcar' is in C.
> 
> but, ultimately i knew this might not be a good fit. i was just curious,
> and also wanted to see how well i understood the C internals.

On balance, I'd prefer to have a new function in seq.el rather than
another primitive in C.  Since we didn't need this function until now,
it is reasonable to assume it is not going to be a hot spot in any
program, so an implementation in C is not really required.

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

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 78656 <at> debbugs.gnu.org, Zach Shaftel <zach <at> shaf.tel>
Subject: Re: bug#78656: [PATCH] Add new reduction primitives `fold-left' and
 `fold-right'
Date: Tue, 03 Jun 2025 01:09:32 +0200

Eli Zaretskii <eliz <at> gnu.org> writes:

> On balance, I'd prefer to have a new function in seq.el rather than
> another primitive in C.  Since we didn't need this function until now,
> it is reasonable to assume it is not going to be a hot spot in any
> program, so an implementation in C is not really required.

Since this would just add an implicit `seq-reverse' call, this doesn't
sound convincing either.  `cl-reduce' is able to reduce :from-end.  If
at all, then adding a new argument to `seq-reduce' that causes reducing
from the end sounds more sensible to me.

@Zach: I really can feel your desire to have a primitive but part of the
story is also that Emacs Lisp is not that purely functional language
that some of us wish, since it's a lot more iteration oriented than
other Lisps - recursion depth is horribly limited, for example.  Trying
to use a purely functional style in Elisp doesn't work well.

So, in Elisp we are having most of these things in seq.el instead of the
core, and I think it's appropriate.  Especially folding is an operation
that is not used that often in Elisp.


Michael.

Previous Next

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