Subject: bug#78656: [PATCH] Add new reduction primitives `fold-left' and `fold-right'

From: Pip Cet <[email-masked]>
Date: Sun, 01 Jun 2025 07:15:54 +0000

"Zach Shaftel via \"Bug reports for GNU Emacs, the Swiss army knife of text editors\"" <[email-masked]> 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