I've learned how to program primarily from an OOP standpoint (like most of us, I'm sure), but I've spent a lot of time trying to learn how to solve problems the functional way. I have a good grasp on how to solve calculational problems with FP, but when it comes to more complicated problems I always find myself reverting to needing mutable objects. For example, if I'm writing a particle simulator, I will want particle "objects" with a mutable position to update. How are inherently "stateful" problems typically solved using functional programming techniques?
Functional programs handle state very well, but require a different way of looking at it. For your position example, one thing to consider is having your position be a function of time instead of a fixed value. This works well for particles following a fixed mathematical path, but you require a different strategy for handling a change in the path, such as after a collision.
The basic strategy here is you create functions that take in a state and return the new state. So a particle simulator would be a function that takes a
Set of particles as input and returns a new
Set of particles after a time step. Then you just repeatedly call that function with its input set to its previous result.
As noted by @KarlBielefeldt, the functional approach to such a problem is to view it as returning a new state from a previous state. The functions themselves do not hold any information, so they will always update state m to state n.
I think you find this inefficient because you assume that the previous state has to be kept in memory while computing the new state. Notice that the choice between writing a completely new state or re-writing the old one in place is an implementation detail from the point of view of a functional language.
For instance, say I have a list of a million integers, and want to increment the tenth by one unit. Copying the entire list with a new number in its tenth position is wasteful, you are right; but it is only the conceptual way of describing the operation to the language compiler or interpreter. The compiler or interpreter is free to take the first list and just overwrite the tenth position.
The advantage of describing the operation in this way is that the compiler can reason about the situation when many threads want to update the same list at different positions. If the operation is described as "go to this position and overwrite what you find", then it is the programmer, not the compiler, who is in charge of making sure that overwrites do not collide.
With all that said, even in Haskell there is a State monad that helps to model situations where "keeping state" is a more intuitive solution for a problem. But please also notice some problems that you find "inherently stateful, like writing to a database" have immutable solutions like Datomic. This can be surprising until you understand it is a concept, not necessarily its realization.
Subscribing to the right mental model helps one better think about and manage state. In my mind, the best mental model is the flip book. Once this clicks you'll understand that FP leans heavily on persistent data structures that capture the state of the world and that functions are used to transition that state without any mutation whatsoever.
Rich Hickey illuminates these ideas:
There are other talks but this should send you in the right direction.
When writing large and moderately large applications, I have often found it useful to differentiate between the sections of the application that are stateful and those that are stateless.
The classes/data structures in the stateful section store the data of the application and the functions in this section work with implicit knowledge of the data of the application.
The classes/data structures/functions in the stateless section are there to support the purely algorithmic aspects of the application. They don't have implicit knowledge of the data of the application. They work in a purely functional nature. The stateful parts of the application may experience change of state as a side effect of running functions in the stateless section of the application.
The hardest part is figuring out which classes/functions to put in the stateless section and which classes/functions to put in the stateful section, and having the discipline to put them in separate files/libraries.