Abstract

• Functional programming* promises safety, composability, and reusability
• Let's connect these ideas with real-world** code

This is an adaptation of Real-World Functional Programming.

Words mean stuff

Functional programming*

* consider FP ≈ referential transparency

Real-world**

** for readability, we'll use a simplified (but analogous) example

Problem space

Consider a banking ATM. A user should be able to:

• Check their balance
• Deposit funds
• Withdraw funds (and charge a fee)

Why another ATM example?

Accurate handling of state is kind of important, because money.

Data types

We'll track a bank account as a simple transaction register.

• The type of each individual contribution and deduction is Float
• The type of an account is List[Float]

State change as a side effect

var account: List[Float] = ...

def deposit(x: Float): Float = {
  account = account :+ x
  account.sum
}

Drawbacks

• Mutable: account reference can change any time
• Imperative: evaluating deposit makes the transaction happen
• Inconsistent: account reference is accessed multiple times

State change as a computational effect

def deposit(x: Float): List[Float] => (Float, List[Float]) =
  { account => (account.sum, account :+ x) }

Improvements

• Immutable: account reference can not change
• Declarative: evaluating deposit does not run the transaction
• Consistent: account accesses are certain to be identical

Representing a state action

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

A State wraps a function run which, given an S, performs some computation and produces both an A and a new S.

Composing with pure functions

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

  def map[B](f: A => B): State[S,B] =
    State { run andThen { case (a,s) => (f(a), s) } }

}

map builds a new state action that, once run, has its output run through f, converting it from an A to a B.

Composing with pure functions

type Tx[A] = State[List[Float],A]

val balance: Tx[Float] =
  State { account => (account.sum, account) }

val report: Tx[String] =
  balance map { x: Float => "Your balance is " + x }

Composing with state actions

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

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

}

flatMap builds a new state action that, once run, uses the output to compute the result of another state action.

Composing with state actions

def deduct(x: Float): Tx[Float] =
  State { account =>
    if (account.sum >= x) (x, account :+ (-x))
    else (0, account)
  }

def deductWithFee(x: Float]: Tx[Float] =
  deduct(x) flatMap { y =>
    State { account =>
      val fee = 3
      (y + fee, account :+ (-fee))
    }
  }

The state monad

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

  def map[B](f: A => B): State[S,B] =
    State { run andThen { case (a,s) => (f(a), s) } }

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

}

The claims

• Safe
• Composable
• Reusable

Safety

def contribute(x: Float): Tx[Unit] =
  State { account => ((), account :+ x) }

• No mutable references (i.e. var account = ...)
• No mutable data structures (e.g. account.append(...))
• State actions are necessarily atomic
• State actions are optionally transactional*

* Depending on the later implementation of an interpreter

Composability

def deposit(x: Float): Tx[(Float,Float)] =
  for {
    _ <- contribute(x) // Tx[Unit]
    b <- balance       // Tx[Float]
  } yield (0,b)

def withdraw(x: Float): Tx[(Float,Float)] =
  for {
    w <- deduct(x)     // Tx[Float]
    b <- balance       // Tx[Float]
  } yield (w,b)

• Big state actions can be constructed from little state actions
• Composition induces no side effects
• Composition triggers no state transitions

Reusability

 def depositThenWithdraw(d: Float, w: Float): Tx[(Float,Float)] =
  for {
    _ <- deposit(d)  // Tx[(Float,Float)]
    w <- withdraw(w) // Tx[(Float,Float)]
  } yield w

• State actions can be composed in different ways to create different behavior

Interpreter

To make it go, we need a way to run a state action:

var account: List[Float] = Nil

def run(x: Tx[(Float,Float)]): ((Float,Float),List[Float]) = {
  val ((w,b),a) = x.run(account)
  account = a
  ((w,b),a)
}

Uh oh, there's that pesky var again...

Problems

• Synchronizing access to mutable references
• Wrapping state actions in transactions

Solutions

We can't escape mutability, but we can push it to the outer edges of our program, and tailor the interpreter to the mechanism of state persistence.

Demo