...And Monads for (Almost) All: The State Monad
This article starts a series on a topic that is very hot among the developers’ community: functional programming. In details, we will focus on monads. This very complex object coming from the Category Theory is so important in functional programming that is very hard to program without it in this kind of paradigm. Its main aim is to make simpler the composition of pure functions, that are mathematical functions that cannot have any side effect. We start with a classic: The State Monad. As its name suggests, using this object, we will be able to manage the state of a program effectively, without breaking one of the main principles of the paradigm , immutability.
Disclaimer: I will not describe the very basics of functional programmings, such as immutability and referential transparency. The material I present has the primary objective to fix the concepts and the reasoning that are needed to understand the basic Monads.
I will use Scala, because I don’t know Haskell (but, it is in my todo list) and because it is a language I love (coming from Java ecosystem). You can agree, or in disagreement with me. I don’t mind ;)
First of all, we need a program with some state to mutate during its execution. As an example, let’s model a simple representation of a stock portfolio. A stock portfolio is a map that associate stock’s names to some stocks owned.
In our representation of reality, a client can perform three operations on her stock portfolio: To buy more stocks; To sell owned stocks; To get the number of stocks owned. As we know that in the functional programming object are immutable, the three functions cannot have any side effect on their input. So, all of the functions must also return the updated bank account.
We imagine to live in a colored world, full of funny and unicorns, so our portfolio always contains some stocks for the given name.
Now that we defined our essential functions, we want to create another function that composes them to create a new use case:
- Selling all the stocks for a given company
- Using the sell’s revenue, buying stocks of another company
- Returning the number of stocks of the first type owned, and the quantity of the newly purchased stocks
Using nothing more than the functions
buy, we can develop the new function as follows.
Despite the simplicity of the above code, you will have undoubtedly noticed that we have to pass manually the correct reference to the updated stocks portfolio to every step of our algorithm. This kind of programming is very tedious and error prone.
We need a mechanism to compose in a smarter way functions that deal with the status of an application. The best would be not to have to worry at all about passing the status of our application from one function call to another.
Awkwardness like this is almost always a sign of some missing abstraction waiting to be discovered.
The State Monad helps us in this way.
The path through the Monad
Citing the book “Learn You a Haskell for Great Good!”
We’ll say that a stateful computation is a function that takes some state and returns a value along with some new state.
sell functions already behave in this sense. They return both a value and a new instance of state. However, the function
get returns only a value, without updating the state. No problem. It is easy to change its definition to let the function return a value and a state: Use the same input state. So the definition of the function
get changes into the following.
The type of the stateful computation quoted above is
S => (A, S), where
S is the state and
A is the value resulting from the execution of the function. The functions of this type are called state actions of state transitions. Hence, we can rewrite the
get functions as follows.
First of all, let’s use some currying to divide inputs into two groups, and to isolate the state.
If we pass to these functions only the first group of inputs, we obtain precisely a set of functions of type
S => (A, S).
The next step is to remove the currying at all. It is not elegant, and we don’t like its syntax ;)
Just to improve the readability of our three functions, let’s define the following type alias.
Our three functions always return a
Double as output. However, to be more elastic, we need the type parameter
A to let a function on
Stocks type to returns any value.
With the new type alias, our functions become the following.
Well, the situation has improved for nothing. What we need now is a better way to compose our functions that we can obtain making the last step through the definition of the State monad: The definition of
The final step: combinator functions
Well the power of programming is composition, the ability to combine different operations to obtain our target result.
The final step we need to do to build our version of the State monad is to define a set of functions that let us combine states smartly, i.e.
The first function we need is
map. As you may already know, the
map function allows applying a function to the type contained in a generic data structure, obtaining a new version of it.
In our case, the
map function is used to transform a
Transaction[A] in a
However, the problem with the
map function is that it tends to accumulate the generic type. For example, the result of the repeated application of
map to a
map(/*... */)(a => map(/*...*/)(/*...*/) is
Transaction[Transaction[_]]. So, we need a function that behaves like
map, but that can flatten the accumulated types: The
flatMap function. Instead of taking a function from
B as a parameter, the
flatMap function takes a function from
Transaction[B] as a parameter.
type Transaction[+A] = Stocks => (A, Stocks), the
flatMap function is defined indeed in this way.
Very well. The last step we miss is to define a function that lifts a value of type
A to the type
Transaction[A]. Think about this function as a factory method in Object-Oriented Programming.
Using the combinators we just defined, we can rewrite the
move method more cleanly.
The presence of the
map and the
flatMap functions allows us to improve further the readability of the code of the
move function, just applying the syntactic sugar of the for-comprehension construct. With the
for...yield syntax, the function becomes the following.
Wow! Now, the code looks like the good imperative code, but it maintains all the remarkable feature of functional code. Supercalifragilisticexpialidocious!!!
It’s time to abstract the above concepts into our monad construct. First of all, we need a type for our monad. Our stocks example uses the type
Stocks to store the state of the application. We need to substitute it with a generic type variable,
Transaction[A] abstracts to type
Once we defined the
State[S, A] type, the
flatMap functions becomes the following.
So, this is our State Monad! Awesome! Moreover, the definition of type
Transaction regarding the type
State allows us to maintain the code of our business function as it is. No change is needed.
If you prefer, you can define a
trait for the type
State. If so, the functions
flatMap become methods of the trait, instead of lonely functions.
Reinventing the wheel
There are a lot of good functional libraries out of there for the Scala language. Both Scalaz and Cats have their implementation of the State Monad. So, the above is only an exercise to acquire a deeper understanding of the State Monad concepts, but it is not ready for production use ;)
In our journey, we started from an application that needs to share some state. Many functions modify this state. Following the functional programming constraints, we tried to avoid the use of mutable state. Using curryfication and first-order functions, we built a framework that allowed us to share the state between different functions. Then, we introduced some combinators, to make the process of composing the previous functions in a more natural, and less error-prone way.
Our final gratification was the definition of the State Monad.
The code I used in this post is available in my GitHub repository, state-monad-example