Immutable State in Real World

Imperative programs use Statements that change the state of the program.
Functional programs avoid changing state and mutable data.

Scala is a multi-paradigm programming language which combines those programming styles, so we are able to use Mutable Data Structures and Immutable Data Structure.

If you want to use Scala to implement purely functional code, you’re going to deal with immutable Data Structure and immutable collections and your program have to be without side effects, using expressions which are referentially transparent.

If you’re used to program with the imperative programming approach, Scala is flexible for that too, so you can use var and mutable collections under scala.collection.mutable._

Just decide which paradigm you’re going to use? I guess you’re interested to FP. 😊

As John De Goes said:

If you mix functional code and non-functional code, then you have to constantly change the way you reason about the code, depending on whether you are in a functional section, or a non-functional section. The process of constantly switching how you reason about the code is mentally exhausting and error-prone.

Mutable State vs Immutable State

The difference between them is summarized in those pictures:

Mutable state

Immutable state

“In FP, we need to know about the whole story of our ADT behaviors. We deal with immutable Data Structures and we extract new data from existing one using compositions to make the scenario of the stories.”

Here is an interesting tweet about immutable data from School of FP:

In this blog, we’ll see how to manipulate states in Functional Programming.

Let’s start!

A pure function takes input and computes it to get an output, but is that enough to solve real World problems? What if we want to implement a game, or to monitor an automaton machine and update its state at the same time of a computation, or to implement a painting application which saves the position of the mouse and do an action (draw) at the same time, or to implement an elevator control system? How could this possibly work using a purely functional manner?

Answer: Implement immutable states!

“Immutable State is about creating the present from the past to prepare for the future. We can choose what we pick from the past in order to create the present, to make it a better past in the future. ” — Wiem Zine

This is exactly what I mean:

case class Education(date: LocalDate, level: String)
case class
Experience(date: LocalDate, subject: String)
case class Skill(date: LocalDate, subject: String)
case class Story(
birthday: LocalDate,
schoolLevel: Option[Education],
experiences: Vector[Experience],
skills: Vector[Skill]
)
def makeStory(oldStory: Story): Story = ??? //TODO: implement the next step in your story

which is the same as:

val makeStory: Story => Story = oldStory => ???

We’re going to create an immutable State, which saves the old State, computes a value and returns it with the updated state.

Let’s compute the age for example!

val makeStory: Story => (Int, Story) =
oldStory =>
(LocalDate.now.getYear - oldStory.birthday.getYear, ???)

And now let’s define a general purpose for this type!

type State[S, A] = S => (A, S)

We can wrap this function in a case class like this:

case class State[S, A](run: S => (A, S))

Now, let’s write again the previous example using State type:

val makeStory: State[Story, Int] =
State( oldStory =>
(LocalDate.now.getYear - oldStory.birthday.getYear, ???))

Assuming that I want to follow the educational level in each stage for a given Person

Those functions update the story and compute the action which is an Option[Education]

def addExperience(experience: Experience): State[Story, 
Option[Education]] =

State(oldState =>
None -> oldState.copy(experiences =
oldState.experiences :+ experience))
def updateEducation(maybeLevel: Option[Education]): State[Story, 
Option[Education]] =

State(oldState =>
maybeLevel -> oldState.copy(schoolLevel = maybeLevel))

def
addSkill(skill: Skill): State[Story, Option[Education]] =
State(oldState => None -> oldState.copy(skills =
oldState.skills :+ skill))

We need to start from the initial Story (from the birth)

val initialStory: Story = 
Story(LocalDate.of(1990, 9, 22), None, Vector.empty, Vector.empty)

The Story has the following events

sealed trait Event
case class GoToSchool(level: String) extends Event
case object FinishSchool extends Event
case class AddExperience(subject: String) extends Event
case class AddSkill(subject: String) extends Event

We’re going to have a set of Events (Scenario) to create the Story (to update the state)

Example:

val scenario: List[Event] = List(
GoToSchool("First Class"),
AddSkill("Painting"),
AddSkill("Football"),
GoToSchool("Second Class"),
AddSkill("Puzzle games"),
...,
GoToSchool("bachelor's degree"),
AddExperience("Waiter"),
AddExperience("Freelancer"),
AddExperience("Travel to London"),
...,
FinishSchool,
AddExperience("Get married"),
AddExperience("Have kids"),
...
)

Let’s complete the function makeStory, it takes an event and returns the educational level: State[Story, Option[Education]]:

I added date in parameter instead of usingLocalDate.now . LocalDate.now make our function non deterministic! and not referential transparent.

This function is referential transparent 😍

def makeStory(event: Event,
date: LocalDate): State[Story, Option[Education]] =
event match {
case GoToSchool(level) =>
updateEducation(Some(Education(date, level)))
case FinishSchool => updateEducation(None)
case AddExperience(subject) =>
addExperience(Experience(date, subject))
case AddSkill(subject) => addSkill(Skill(date, subject))
}

Goal

1- makeStory for every event keeping the previous state.

scenario.map(event => makeStory(event)) // List[State[Story, Unit]]

This will not keep the previous computation! Every element in the list represents a new State. In order to save the state of this list of result, we’re going to have this function, it combines the states of every element:

sequence: List[State[S, A]] => State[S, List[A]]

2- The goal is to see the finalState after computation which describes the whole Story and the educational path with the age. (let’s compute the age too!)

The birthday would be the same in all State, so we need to read it from the state:

def get[S]: State[S, S]

In State[S, A] we‘re going to implement map and flatMap to be able to use and combine the result of the previous computations of our program.

Let’s do it!

case class State[S, A](run: S => (A, S)) { self =>

def flatMap[B](f: A => State[S, B]): State[S, B] =
State(s => {
val (a, s1) = self.run(s)
f(a).run(s1)
})

def map[B](f: A => B): State[S, B] =
flatMap(a => State.pure(f(a)))
  def map2[B, C](fb: State[S, B])(f: (A, B) => C): State[S, C] =
flatMap(a => fb.map(b => f(a, b)))
}
object State {
def pure[S, A](a: A): State[S, A] = State(s => (a, s))

def sequence[S, A](fs: List[State[S, A]]): State[S, List[A]] =
fs.foldRight(point[S, List[A]](List.empty[A])) { (f, acc) =>
f.map2(acc)(_ :: _)
}
  def get[S]: State[S, S] = State(s => (s, s))
}

pure(a) passes through the State without using it, and returns a constant value a with the unchanged state.

Now let’s evaluate the Scenario!

def age(date: LocalDate, birthday: LocalDate): Int =
date.getYear - birthday.getYear
def evaluate(scenario: List[Event],
date: LocalDate): State[Story, (Int, List[Education])] =
for {
education <- State
.sequence(scenario.map(event => makeStory(event, date)))
.map(_.flatten)
state <- State.get
} yield (age(date, state.birthday), education)

Now we can see the result:

println(
s"*** evaluate scenario: ${evaluate(scenario,
LocalDate.now).run(initialStory)}")

Done!

You can improve this program and use it to create a CV 😀

Well I thought about this example when I was writing this blog. I hope that you learned from it, and you enjoyed reading it, I tried to make it as simple as possible.

If you want to see more examples, check those examples: Random Number Generator, Candy machine 🍭 Those are exercises from the red Book (Functional Programming in Scala).

There is also an interesting paper of Philip Wadler that Eric Terreborre mentioned in his talk here. 👋