Where is my state?

People often associated functional programming with statelessness. The reality is that there is always a notion of state, functional programming is about stateful programming. The ambiguity is probably the result of state appearing in different ways than in a procedural style.

In a procedural style, state is associated to memory and you change it by using the writable property of memory.

In a functional style, state is still in memory  but the “classical” approach is to disallow yourself from changing it by writing again over memory. This is the immutable programming style. It goes with functional programming because it is very difficult to build on immutability without some functional programming concepts (I have tried!).  So if you have state and you cannot write over it, the only thing you can do is to read it, and if you want to change the state, you need to write a new memory location with your new state value (a non-functional  near immutable approach is to use arrays and grow them). The problem for beginners is “where should that new state be”?  It needs  to be accessable, and while you maybe knew how to access the old state, where should you put the new state so as to be able to work with it, instead of the old state?
Recursiveness is then the first  way  to manage state; The idea is that if you have a function F that works with state, then if you create a new version of the state you can simply call F recursively  with the new state, and again and again with each new version of the state.

Recursiveness is always somewhere nearby if you are using immutability; Yet you do not need to expose it to manage state. Again, suppose a function F uses state, have it return its state after use, if the state has not changed, then  return it unchanged, if the state changed, then return its new version. The trick is then to have a loop that calls F with the state, then takes the returned value to call F again, and so on. As this is immutable code, the loop is a small tail recursive function.

State can be big and heavy, and not for the wrong reasons, your application may be a big thing. The last thing you want to do is to copy that whole structure just to make a small change. The simple approach is to reuse parts of your old state to make a new state, changing only what needs to be changed. Yet  as the state is usually a tree like structure, if what is changing is deep in the original state, then it will cost you to create a new state because you will need to rebuild much of the hierarchy of the state. One way around this is to take the old state, encapsulate it in a “change of state” structure and use this as the new state  This approach is what I call a differential approach: the state change is the difference. By stacking differences you build a complete state. Usually the differential approach is combined with the “normal” partial copy approach. The reason is that if pursued forever, the “stack” of state changes become too big and starts both to consume memory and take time to access.

In the end your new state will either leave your function “onwards” into recursion or backwards by return, and often the same algorithm may use both methods.
When beginning with the functional style, state seems to be forever a pain to drag around. But with time patterns appear. First you may notice that not all states have the same lifetime, and they do not all have the same read write properties. It is a good idea to try to separate states that have different access and update properties.  You may then note that the hierarchy of functions aligns itself to with the access patterns of your state. Yet if you tie state to function in an layered like fashion that is classical to procedural programming you realize that what you have is not so much state as parameters. That is, while you are working in an inner function you have no ability to modify the outer “state”, so it is more a parameter like than state like. Nevertheless, with situation where states have a strict hierarchy, this approach is ok.

At some point, carrying around state becomes such a standardized routine that  it makes sense to look for help to go to the next level. And the next level is… monads. Here is the deal, I said before that states will either exit your function through a further recursion or by return.  That means that there is a set of compatible patterns that can be used to assemble little bits of code that work on state, so that they nicely fit and the state zips around as an argument or as a return value. This pattern appears naturally when your work with states: it is the idea that the state is passed as last argument and that the stateful functions always return a state. As you want the function to do something useful, you systematically return a tuplet with a state and a function specific return value. Before understanding monads,  I wrote whole applications like this. What monads allow you to do is to standardize so much this method of call pattern that it becomes possible to strip the exposed code of these “peripheral” state going in and state going out. The result is code that looks stateless but that isn’t.  The value of monadic state management is that you make much less mistakes and you can specialize your monad further to give it special properties. Still, from a stateful perspective the main gain of monadic states is productivity: hiding the state mean you can focus on more important things.