> I think that in every imperative language that offers `map`, `filter`, `reduce`, or similar, the written contract of this API should state that any higher-order function handed to it as an argument must be free from side effects.

Does the written contract for for-loops specify this as well? Because that's the obvious alternative for a reduce that an imperative programmer would reach for: a for-loop with the programmer managing the accumulation manually.

I also don't see why a reduce should be side-effect free. There's nothing wrong with having a type def't for reduce be

    base.data.List.foldLeft : (b ->{e} a ->{e} b) -> b -> [a] ->{e} b

Where {e} indicates a side effect. Here, the reducer can have side effects, and those side effects propagate to the result of the fold/reduce.