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 Programming – Dealing with State Problems
functional programming
Related Solutions
The usual way to go about state changes in a pure language like Haskell is to model them as functions that take the old state and return a modified version. Even for complex objects, this is efficient because of Haskell's lazy evaluation strategy - even though you are syntactically creating a new object, it is not copied in its entirety; each field is evaluated only when it is needed.
If you have more than a few local state changes, things can become clumsy, which is where monads come in. The monad paradigm can be used to encapsulate a state and its changes; the textbook example is the State monad that comes with a standard Haskell install. Note, however, that a monad is nothing special: it's just a data type that exposes two methods (>>= and return), and meets a few expectations (the 'monad laws'). Under the hood, the State monad does exactly the same: take the old state and return a modified state; only the syntax is nicer.
I'll try to hint on the answer. This is not an answer, only an introductory illustration. @jk's answer points to the real thing, zippers.
Imagine you have an immutable tree structure. You want to alter one node by inserting a child. As a result, you get a whole new tree.
But most of the new tree is exactly the same as old tree. A clever implementation would reuse most of the tree fragments, routing pointers around the altered node:
Okasaki's book is full of examples like this.
So I suppose you could reasonably alter small parts of your game world each move (pick up a coin), and only actually change small parts of your world data structure (the cell where the coin was picked up). Parts that only belong to past states will be garbage-collected in time.
This probably takes some consideration in designing the data game world structure in an appropriate way. Unfortunately, I'm no expert in these matters. Definitely it must be something else than a NxM matrix one would use as a mutable data structure. Probably it should consist of smaller pieces (corridors? individual cells?) that point to each other, as tree nodes do.
Best Answer
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
Setof particles as input and returns a newSetof particles after a time step. Then you just repeatedly call that function with its input set to its previous result.