Функциональное состояние

Базовый шаблон, как сделать любой API с отслеживанием состояния чисто функциональным, выглядит так:

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

object State:
  extension [S, A](underlying: State[S, A])
    def run(s: S): (A, S) = underlying(s)

  def apply[S, A](f: S => (A, S)): State[S, A] = f

Здесь State — это сокращение от вычисления, которое переносит какое-то состояние, действие состояния, переход состояния или даже оператор.

Помимо определения непрозрачного типа, предоставляется метод расширения run, позволяющий вызывать базовую функцию, а также метод apply для сопутствующего объекта, позволяющий создавать значение State из функции. В обоих случаях известен тот факт, что State[S, A] эквивалентно S ⇒ (A, S), что делает эти две операции простыми и кажущимися избыточными. Однако за пределами определяющей области видимости — например, в другом пакете — эта эквивалентность неизвестна, и, следовательно, нужны такие преобразования.

Резюме

• API с отслеживанием состояния можно смоделировать как чистые функции, которые преобразуют входное состояние в выходное при вычислении значения.
• Тип данных State упрощает работу с API с отслеживанием состояния, устраняя необходимость вручную передавать состояния ввода и вывода во время вычислений.

Пример

Рассмотрим упрощенный пример машины по раздаче конфет.

case class SimpleMachine(candies: Int, coins: Int)

Если в машине остались конфеты и ей заплатить монету, то она выдаст конфету. Количество конфет уменьшиться на 1, а количество монет увеличится на 1. В остальных случаях состояние машины не изменится.

Опишем это функцией вычисления следующего состояния машины:

case class SimpleMachine(candies: Int, coins: Int):
  self =>

  lazy val next: SimpleMachine =
    if candies <= 0 then self
    else SimpleMachine(candies - 1, coins + 1)

Определим State, вычисляющий значение - количество заработанных монет:

val state: State[SimpleMachine, Int] = State(sm => (sm.coins + 1, sm.next))

Здесь используется метод apply, создающий значение State из функции.

Запустить вычисление значения и следующего состояния можно, вызвав run:

val initial = SimpleMachine(100, 0)
state.run(initial)
// (1, SimpleMachine(99, 1))

Функции общего назначения

Функции общего назначения, описывающие шаблоны программ с отслеживанием состояния.

map

map позволяет при наличии базового шаблона State[S, A] и функции преобразования значения из типа A в тип B получать State[S, B] - преобразование входного состояния в выходное с вычислением значения типа B.

object State:
  extension [S, A](underlying: State[S, A])
    def map[B](f: A => B): State[S, B] =
      s =>
        val (a, s1) = run(s)
        (f(a), s1)

Пример:

val stateB = state.map(coins => s"Заработано $coins монет")
stateB.run(initial)
// (Заработано 1 монет, SimpleMachine(99, 1))

map2

map2 позволяет объединять два State в один при наличии функции объединения входящих значений.

object State:
  extension [S, A](underlying: State[S, A])
    def map2[B, C](sb: State[S, B])(f: (A, B) => C): State[S, C] =
      s0 =>
        val (a, s1) = run(s0)
        val (b, s2) = sb.run(s1)
        (f(a, b), s2)

Пример:

val stateA =
  State[SimpleMachine, String](sm => ("Первое изменение", sm.next))
val stateB =
  State[SimpleMachine, String](sm => (", Второе изменение", sm.next))
val stateC = stateA.map2(stateB)(_ + _)

stateC.run(initial)
// (Первое изменение, Второе изменение, SimpleMachine(98, 2))

flatMap

flatMap позволяет при наличии функции преобразования значения в новый State получать этот State:

object State:
  extension [S, A](underlying: State[S, A])
    def flatMap[B](f: A => State[S, B]): State[S, B] =
      s0 =>
        val (a, s1) = run(s0)
        f(a)(s1)

Пример:

val stateA = State[SimpleMachine, Int](sm => (sm.candies - 1, sm.next))
val f: Int => State[SimpleMachine, String] = candies =>
  if candies <= 0 then State(sm => ("Конфеты кончились", sm))
  else State(sm => ("Конфеты ещё есть", sm))

val stateB = stateA.flatMap(f)

stateB.run(initial)
// (Конфеты ещё есть, SimpleMachine(99, 1))

for comprehension

При наличии у State методов map и flatMap можно использовать синтаксический сахар:

val stateB =
  for
    candies <- stateA
    message <- f(candies)
  yield message

stateB.run(initial)
// (Конфеты ещё есть, SimpleMachine(99, 1))

unit

unit оборачивает любое значение в очень простой State, не изменяющий состояние:

object State:
  def unit[S, A](a: A): State[S, A] =
    s => (a, s)

Пример:

val stateA = State.unit[SimpleMachine, String]("Сообщение")
stateA.run(initial)
// (Сообщение, SimpleMachine(100, 0))

get, set и modify

• get нужен для получения текущего состояния
• set - для замены старого состояния новым
• а modify - для изменения состояния (основан на двух предыдущих)

object State:
  def get[S]: State[S, S] = s => (s, s)

  def set[S](s: S): State[S, Unit] = _ => ((), s)

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

Пример:

val initial = SimpleMachine(100, 0)
val other   = SimpleMachine(0, 100)

State.get[SimpleMachine].run(initial)
// (SimpleMachine(100, 0), SimpleMachine(100, 0))

State.set(other).run(initial)
// ((), SimpleMachine(0, 100))

State.modify[SimpleMachine](_.next).run(initial)
// ((), SimpleMachine(99, 1))

traverse и sequence

traverse и sequence необходимы для обработки коллекции операций с состоянием.

object State:
  def sequence[S, A](list: List[State[S, A]]): State[S, List[A]] =
    traverse(list)(identity)

  def traverse[S, A, B](as: List[A])(f: A => State[S, B]): State[S, List[B]] =
    as.foldRight(unit[S, List[B]](Nil))((a, acc) => f(a).map2(acc)(_ :: _))

Автомат, моделирующий раздачу конфет

Давайте реализуем более сложный автомат, моделирующий простой раздатчик конфет. Автомат имеет два типа входа: можно вставить монету или повернуть ручку, чтобы выдать конфету. Он может находиться в одном из двух состояний: заблокировано или разблокировано. Он также отслеживает, сколько конфет осталось и сколько монет в нем содержится:

enum Input:
  case Coin, Turn
 
case class Machine(locked: Boolean, candies: Int, coins: Int)

Правила работы машины следующие:

• (а) Если вставить монету в заблокированный автомат, он разблокируется, если в нем остались конфеты.
• (б) Если повернуть ручку на разблокированном автомате, он выдаст конфеты и заблокируется.
• (в) Поворот ручки на заблокированном автомате или вставка монеты в разблокированный автомат ничего не дает.
• (г) Машина, в которой закончились конфеты, игнорирует все входные данные.

Для начала создадим функцию, которая реализует правила выше и по переданному Input-у возвращает функцию изменения состояния машины:

object Candy:
  private val updateMachine: Input => Machine => Machine =
    (i: Input) =>
      (s: Machine) =>
        (i, s) match
          case (_, Machine(_, 0, _))              => s      // (г)
          case (Input.Coin, Machine(false, _, _)) => s      // (в)
          case (Input.Turn, Machine(true, _, _))  => s      // (в)
          case (Input.Coin, Machine(true, candy, coin)) =>  // (а)
            Machine(false, candy, coin + 1)
          case (Input.Turn, Machine(false, candy, coin)) => // (б)
            Machine(true, candy - 1, coin)

Теперь создадим метод simulateMachine, который управляет машиной на основе списка входных данных и возвращает количество монет и конфет, оставшихся в машине в конце:

object Candy:
  def simulateMachine(inputs: List[Input]): State[Machine, (Int, Int)] =
    for
      _ <- State.traverse(inputs)(input => State.modify(updateMachine(input)))
      s <- State.get
    yield (s.coins, s.candies)

Первая строка State.traverse(inputs)(input => State.modify(updateMachine(input))) возвращает State, преобразующий входное состояние машины в выходное с вычислением значения типа List[Unit], которое нас не интересует. Вторая строка возвращает выходное состояние в качестве значения. Из выходного состояния мы можем получить итоговое количество монет и конфет после всех преобразований.

Итого

Метод simulateMachine по списку операций (вставить монету или повернуть ручку) возвращает State[Machine, (Int, Int)] - по своей сути функцию с типом Machine => ((Int, Int), Machine). Осталось только её запустить.

Например, если входные данные Machine содержат 10 монет и 5 конфет и всего успешно куплено 4 конфеты, то получим следующие выходные данные (14, 1):

val initialMachine = Machine(true, 5, 10)

val inputs =
  List(Coin, Turn, Coin, Coin, Coin, Turn, Turn, Turn, Coin, Turn, Coin, Turn)

val runner = Candy.simulateMachine(inputs)
runner.run(initialMachine)
// ((14, 1), Machine(true, 1, 14))

4 и 5 операции - повторная вставка монеты, а также 7 и 8 - поворачивание ручки на заблокированном автомате, не изменяют состояния, поэтому на выходе получаем результат успешной покупки 4 конфет.

Реализация

Реализация в Cats

import cats.data.State

val step1 = State[Int, String]{ num =>
  val ans = num + 1
  (ans, s"Result of step1: $ans")
}

val step2 = State[Int, String]{ num =>
  val ans = num * 2
  (ans, s"Result of step2: $ans")
}

val both = for {
  a <- step1
  b <- step2
} yield (a, b)

val (state, result) = both.run(20).value
// val state: Int = 42
// val result: (String, String) = (Result of step1: 21,Result of step2: 42)

Ссылки:

• Cats
• Functional Programming in Scala, Second Edition, Chapter 6
• Herding Cats
• Scala with Cats