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?
6
-
4The first step is likely realizing that problems aren't inherently stateful.– TelastynCommented Jun 9, 2014 at 1:42
-
5Some problems are inherently stateful, like writing to a database or drawing a gui. Taking my particle simulator example, what would be an alternative way to think about it? Returning new particles every time their position updates in order to avoid state seems inefficient to me, and not a good model of the real world.– Andrew MartinCommented Jun 9, 2014 at 2:12
-
5Except perhaps for the database example, those problems are not inherently stateful. For example, for GUI programming, you're really using mutable state as a poor, implicit model of time; functional reactive programming lets you model time explicitly without relying on state by providing streams of events you can combine.– Tikhon JelvisCommented Jun 18, 2014 at 16:32
-
2There's a simpler solution: when you come to a problem that's not easily modeled with FP techniques, don't use functional programming to solve it. Right tool for the job and all that...– Mason WheelerCommented Feb 25, 2015 at 17:23
-
1@AndrewMartin Not a good model of the real world? The mathematics used in physics to model the real world is purely functional. With a good garbage collector allocating an object is as cheap as bumping a pointer, and collection time is proportional to the number of live objects. If anything, I'd bet the major source of inefficiencies in functional programming is using data structures that aren't cache-efficient. Linked lists and binary trees aren't exactly poster childs of cache efficiency.– DovalCommented Feb 25, 2015 at 17:55
|
Show 1 more comment
4 Answers
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.
answered Jun 9, 2014 at 2:29
-
7
-
1Thanks for this insight. My worries about inefficiency were thwarted by @logc; the technical details of how state is transformed is a low level implementation problem that the language itself is supposed to solve. I watched Rich Hickey explain how he does this with Clojure in a video. Commented Jun 9, 2014 at 21:59
-
1@jhewlett: To be more precise: FP does have state, even mutable state, but they do not represent it using mutable variables.– GiorgioCommented Feb 25, 2015 at 19:04
-
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.
-
4I think the snippet about updating a large list is misleading; I don't know of any compiler that will actually perform that optimization for you. Even if the compiler could do that, it's only possible in cases where you don't hold on to previous versions of the list. The real solution is to use a list data structure that doesn't require copying the whole thing to change a single element.– DovalCommented Feb 25, 2015 at 17:50
-
@Doval: "Even if the compiler could do that, it's only possible in cases where you don't hold on to previous versions of the list.": This reminds me of unique types in Clean.– GiorgioCommented Jan 24, 2017 at 20:33
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.
-
-
@kravemir, whether you write an application using OOP or FP, you have to understand where the state of the application lies.– R SahuCommented Sep 22, 2016 at 17:57