Two Vexing Problems in Functional Programming

The thing is, functional and imperative programming are mathematically equivalent - to the point that you can express imperative code in a pure functional language, if that's what you really need. If you want a O(1) random access in a functional language, you can formally define it; the problem with this is that you may end up embedding a whole computer in your program to do it, if your program heavily depends on side effects like those in the article. So, if you really need O(1) mutability for a large part of your program, maybe functional programming is not the tool for the job? Being too tied to a paradigm prevents you from finding the best tool at hand.

Functional programs are best used when you want referential transparency[1] as your problem domain benefits from it. If you want to represent mutable state in a functional, transparent way you use a subset of temporal logic[2] - each function has an additional state of the world input parameter, and return an additional updated state of the world value with all the mutated objects in it. The State monad is a version of this with increased legibility (as long as you don't combine many different sources of mutation).

If your needs for mutation are limited to a few objects in each module, you represent those as streams (the generalized version of futures which are able to be repeatedly updated with new values); a stream represents the history of all values that a mutable variable takes during the program execution. This is the basis of the functional reactive paradigm[3] on which modern web frameworks like React and Vue are converging, as it happens that modeling asynchronous state mutations of multiple loosely connected elements is easier in the functional paradigm than in the imperative.

[1] https://en.wikipedia.org/wiki/Referential_transparency

[2] https://en.wikipedia.org/wiki/Temporal_logic

[3] https://en.wikipedia.org/wiki/Functional_reactive_programmin...

The "big object" problem is solved by the persistent data structures in Clojure

https://clojure.org/reference/data_structures

These are a little slower than conventional data structures (e.g. Java Collections) but are much more efficient than copying the whole structure every time you want to "change" it. The garbage collector picks up behind you so you're not wasting unbounded space on unreachable versions of the data structures.

I believe mutable data-structures per se are not a bad thing. What is bad is Unobservable State Mutation.

When you assign a field into a data-structure it is bad because later on you will see the changed data-structure and try to use it but it has a wrong value which causes an error in your program - maybe not a crash just an error in the output. And then it's really hard to say what caused that error because you have no visibility into who or where did that erroneous assignment happen.

If instead you could forbid direct assignments and could write a "watcher" (a.k.a "setter") for all data-modifications, you could observe how your program-state evolves during its execution, and you could write assertions that prevent wrong type of data-manipulation from happening.

One such language is Smalltalk. You can only modify data by sending a "message" to an object to be modified, and the object can only respond by executing one of its methods. You can then write assertions in those methods to halt in debugger or write to console if you see the program write a specific value or type of value into your data-structure.

Even on the rather primitive level of Arrays you could easily modify their #at:put: -method in Smalltalk and halt or log the stack-trace if somebody tries to store the number 42 into the array. :-)

In the end the problem is understanding what your program does in terms of its state, how the state evolves. Why? Because: Modifying state in essence modifies your program. And to understand your program you must understand all evolving versions of it. Like, if you want to understand a 'caterpillar' you must also understand its next mutated state 'butterfly'.

FP makes it easier to understand the state-evolution because new state is just the result of some calculation which is easy (?) to understand by understanding each "pure" function in your program and reasoning what their combined result is.

But if you can understand the state-evolution of your program by imperative means that is fine too. That is why many suggest using a database to keep the state. A database is mutable by definition. But it makes it easy to observe how your state evolves by observing the UPDATE and DELETE and INSERT calls made into your database.