Chapter 6: Purely functional state
- Notes: Chapter notes and links to further reading related to the content in this chapter
- FAQ: Questions related to the chapter content. Feel free to add questions and/or answers here related to the chapter.
State in Scalaz
You do not need to understand this more general type if you just want to use
State[S,A]. But the general type has two additional features:
- The start state and end state of a state transition can have different types. That is, it's not necessarily a transition
S => (S, A), but
S1 => (S2, A). The ordinary
Statetype is where
S2are fixed to be the same type.
- It is a monad transformer (see chapter 12). The type of a state transition is not
S => (S, A), but
S => F[(S, A)]for some monad
F(see chapter 11). The monad transformer allows us to bind across
Statein one operation. The ordinary
Statetype is where this monad is fixed to be the identity monad
Pseudorandom number generation
The Wikipedia article on pseudorandom number generators is a good place to start for more information about such generators. It also makes the distinction between random and pseudo-random generation.
There's also a good page on Linear congruential generators, including advantages and disadvantages and links to several implementations in various languages.
Deterministic finite state automata
State data type can be seen as a model of Mealy Machines in the following way. Consider a function
f of a type like
A => State[S, B]. It is a transition function in a Mealy machine where
- The type
Sis the set of states
State[S, B]'s representation is a function of type
S => (B, S). Then the argument to that function is the initial state.
- The type
Ais the input alphabet of the machine.
- The type
Bis the output alphabet of the machine.
f itself is the transition function of the machine. If we expand
A => State[S, B], it is really
A => S => (B, S) under the hood. If we uncurry that, it becomes
(A, S) => (B, S) which is identical to a transition function in a Mealy machine. Specifically, the output is determined both by the state of type
S and the input value of type
Contrast this with a Moore machine, whose output is determined solely by the current state. A Moore machine could be modeled by a data type like the following:
case class Moore[S, I, A](t: (S, I) => S, g: S => A)
Together with an initial state
s of type
Sis the set of states.
Iis the input alphabet.
Ais the output alphabet.
tis the transition function mapping the state and an input value to the next state.
gis the output function mapping each state to the output alphabet.
As with Mealy machines, we could model the transition function and the output function as a single function:
type Moore[S, I, A] = S => (I => S, A)
Since both the transition function
t and the output function
g take a value of type
S, we can take that value as a single argument and from it determine the transition function of type
I => S as well as the output value of type
A at the same time.
Mealy and Moore machines are related in a way that is interesting to explore.
If we specialize
Moore so that the input and output types are the same, we get a pair of functions
t: (S, A) => S and
g: S => A. We can view these as (respectively) a "getter" and a "setter" of
A values on the type
get: S => A set: (S, A) => S
Imagine for example where
type Name = String case class Person(name: Name, age: Int)
getName would have the type
Person => Name, and
setName would have the type
(Person, Name) => Person. In the latter case, given a
Person and a
Name, we can set the
name of the
Person and get a new
Person with the new
The getter and setter together form what's called a lens. A lens "focuses" on a part of a larger structure, and allows us to modify the value under focus. A simple model of lenses is:
case class Lens[A, B](get: A => B, set: (A, B) => A)
A is the larger structure, and
B is the part of that structure that is under focus.
Importantly, lenses compose. That is, if you have a
Lens[A,B], and a
Lens[B,C], you can get a composite
Lens[A,C] that focuses on a
C of a
B of an
Lenses are handy to use with the
State data type. Given a
State[S,A]. If we're interested in looking at or modifying a portion of the state, and the portion has type
T, it can be useful to focus on a portion of the state that we're interested in using a
Lens[S,T]. The getter and setter of a lens can be readily converted to a
def getS[S,A](l: Lens[S, A]): State[S,A] = State(s => (l.get(s), s)) def setS[S,A](l: Lens[S, A], a: A): State[S,Unit] = State(s => ((), l.set(s, a)))
We cannot, however, turn a
State action into a
Lens, for the same reason that we cannot convert a Moore machine into a Mealy machine.
Stack overflow issues in State
State data type as represented in chapter 6 suffers from a problem with stack overflows for long-running state machines. The problem is that
flatMap contains a function call that is in tail position, but this tail call is not eliminated on the JVM.
The solution is to use a trampoline. Chapter 13 gives a detailed explanation of this technique. See also Rúnar's paper "Stackless Scala With Free Monads".
Using the trampolining data type
TailRec from chapter 13, a stack-safe
State data type could be written as follows:
case class State[S,A](run: S => TailRec[(A, S)])
This is identical to the
State data type we present in chapter 6, except that the result type of
TailRec[(S,A)] instead of just
(S,A). See chapter 13 for a thorough discussion of
TailRec. The important part is that the result type of the
State transition function needs to be a data type like
TailRec that gets run at a later time by a tail recursive trampoline function.