[kjksf]

In every mainstream language I can think of `map foo myCollection` creates an intermediary map.

Memory allocation is so expensive that making that copy is often more expensive that calling `foo` on each element.

Sometimes making a copy is exactly what you need and there's no way around that cost (but hold that thought).

But I've also seen `sum map foo myCollection` so many times (especially in JavaScript).

Here you have a short, neat but also extremely wasteful way of doing things. I see it so frequently that I assume that many people are unaware of this cost (or completely disregard performance concerns).

If you were to write this imperatively, it would be obvious that you're making a copy and maybe you would stop and re-think your approach.

But there's more.

If you're paying attention to performance, an easy way to improve performance of `map foo myCollection` in e.g. Go is to pre-allocate the resulting array.

For large arrays, this avoid re-allocating of underlying memory over and over again, which is the best a `map` can do.

In imperative code those costs are more visible. When you have to type that code that does memory allocation, you suddenly realize that the equivalent of `map` is extremely wasteful.

[h_r]

I don't want to discuss this forever but I have a couple of comments:

Your points about efficiency are a separate topic entirely from the original claim that manually writing out an imperative solution makes it easier to see the algorithmic complexity. That was a surprising claim to me because, in my experience, if I understand what some HOF is doing, reading the code is even easier because there is less of it to wade through (and mental exhaustion doesn't make one easier to read vs the other).

> In every mainstream language I can think of `map foo myCollection` creates an intermediary map

You need to build up the final result, sure. Not an intermediary map but whatever structure (or functor) you're mapping over. That is the whole point of immutable data structures. Also when you're using persistent data structures, which all modern FP languages do, the cost of constructing the result can be far less than what you expect, especially if the result is lazy and you need only some of the results. There is a cost to immutability and if it's unbearable in some situation, fall back to in-place mutation but the semantics of these two approaches are definitely not the same.

> But I've also seen `sum map foo myCollection` so many times

Yeah... that should be a fold (reduce, whatever). :)

[LandR]

>> In every mainstream language I can think of `map foo myCollection` creates an intermediary map.

Language support for Transducers can fix this, you can compose functions like map / filter / reduce over a collection and only hit each item once.

[erik_seaberg]

Even Java can do this. You only pay for another Collection<T> if you actually #collect the elements of a Stream<T>.

[Gaelan]

Is Rust mainstream? If so, this code:

    numbers.iter().map(|n| { ... }).sum();

Compiles to a plain loop, with no allocation.

[steveklabnik]

(You want for_each not map, by the way)

[Gaelan]

Wait, why? AFIAK for_each doesn't return another iterator, and I'm calling sum afterward.

[steveklabnik]

.... hacker news cut off the “sum” part, and so I didn’t see it. On my phone it just happened to clip it exactly long enough that it was still valid syntax, wow. Anyway, sorry and my bad!