Scans and reduction functions

[WardBrian]

Related to #3339, there are also common higher-order functions that return a different type than their input.

Some common options are:

• fold_left(F, T, ...) => f(f(f(f(T[0], T[1]), T[2]), ...), T[3]) (sometimes, rather than starting at T[0], an extra 'init' argument is passed)
• fold_right, which is the same idea but with the opposite association f(T[0], f(T[1], ...f(T[N], init)))
• reduce, which is defined such that it is equivalent to the above when the f is associative but does not explicitly state an order of evaluation. The cool thing about reduce is it can be parallelized, c.f. foldl and foldr Considered Slightly Harmful, and More Fun with Moniods
• scan, which returns a cumulative evaluation scan(f, T, ...) => [T[1], f(T[1], T[2]), f(f(T[1], T[2]), T3), ...]. Note that scan can also be parallelized when f is associative, c.f. Prefix Sums and their Applications. (Note: even though reduce(f, T, ...) == scan(f, T, ...)[N], the ideal parallelization algorithms actually differ)

There are other functions of questionable value to Stan in this family, like folding_map which returns both a carry and a mapped container (this is, confusingly, what JAX calls scan. Scans a-la Blelloch as described above are called associative_scan in JAX)

[SteveBronder]

reduce, which is defined such that it is equivalent to the above when the f is associative but does not explicitly state an order of evaluation. The cool thing about reduce is it can be parallelized, c.f. foldl and foldr Considered Slightly Harmful, and More Fun with Moniods

For this, could we just take the code for reduce_sum and make a reduce that takes in a general reduction function? Then reduce_sum is just a specialization of that.