Pure functional state

Let’s start with Scala/Java’s built-in random number generator.

val rng = new Random()
println(rng.nextInt(6))  // Two calls, get different results.
println(rng.nextInt(6))  
Copy the code

This rng.nextint (6) is not referential transparent because the state seed inside the Random object changes in the form of side effects that are not visible to the user. Each call to nextInt means that the internal state is destroyed (this erases the previous state of the seed, making the state untraceable). Functions like these are difficult to test, combine, modularize, and parallelize.

The key to restoring reference transparency is to make status updates explicit. Do not update the state as a side effect, but return a new state along with the generated value.

trait RandomNrGen :
  def nextInt : (Int.RandomNrGen)
Copy the code

Instead of just returning a new random number, nextInt now returns a random number and a new state, leaving the previous state unchanged.

In this way, state changes are no longer carried out by erasing, but by deriving from the next state. In this way, nextInt callers have the opportunity to reuse the same state. Ideally, the state itself is still encapsulated and API users do not need to know the details of state delivery.

The idea of transitive state can also be applied to tail recursive functions of cumulative computation: the cumulative process is propagated by means of implicit parameters. This routine can optimize some of the non-tail recursive functions to be tail recursive, thus avoiding the risk of stack overflow, and the user can not pay attention to the accumulation process. For example, the tail recursive implementation of the Fibonacci sequence:

// Fold to the right.
@tailrec
def fib(n : Int)(using left : Int = 0, right : Int = 1, list : LazyList[Int] = LazyList(0.1).take(n)) : List[Int] =
  if(n <= 2) list.toList else fib(n- 1)(using right,left + right,list :+ (right + left))

// The user can ignore the middle states of left, right, and list.
// 0, 1, 1, 2, 3, 5, 8...
fib(40)
Copy the code

Here is a linear congruence generator implemented in Scala. It doesn’t matter how the seed is computed, just note that nextInt generates a binary: a random number calculated based on the current state, and the next state.

case class SimpleRandomNrGen(seed : Long) extends RandomNrGen :
  private val nexus: Long = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFL
  private lazy val nextRandomNrGen: SimpleRandomNrGen = SimpleRandomNrGen(nexus)
  override def nextInt: (Int.RandomNrGen) = ((nexus >>> 16).toInt,nextRandomNrGen)
Copy the code

Note that nextRandomNrGen must be declared lazy-loaded, otherwise the application will recursively call apply until the stack overflows when the instance is created. See:

Now, nextInt calls to the same random number generator will be idempotent. It has reference transparency, so as long as the state of the generator remains unchanged, the generated random number must be the same. Therefore, can be simpleRandomNrGen. NextInt as a fixed value the value.

val simpleRandomNrGen = SimpleRandomNrGen(3789012)
val (n,_) = simpleRandomNrGen.nextInt
val (m,_) = simpleRandomNrGen.nextInt

println(n == m)
Copy the code

By calling the SimpleRandomNrGen of the next state consecutively, successive different random numbers can be obtained, while preserving the state of each call.

val simpleRandomNrGen = SimpleRandomNrGen(3789012)
val (n,nextGen1) = simpleRandomNrGen.nextInt
val (m,nextGen2) = nextGen1.nextInt
val (k,nextGen3) = nextGen2.nextInt
println(s"$n.$m.$k")
Copy the code

You can also build an inert random sequence using the lazy load flow described in the previous chapter.

// After Scala 2.13, Stream is replaced with LazyList.
// #:: is the way to construct a LazyList.
def RandomStream(seed : Long = new Date().getTime)(using gen :RandomNrGen = SimpleRandomNrGen(seed)) : LazyList[Int] =
  gen.nextInt._1 #:: RandomStream()(using gen.nextInt._2)
Copy the code

Implement stateless apis in purely functional form

The transformation of stateful apis into this functional style of passing state is not unique to random number generators; it is a general problem that we can all approach in the same way. Such as:

class Obj :
  private var state : Short = 0
  def bar : Int=???// Modifies the state variable.
Copy the code

Assuming that BAR changes state in some form each time, it can be translated into a purely functional API by explicitly declaring the transition to the next state in the function signature:

class Obj2 :
  def bar : (Int.Obj2) =???Copy the code

Of course, there is a performance penalty for calculating the next state using pure functions compared to in-place updates using the direct erase approach. It depends on whether our program needs to preserve state.

First, implement several simple random number generation methods to do the warm-up:

  1. Generation 0 toInt.MaxValue(contains) random number. This can be used%But you need to pay attention to the processingInt.MaxValueIn the case.
  2. To generate a[0, 1)The interval ofDoubleThe number.
  3. generate(Int,Double)Random number pairs, you can use existing methods to achieve.
case class SimpleRandomNrGen(seed: Long = new Date().getTime) extends RandomNrGen :
  // Include this upper bound to prevent overflow [0,bound]
  // We need to consider the limiting case: int.maxValue. If we use the modulo operation, we can get at most Int.MaxValue - 1.
  // So it calculates in the precision of Long, and then converts back to Int.
  override def nonNegativeInt(bound: Int = Int.MaxValue) : (Int.RandomNrGen) =
    val (v, n) = nextInt
    (if v < 0 then (math.abs(v + 1) % (bound.toLong + 1)).toInt else (v % bound.toLong + 1).toInt, n)

  override def _0_1double: (Double.RandomNrGen) =
    val tuple: (Int.RandomNrGen) = nonNegativeInt(bound = 99)
    (tuple._1.toDouble / 100, tuple._2)

object SimpleRandomNrGen:
  // The implementation of the accompanying object version, which receives randomNrGen externally.
  def intDouble(rdmGen : RandomNrGen) : ((Int.Double),RandomNrGen) =
    val (i,nxt) = rdmGen.nextInt
    val (d,nnxt) = nxt._0_1double
    ((i,d),nnxt)
  def nonNegativeInt(randomNrGen: RandomNrGen) : (Int.RandomNrGen) = randomNrGen.nonNegativeInt()
  def _0_1double(randomNrGen : RandomNrGen) : (Double.RandomNrGen) = randomNrGen._0_1double

  // Generate a continuous string of ints
  def RdmIntStream(seed: Long = new Date().getTime, bound: Int = Int.MaxValue)(using gen: RandomNrGen = SimpleRandomNrGen(seed)): LazyList[Int] =
    val (i, nxt) = gen.nonNegativeInt(bound)
    i #:: RdmIntStream(bound = bound)(using nxt.asInstanceOf[SimpleRandomNrGen])

  // generate consecutive Double [0,1) strings
  def Rdm0_1DoubleStream(seed: Long = new Date().getTime)(using gen: RandomNrGen = SimpleRandomNrGen(seed)): LazyList[Double] =
    val (d, nxt) = gen._0_1double
    d #:: Rdm0_1DoubleStream()(using nxt)
Copy the code

Apis with better behavior states

Review all previous implementations. Each of our functions is formally similar:

// S: state
// V: value
(State) = > (V.State)
Copy the code

This type of function is called state transition: changing from one state S to another. For example, the random number generator in this paper can be defined as:

type Rdm[+A] = RandomNrGen= > (A.RandomNrGen)
Copy the code

Note that Rdm[+A] is A function type. The purpose of this type is to shield the user from the state passing process of RamdomNrGen and focus only on the value A. Any function that returns Rdm[A] is A higher-order function. For ease of understanding, we will later call such higher-order functions behavior. Such as:

def f[A] :Rdm[A] =???def f[A](args : Any*) : Rdm[A] =???// You can use free variables.
Copy the code

A concrete implementation of f should be A closure that takes the initial state S as an argument and returns A binary (A,S). Such as:

def f[A] :Rdm[A] = s => 
  val (a,nxt) = s.g    // Get the current value and state from the last s calculation.
  (a,nxt)
Copy the code

Behavior F is not driven until it receives a RandomNrGen, because using higher-order functions is equivalent to implementing the effect of delayed execution through Currization. The delayed execution (or delayed confirmation of parameters) property of Coriation is also used in a final example: simulating finite state machines.

Now, instead of focusing on what (initial) state comes in from the outside world, we focus on the behavior itself and make further abstractions. Behavior itself is A function, so our instinct to think that behavior itself can also be mapped, composed, and nested is correct, and it’s time to do some “infrastructure” for Rdm[+A] types.

First implement the Unit method, which takes a value of A, and then simply passes a fixed randomNrGen state. You can think of the Unit (100) call as a literal; Alternatively, you can think of Unit itself as A lift ** from [A] to Rdm[A].

def unit[A](a: A) :Rdm[A] = randomNrGen => (a, randomNrGen)
Copy the code

The basic Map combinator is then implemented, which is A transformation behavior: extract the result of Rdm[A] behavior, A, map it to B, and pass it on.

def map[A.B](rdm: Rdm[A])(f: A= >B) :Rdm[B] = rdmNrGen =>
  val (a, nxt) = rdm(rdmNrGen)
  (f(a), nxt)
Copy the code

Group, nested state behavior

Map is not powerful enough to express composite behavior. We also need to create another map2 combinator to superimpose two behaviors into one behavior. The implementation is as follows:

def map2[A.B.C](rdmA : Rdm[A],rdmB : Rdm[B])(f : (A.B) = >C) : Rdm[C] =
  randomNrGen =>
	// randomNrGen's state is shifted twice here.
	val (value_A,nxt) = rdmA(randomNrGen)
	val (value_B,nnxt) = rdmB(nxt)
	(f(value_A,value_B),nnxt)
Copy the code

With map2, the above intDouble (or doubleInt, etc.) can be replaced with a very short statement:

def intDouble(firstDo : Rdm[Int],andThen : Rdm[Double) :Rdm[(Int.Double)] = map2(firstDo,andThen)((_,_))
Copy the code

A little layer of generalization to this class of methods yields the both method, which allows random generation of any type of (A,B) pair.

def both[A.B](rdmA : Rdm[A],rdmB : Rdm[B) :Rdm[(A.B)] = map2(rdmA,rdmB)((_,_))
Copy the code

A slightly trickier approach is the Sequence method. This generic combinator has been used several times in previous chapters and stands for “flipping”, such as converting List[Option[A]] to Option[List[A]]. Similarly, here we expect to implement the method of flipping List[Rdm[A]] to Rdm[List[A]] : flipping A sequence of actions that generates A single value to A single action that generates multiple values.

def sequence[A](fs : List[Rdm[A]]) : Rdm[List[A]] =
  fs.foldRight(unit[List[A]] (List[A]())){
    (rdm,acc) => {map2(rdm,acc)(_ :: _)}
  }
Copy the code

The sequence method is based on foldRight provided by map2 and List. Note that right-folded initial values are passed List[A]() rather than Nil, because the latter does not allow the compiler to do effective type inference.

FlatMap is another expressively powerful combinator that provides the ability to nest A combination of Rdm[List[A]] :

  // Rdm[B] = (Rng) => (B,Rng)
  def flatMap[A.B](rdmA : Rdm[A])(f : A= >Rdm[B) :Rdm[B] = rdm =>
    val (value_A,nxt) = rdmA(rdm)
    f(value_A)(nxt)
Copy the code

The next section shows how flatMap implements the Map and MAP2 methods, which is why flatMap is more expressive than the other two. Another important use for implementing flatMap is to enable the Scala compiler to support nested combinations of behavior expressed in for expressions, as well as reduction, as described below.

Refining generic expressions

So far we have implemented the unit, map, map2, flatMap, sequence functions for the random number generator. These are common behaviors in functional programming, regardless of state types. So we extracted a more general signature:

def map[S.A.B](a :S= > (A.S))(f: A= >B) : S= > (B.S)
Copy the code

The previous Rdm[A] can also have A more general form:

type State[S, +A] = S= > (A.S)
Copy the code

Here, State can be used to refer to “State”, or even to the abbreviation of “instruction” statement.

We summarize our experience from the example of writing random number generator and finally complete a general pattern. The three combinators map, map2, and flatMap are implemented in the class definition, and unit and sequence are implemented in the companion object.

case class State[S, +A] (run: S= > (A.S)):
  // When the argument is a single argument, use curly braces {} instead of ().
  def map[B](from: A= >B) :State[S.B] = flatMap { a => unit(from(a)) }

  // Merge with another State to create a new State.
  // With this in mind, you can implement the sequence method with foldRight.
  def map2[B.C](otherState: State[S.B])(zip: (A.B) = >C) :State[S.C] =
	flatMap { a => { otherState.map { b => zip(a, b) }}}

  // The basic combinator. A is used to generate the next state NXT, and the statement containing the next state NXT is returned.
  def flatMap[B](f: A= >State[S.B) :State[S.B] = State { s => val(a, nxt) = run(s); f(a).run(nxt) }object State:
  // Can be thought of as the process of upgrading a single value a: S with another State S to State[S, a].
  // If a is of type List[T], then the unit method is promoted to State[S,List[T]], see sequence.
  def unit[S.A](a: A) :State[S.A] = State { s => (a, s) }

  def sequence[S.A](ss: List[State[S.A]]) :State[S.List[A]] =
    ss.foldRight(unit[S.List[A]] (List[A]()))((statement,acc) => { statement.map2(acc)( _ :: _) })

Copy the code

Map and MAP2 are essentially reusing flatMaps, which contain implicit state transitions. Therefore, all upper-level API logic calls trigger state transitions, but the user doesn’t need to pay much attention to them.

Pure functional command programming with For expressions

In imperative programming, a program is made up of a series of instruction statements. Each instruction can modify the state, and in this chapter each instruction is a function: they take arguments to read the current state of the program and return a value representing the state of the writing program.

Therefore, functional and imperative programming are not opposites, and it is perfectly reasonable to use side-effect free functions to maintain program state. Functional programming also has great support for writing imperative programs, with additional benefits such as programs that can be reasoned by equations.

Map, MAP2, and flatMap ultimate combinators have been implemented previously to handle the propagation of state from one instruction to another. The type of value returned may change as the state changes. Again, using random number generators as an example:

val int = State[RandomNrGen.Int]{_.nextInt}
val action : State[RandomNrGen.List[Int]] = int.flatMap {
  x => int.flatMap {
    y => int.map {
        z => List(x,y,z)
    }
  }
}

// The incoming generator drives the behavior execution.
println(action.run(new SimpleRandomNrGen(3000)))
Copy the code

This code style still looks a little less “imperative”, and it’s not easy to see what the code is doing. Scala’s derivation of for expressions restores the “imperative” style:

val value: State[RandomNrGen.List[Int]] =
for {
  x <- int  // Get x from the int behavior
  y <- int  // Get y from the int behavior
  z <- int  // Get z from the int behavior
} yield List(x, y, z)

// The incoming generator drives the behavior execution.
val(a,nxt) = action.run(new SimpleRandomNrGen(3000))
// Prints a random array
println(a.mkString(","))
Copy the code

The code derived from the for expression is more readable and looks like an imperative, but is actually exactly equivalent to the previous flatMap and map combination.

Further, if we have a get combinator to get the current state, and a set combinator to set the current state, then we can implement a combinator that changes the state in any way:

def modify[S](f : S= >S) :State[S.Unit] = for {
  s <- get
  _ <- set(f(s))
} yield(a)State[S,S] : State[S,S];
def get[S] : State[S.S] = State {s => (s,s)}

// Setting the status is A side effect and does not require A return value, so mark the return value A as Unit.
// () is the literal of Unit.
def set[S](s : S) : State[S.Unit] = State { _ => ((),s)}
Copy the code

The modify behavior optionally modifies state by combining partial functions (also of Function01 type, as mentioned earlier). On the other hand, to facilitate type inference by the compiler, it is best to annotate type parameters explicitly at call time.

modify[RandomNrGen] {case SimpleRandomNrGen(100) = >SimpleRandomNrGen(200)
  case s => s
}.run(new SimpleRandomNrGen(100))
Copy the code

The idea behind this modify action is that if the seed of the incoming generator is 100, replace it with the one of 200.

This demo is still a little clunky. Let’s look at a new example: the candy machine problem.

Simulate finite state machines

This example is the final puzzle for exercise 6.11 in the book. Given the following implementation:

// Scala 2.x can be used to represent algebraic types in traits + case classes.
enum Input:
  case Coin extends Input
  case Turn extends Input

case class Machine(locked : Boolean, candies : Int, coins : Int)
def simulateMachine(inputs : List[Input) :State[Machine, (Int.Int)] =???Copy the code

The machine follows this rule:

  1. To the locked state (locked = true) put a coin into the vending machine, if there is any candy left (coins ! = 0) makes it unlocked.
  2. For an unlocked (locked = false) by inserting a coin into the vending machine, which will give you a candy and then become locked.
  3. Pressing a button on a locked vending machine or putting a coin into an unlocked vending machine does nothing.
  4. The vending machine ignores other inputs (one state at a time, serial) as it outputs candy.

The Input of simulateMachine is very clear, like List(Coin,Turn,Coin,Turn) List[Input], The user expects to extract the (Int,Int) tuple from the last State[Machine,(Int,Int)] output.

The answer to this question can be found at github: fpinscala/11.answer.md at second-edition · fpinscala/fpinscala (github.com). It’s hard to read this code directly, so here’s a step by step analysis.

The candy machine State is wrapped and passed with the State type declared above. This example does not focus on how the intermediate State changes. Instead, set the intermediate State to State[Machine,Unit] (see the previous set method). On the last call, we use a binary to indicate the number of sweets and coins left, and pass the next Machine State (although it will not be used again), which is State[Machine,(Int,Int)].

With these clues in hand, the next step is to deconstruct the intermediate process by which List[Int] is converted to State[Machine,(Int,Int)]. First, List[Inputs] must map to the intermediate State of the Machine: List[State[Machine,Unit]].

// For the moment.
inputs.map{ input  => ??? }
Copy the code

Specific rules for state transitions are implemented according to the requirements of the topic. Before getting started, we noticed that each state transition of the machine can be broken down into three orderly steps:

  1. First confirm the user’s inputInput.
  2. Check the current state of the machineMachine.
  3. Returns the next state of the machineMachine.

We want to integrate these three steps into a function and achieve the effect of delayed validation, so we reintroduce currization here. Its function signature should look like this:

def update: Input= >Machine= >Machine
Copy the code

Improve the logic according to the meaning of the question, and obtain:

def update: Input= >Machine= >Machine = (i: Input) => (s: Machine) =>
  (i, s) match {
    case (_, Machine(_, 0, _)) => s
    case (Coin.Machine(false, _, _)) => s
    case (Turn.Machine(true, _, _)) => s
    case (Coin.Machine(true, candy, coin)) =>
      Machine(false, candy, coin + 1)
    case (Turn.Machine(false, candy, coin)) =>
      Machine(true, candy - 1, coin)
  }
Copy the code

The overall pattern matching describes all of the state transitions, so it can be integrated into the Modify behavior. When update accepts an Input, it does not immediately return the result. Instead, it returns a partial function of Machine => Machine, which corresponds to the f: S => S parameter required for modify.

inputs.map{ input  =>
    val machineToMachine: Machine= >Machine = update(input)
    modify[Machine](machineToMachine)
}
Copy the code

The official web site provides a more compact and abstract implementation of compose, which requires that we be familiar with this class of combinators (or at least distinguish them from andThen: Java 8 Compose and andThen differentiation-csDN). The semantics are equivalent:

// After Scala 3, the process of Eta expansion is automatic and can be written as:
// inputs.map {modify[Machine].compose(update)}

// Compose is evaluated from right to left, implicitly passing the map input parameters to update,
// Get Machine => Machine and pass it to modify[Machine].
inputs.map {modify[Machine] _ compose update}
Copy the code

The last question is how to get the last state. Think about how we used to get the end of the list — create an iterator to iterate over, beginning at the beginning and ending at the end; This is often done through a typical imperative for cycle.

As I’ve hinted before, Scala’s for expression can give an equivalent implementation of the separation of concerns: after “iterating” through all the Input states, the previous GET method is called to assign the last Machine state to S, and then extracts candies and Coins messages from it.

def simulateMachine(inputs : List[Input) :State[Machine, (Int.Int)] = for {
  // Do not care about the intermediate result, set type A to Unit.
  _ <- sequence[Machine.Unit](inputs.map{
    input  =>
    val machineToMachine: Machine= >Machine = update(input)
    modify[Machine](machineToMachine)
  })
  // Get the state of the last moment
  s <- get
} yield (s.candies,s.coins)
Copy the code

A simplified version of this is the source code in the link:

def simulateMachine(inputs: List[Input) :State[Machine, (Int.Int)] = for {
  _ <- sequence(inputs map (modify[Machine] _ compose update))
  s <- get
} yield (s.coins, s.candies)
Copy the code

Here’s a simple test:

val ((candies,coins),machine) = simulateMachine(List(Coin.Turn.Coin.Turn)).run(Machine(true.10.0))
println(s"candies = $candies, coins =$coins")
Copy the code