Ask HN: Functional vs. Imperative Implementation of Algorithms

> Functional programming experts say that their code is efficient because the compiler translates it to an efficient representation on the CPU. They have TCO and other things. But they don't mutate data and hence every function call creates a new data in memory taking up space. How do they overcome that?

By letting the compiler make assumptions. For example, consecutive map calls can be converted into a single one. If the data isn't shared with something else, the compiler can mutate it. MUCH easier to paralellize maps.

As a starting point for those nitty grittys, this talk is probably as good as any https://www.youtube.com/watch?v=vzfy4EKwG_Y

Functional is easier to reason about, if you are the kind of person who prefers reasoning in that way. For some people, it fits the way they think better. For others, it doesn't.

But imperative is still the default first approach that everybody is taught. For those whose minds fit better with functional, when they encounter functional programming, it's like being let out of prison. It's amazing. The problem comes when they assume that it will be the same for everyone, and if someone else doesn't have the same experience, it's because they haven't "gotten" functional yet. No, some peoples' minds find imperative to be a more natural way to think.

So: Learn some functional. Learn it well enough to see if it fits how you think. If it does, great! And if it doesn't, also great! Then, primarily go with the tool that fits you.

> But they don't mutate data and hence every function call creates a new data in memory taking up space.

Well, only if you mutate the data. And even then, most functional languages provide persistent data structures that allow efficient sharing of the unchanged parts of the data structure.

> Now my question is where do I learn about these nitty gritty's? Should I read about compilers more? Or systems? Or what?

I'd recommend choosing a functional language and an imperative language and learning both.

> And even then, most functional languages provide persistent data structures that allow efficient sharing of the unchanged parts of the data structure.

So you are saying that in imperative setting if we use the original data for multiple functions we have to create copies of it and then modify those copies. So we end up taking extra space there also. So both languages take up space. One before the function call another after.

Not exactly (if I understand the question correctly).

Imperative usually goes with mutation. If I'm willing to do mutation, then I can replace the old value with the new value in the same location, allocating nothing either before or after.

If you want to do immutable with imperative, then yes, you have to allocate sometime.

> If you want to do immutable with imperative, then yes, you have to allocate sometime.

Yes that's what I was saying.

I cannot provide references, but I would suggest researching Compilers and Compiler optimisations.

You may want to look at:

https://www.plai.org/