from Hacker News

Reduce vs. Fold in Common Lisp

by billiob on 6/3/23, 6:03 PM with 29 comments

• by ruricolist on 6/4/23, 11:22 PM

  The history here is that Common Lisp gets reduce from APL (https://aplwiki.com/wiki/Reduce). It's not an attempt an ML-style fold, but a different formalism from a different lineage.

• by varjag on 6/4/23, 10:22 PM

  …REDUCE functions can be called with zero, one or two list values.

  No, it's either two or zero arguments.

• by somewhereoutth on 6/4/23, 11:03 PM

  fold is a natural consequence of church lists, probably the most fundamental way of expressing the list abstraction:

  \f \x (f a0 (f a1 (f a2 x)))

  So fold is just applying a list (function) to 2 arguments. Or you can be helpful and make something like fold := \f \x \l l f x which is useful for binding the f and the x and applying to multiple lists (everything is Curried of course)

  LISP is not quite based on lambda calculus, so it should be no surprise it doesn't quite get reduce(i.e. fold) right.

  See also church numerals, which are like lists but without the elements, they also have a 'fold':

  \f \x f (f (f x))) == 3

  We can make trees! Which again also have a 'fold'

  \f \x f a0 (x a1) (f a2 (x a3) (x a4))

  And many other more exotic folding data structures.

• by dreamcompiler on 6/5/23, 4:34 AM

  > It then applies the function to successive pairs of sequence elements.

  No. #'reduce may take the first pair as an optimization step, but from that point on it processes sequence elements one at a time. It passes an accumulated value and the next sequence value to the function.

• by tangus on 6/4/23, 10:48 PM

  >Fold is also simpler than REDUCE since it does not have any special case, making it easier to reason about its behaviour.

  If returning the initial value when the list is empty is considered a special case (or "surprising aspect") of REDUCE, then it's the same for FOLD, no?

• by User23 on 6/5/23, 5:39 AM

  I don't have a running image handy, but

    (+) ; => 0
    (*) ; => 1
  

  and

    (+ n) ; => n
    (* n) ; => n
  

  which I expect has some bearing on the behavior of reduce in the examples given.

  It's pretty obvious that any other function could either have or be advised to have whatever equivalent semantics are appropriate.

  Of course

    (apply #'+ '(1 2 3 4 5)) ; => 15
  

  So reduce can be obviated by just letting the function take variable args too.

• by lispm on 6/5/23, 5:14 AM

  so foldl is basically

    (defun foldl (function value sequence)
      (reduce function sequence :initial-value value))

• by mgaunard on 6/5/23, 7:59 AM

  + is not associative for many types.