Reduce vs. Fold in Common Lisp(n16f.net) |
Reduce vs. Fold in Common Lisp(n16f.net) |
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
ml-style folds in the presence of ad-hoc polymorphism solve this rather handily -- in haskell for instance monoid is the typeclass that only requires an associative operation and an identity element
typeclasses have some clunkiness in this regard; you have to wrap numeric types as "sum" or "product" etc to go "ah yes today i want to say numbers are a monoid under this operation" but at the very least it does enable formal, user-defined associations between identity elements and functions
luckily most things programmers deal with are plausibly just one kind of monoid. for instance the eleventy billion different string types haskell programmers love to use all tend to satisfy monoid under concatenation without any wrappers
Yes, that's another problem. There is precedent for associating metadata with user-defined functions (eg inverses); identities seem to have fallen by the wayside, but I am planning to fix that for j.
No, it's either two or zero arguments.
[1] http://www.lispworks.com/documentation/lw60/CLHS/Body/f_redu...
\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.
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.
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?
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`.
(+) ; => 0
(*) ; => 1
(+ n) ; => n
(* n) ; => n
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
In Common Lisp the max number of arguments can be small.
$ abcl
Armed Bear Common Lisp 1.8.0
Java 11.0.19 Ubuntu
OpenJDK 64-Bit Server VM
Low-level initialization completed in 0.304 seconds.
Startup completed in 1.501 seconds.
Type ":help" for a list of available commands.
CL-USER(1): CALL-ARGUMENTS-LIMIT
50 (defun foldl (function value sequence)
(reduce function sequence :initial-value value)) (+ #c(10 -1) #c(20 1))
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (+ #c(10 -1) #c(20 1))
30
* (type-of (+ #c(10 -1) #c(20 1)))
(INTEGER 0 4611686018427387903)
* (type-of (+ #c(10 -1) #c(20 1.0)))
(COMPLEX (SINGLE-FLOAT 0.0 30.0)) </ ⍬ ⍝ Empty list
0
</ ,5
5
</ 0 5
1
</ 5 0
0
Don't use
(apply #'+ long-list-of-numbers)
(reduce #'+ long-list-of-numbers) * (disassemble (lambda () (apply #'+ '(1 2 3 4 5))))
; disassembly for (LAMBDA ())
; Size: 21 bytes. Origin: #x5345C11B ; (LAMBDA ())
; 1B: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer
; 1F: 488945F8 MOV [RBP-8], RAX
; 23: BA1E000000 MOV EDX, 30
; 28: 488BE5 MOV RSP, RBP
; 2B: F8 CLC
; 2C: 5D POP RBP
; 2D: C3 RET
; 2E: CC10 INT3 16 ; Invalid argument count trap
NIL
* (disassemble (lambda () (reduce #'+ '(1 2 3 4 5))))
; disassembly for (LAMBDA ())
; Size: 21 bytes. Origin: #x5345C1AB ; (LAMBDA ())
; AB: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer
; AF: 488945F8 MOV [RBP-8], RAX
; B3: BA1E000000 MOV EDX, 30
; B8: 488BE5 MOV RSP, RBP
; BB: F8 CLC
; BC: 5D POP RBP
; BD: C3 RET
; BE: CC10 INT3 16 ; Invalid argument count trap
NIL