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

Previous Next

Full log

View this message in rfc822 format

From: Zach Shaftel <zach <at> shaf.tel>
To: Pip Cet <pipcet <at> protonmail.com>
Cc: 78656 <at> debbugs.gnu.org
Subject: 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

Previous Next

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