If I understand correctly, does this mean that a map operation (that is not reduced further; i.e. we want a collection as the output) could be carried out in parallel efficiently using reducers only if there is an efficient (O(1)) way to concatenate the collections produced at each combining step (in the "internal nodes" of the fork-join computation tree)?

This would constrain how collections are implemented to make good use of this technique.