Reduce function for left-associative reduction

[njordhov]

This is to propose a new function reduce similar to fold but with different behavior when used with a non-commutative combination function.

Reduce performs a left-associative reduction with the first argument to the reducer being the initial value then the accumulated result and the second argument being each element of the input sequence; It also reverses the order of the arguments compared to fold so the initial value comes before the input sequence in the call. Signature:

Function(A, B) -> A, A, (Sequence B)  
-> A

Examples:

(reduce - 11 (list 1 2 5))   ;; Returns 3 equivalent to (- 11 1 2 5)
(reduce concat "ab" "cdef")   ;; Returns "abcdef" like (concat "ab" "c" "d" "e" "f")
(reduce concat "ab" (list "cd" "ef"))   ;; Returns "abcdef" like (concat "ab" "cd" "ef")

Although fold and reduce are practically synonyms or typically labels similar functionality in programming languages, the latter is preferable. Both Clojure and Common Lisp use reduce; Javascript has reduce. It is also the term used in React and Redux.

Original: https://github.com/blockstack/stacks-blockchain/issues/1257

[psq]

I'm concerned that having both functions would be more confusing than helpful. And there's nothing you could do with reduce you couldn't do with fold unless I'm missing something. The order of the arguments and parameters are just reversed.

[njordhov]

I'm concerned that having both functions would be more confusing than helpful.

It could replace fold which generally is less useful, and unintuitive when the argument order is significant. Compare:

(fold - (list 1 2 5) 11) ;; Returns -7 by calculating (- 5 (- 2 (- 1 11)))
(reduce - 11 (list 1 2 5))   ;; Returns 3 equivalent to (- 11 1 2 5)

(fold concat "cdef" "ab")   ;; Returns "fedcab"
(reduce concat "ab" "cdef")   ;; Returns "abcdef" like (concat "ab" "c" "d" "e" "f")

(fold concat (list "cd" "ef") "ab")   ;; Returns "efcdab"
(reduce concat "ab" (list "cd" "ef"))   ;; Returns "abcdef" like (concat "ab" "cd" "ef")

And there's nothing you could do with reduce you couldn't do with fold

The proposed function covers more of the typical use cases. If you were to use fold for the same, it would take extra code to reverse arguments and item order.

[hugocaillard]

We could also introduce fold-left and fold-right And deprecate the current fold (deprecation doesn't really happen at the clarity level but in the tooling)