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 Moniodsscan, 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)
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 associationf(T[0], f(T[1], ...f(T[N], init)))reduce, which is defined such that it is equivalent to the above when thefis associative but does not explicitly state an order of evaluation. The cool thing aboutreduceis it can be parallelized, c.f.foldlandfoldrConsidered Slightly Harmful, and More Fun with Moniodsscan, which returns a cumulative evaluationscan(f, T, ...) => [T[1], f(T[1], T[2]), f(f(T[1], T[2]), T3), ...]. Note thatscancan also be parallelized when f is associative, c.f. Prefix Sums and their Applications. (Note: even thoughreduce(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_mapwhich returns both a carry and a mapped container (this is, confusingly, what JAX callsscan. Scans a-la Blelloch as described above are calledassociative_scanin JAX)