> Not all immutable data structures can be made as efficient as mutable ones. Usually they are as fast as mutable ones,
I don't think this is true. Clojure uses immutable persistent data structure under the hood, just as most functional languages do, and devs often jump through hoops to circumvent them for performance reasons, opting instead for bit bashing like most other languages.
An immutable tree is often about as fast as a mutable tree, it's just pointer manipulation in either case.
An immutable data structure representing an array is definitely much slower than a mutable array (a contiguous piece of memory).
Usually != always, unfortunately :(
> An immutable tree is often about as fast as a mutable tree, it's just pointer manipulation in either case.
This might be true, depending on what type of processing you're doing, and if you have a good garbage collector.
Of course, if you're allowed to use mutable trees, then you should just use a hash table which will be faster both asymptotically and in practice.
You can write any algorithm using any Turing-complete machine, including the original tape-based Turing machine or a language like Malbolge. But it is going to take an inordinate amount of time to write and debug.
What FP and message passing buy you is the ease of reasoning. No shared state -> no problem of concurrent updates. No state at all -> no questions like "but does this method update that instance member?". All your state lives in message queues and call stacks, and both provde very stringent and easy-to-understand disciplines.
This also gives you composability: you have easy time putting things together and rearranging them as you see fit, without caring of any hidden data dependencies. Everything is explicit.
(Combined with a static type checker and a right type system, it gives you the effect of "if it compiles, it runs correctly 99% of times", seen e.g. in Haskell or Rust. Elixir is not a statically-typed language, though.)
Yes, it does sometimes come at a cost. Not all immutable data structures can be made as efficient as mutable ones. Usually they are as fast as mutable ones, but pay some space cost; IIRC it's theoretically proven that the cost is no more than a logarithmic one.
With RAM being so much cheaper than developers' time, it's a rather good tradeoff. At least, using JIT in Java or Javascript, or just using Python and Ruby, one usually pays a similar or higher RAM cost, for a fraction of benefits. JS does move towards immutability and FP-ness, though, because the above applies to it, too, and it's not so OOP-heavy as for make FP approaches largely impractical.