Reduce vs. Fold in Common Lisp
n16f.net
Reduce vs. Fold in Common Lisp
1–10 of 30 posts
Re: Reduce vs. Fold in Common Lisp
#2…REDUCE functions can be called with zero, one or two list values.
No, it's either two or zero arguments.
Re: Reduce vs. Fold in Common Lisp
#3…REDUCE functions can be called with zero, one or two list values. No, it's either two or zero arguments.
Author here. I double checked the Hyperspec [1] and you're quite right. I'll fix the article tomorrow, thank you for noticing!
[1] http://www.lispworks.com/documentation/lw60/CLHS/Body/f_redu...
Re: Reduce vs. Fold in Common Lisp
#4>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?
Re: Reduce vs. Fold in Common Lisp
#5fold 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.
Re: Reduce vs. Fold in Common Lisp
#6>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?
The most surprising aspect of REDUCE is the way the callback can be called depending on both the length of the list and the presence of absence of an initial value.
Re: Reduce vs. Fold in Common Lisp
#7>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?
The initial value is optional for `reduce`, but required for `fold`. If you don't pass the initial value to `reduce`, and the sequence argument is empty, then `reduce` calls the function with no arguments, which is unique - in all other cases, it is called with two arguments. `fold` always calls its function argument with two arguments.
This shows up more clearly in statically-typed functional languages, where variadic functions like this are far less common. In that case, you typically see that `reduce` returns an option type, whereas `fold` does not. The types would look something like `fold :: (a -> b -> a) -> a -> List b -> a` vs `reduce :: (a -> a -> a) -> List a -> Option a`.
Re: Reduce vs. Fold in Common Lisp
#8The 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.
Re: Reduce vs. Fold in Common Lisp
#9The 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.
I never heard of apl's allowing for an explicit choice of initial value, nor direction control ('from-end'), which mls typically also provide (foldl vs foldr). On the other hand, the ad-hoc choice of result for an empty input is a flaw common to cl and apl.
Re: Reduce vs. Fold in Common Lisp
#10The 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.
While reading this, I was immediately reminded of the reduce operator, glad to see my intuition wasn't far off.
The nifty thing about this operator in the array-langs compared to the usual fold function is that they usually define identity elements for all primitive functions, which means that no initial value has to be provided: https://aplwiki.com/wiki/Identity_element
The downside of this approach though, is that using reduce with non-primitive functions can result in domain errors (at least in APL). I think BQN's version of the operator is a bit nicer, in that it allows you to specify an initial value in this situation: https://mlochbaum.github.io/BQN/doc/fold.html