Common Lisp function for "Reduce and Return Intermediate Results as Sequence"

Question

In Clojure, there is a higher-order function reductions, which you would use with arguments similar to reduce and will return a sequence containing all intermediate results.

Is there an equivalent in Common Lisp? I was unable to find any reference to it online, including the various books/articles on https://common-lisp.net/tutorials/ but given Lisp's heritage as a family of List Processing languages I imagined a list->list function like reductions will exist across dialects.

Exegesis

Do note that Common Lisp's reduce function has a few more bells-and-whistles than Clojure's. Common Lisp's lets you specify the traversal order (e.g., you can go from right to left in addition to the default left to right), you can omit the initial value (in which case, the "first" element (leftmost or rightmost, depending on the traversal order) is used as the initial value), etc. Some of those features make this not quite as trivial as it might seem otherwise. – Maris

@JoshuaTaylor Great point, thanks. I still need to get used to the Common Lisp culture of having very powerful options built in to various functions. – Exegesis

@JoshuaTaylor You can omit the initial value in Clojure's reduce: (reduce + ["whatever"])) => "whatever". – Voss

Answer 1

There is no standard function for it. You could define one easily:

(defun reductions (function sequence &rest args
                   &key key from-end (start 0) end initial-value)
  (declare (ignore key from-end start end initial-value))
  "Return a list of intermediate values from reducing SEQUENCE with FUNCTION."
  (let* ((reductions (list))
         (result (apply #'reduce
                        (lambda (&rest arguments)
                          (let ((result (apply function arguments)))
                            (push result reductions)
                            result))
                        sequence
                        args)))
    (values (or (nreverse reductions)
                (list result))
            result)))

(reductions #'+ '(1 2 3 4 5 6 7 8 9 10) :initial-value 0)
;=> (1 3 6 10 15 21 28 36 45 55)

Edit: Use APPLY with &REST ARGS instead of calling REDUCE directly. Some implementation of REDUCE might not work if NILs are supplied for keyword arguments.

Edit2: The reducing function can be called with 0 or 2 arguments.

Edit3: When REDUCE is called with a list of only one element, the only element is returned as is. The reducing function is not called at all, which means the list of reductions would be empty. I added an OR to return the final result wrapped in a list in that situation (to match Clojures behaviour). I also changed the code to return the final result as a second return value (might be useful and "why not?").

Briny

Can you elaborate on your first edit where you mention that "Some implementation of REDUCE might not work if NILs are supplied for keyword arguments." The docs show that some can be nil, start has to be a number (and default is 0). For initial-value, it's not that it can or can't be nil, it's that the behavior is different depending on whether it's provided or not. There shouldn't be any variation in implementations; what matters is whether it's provided at all. – Maris

@JoshuaTaylor I meant that some implementation might specify IDENTITY as the default for KEY, or (1- (LENGTH SEQUENCE)) as the default for END and passing a NIL would mess that up. But you're right, the spec actually states that NIL is the default, so that's not actually a problem. The edited code still is needed to handle INITIAL-VALUE though. – Briny

In fact, I think that using nil to stand in for key arguments ("If key is not supplied or is nil, the sequence element itself is used.") is established, exactly to make this kind of use case easier. The trip up in this case is just with initial-value. It's nice to see solutions that address this correctly. :) – Maris

Thank you, this is very educational. – Exegesis

reductions has been added to clojure.core – Idel