Learn You a Haskell for Great Good! - Miran Lipovaca [143]
However, some problems are inherently stateful, in that they rely on some state that changes over time. While this isn’t a problem for Haskell, these computations can be a bit tedious to model. That’s why Haskell features the State monad, which makes dealing with stateful problems a breeze, while still keeping everything nice and pure.
When we were looking at random numbers back in Chapter 9, we dealt with functions that took a random generator as a parameter and returned a random number and a new random generator. If we wanted to generate several random numbers, we always needed to use the random generator that a previous function returned along with its result. For example, to create a function that takes a StdGen and tosses a coin three times based on that generator, we did this:
threeCoins :: StdGen -> (Bool, Bool, Bool)
threeCoins gen =
let (firstCoin, newGen) = random gen
(secondCoin, newGen') = random newGen
(thirdCoin, newGen'') = random newGen'
in (firstCoin, secondCoin, thirdCoin)
This function takes a generator gen, and then random gen returns a Bool value along with a new generator. To throw the second coin, we use the new generator, and so on.
In most other languages, we wouldn’t need to return a new generator along with a random number. We could just modify the existing one! But since Haskell is pure, we can’t do that, so we need to take some state, make a result from it and a new state, and then use that new state to generate new results.
You would think that to avoid manually dealing with stateful computations in this way, we would need to give up the purity of Haskell. Well, we don’t have to, since there’s a special little monad called the State monad that handles all this state business for us, without impacting any of the purity that makes Haskell programming so cool.
Stateful Computations
To help demonstrate stateful computations, let’s go ahead and give them a type. We’ll say that a stateful computation is a function that takes some state and returns a value along with some new state. That function has the following type:
s -> (a, s)
s is the type of the state, and a is the result of the stateful computations.
Note
Assignment in most other languages could be thought of as a stateful computation. For instance, when we do x = 5 in an imperative language, it will usually assign the value 5 to the variable x, and it will also have the value 5 as an expression. If you look at that functionally, it’s like a function that takes a state (that is, all the variables that have been assigned previously) and returns a result (in this case, 5) and a new state, which would be all the previous variable mappings plus the newly assigned variable.
This stateful computation—a function that takes a state and returns a result and a new state—can be thought of as a value with a context as well. The actual value is the result, whereas the context is that we must provide some initial state to actually get that result, and that apart from getting a result, we also get a new state.
Stacks and Stones
Say we want to model a stack. A stack is a data structure that contains a bunch of elements and supports exactly two operations:
Pushing an element to the stack, which adds an element onto the top of the stack
Popping an element off the stack, which removes the topmost element from the stack
We’ll use a list to represent our stack, with the head of the list acting as the top of the stack. To help us with our task, we’ll make two functions:
pop will take a stack, pop one item, and return that item as the result. It will also return a new stack, without the popped item.
push will take an item and a stack and then push that item onto the stack. It will return () as its result, along with a new stack.
Here are the functions in use:
type Stack = [Int]
pop :: Stack -> (Int, Stack)
pop (x:xs) = (x, xs)
push ::