Putting functional programming to work

James Earl Douglas

October 13, 2014

Abstract

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 RW analogous) example

Problem space

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

Ugh, 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.

State change as a side effect

var account: List[Float] = ...

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

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

Drawbacks

State change as a computational effect

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

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

Improvements

Representing a state action

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

A State wraps a function run which, given a state S, performs some computation and produces both an A and a new state 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 other 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

Safety

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

* 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)

Reusability

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

Interpreter

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

def run(x: Tx[(Float,Float)]): ((Float,Float),List[Float]) = {
  db.beginTransaction()
  val account = db.getAccount(...)
  val ((w,b),account2) = x.run(account)
  db.updateAccount(account2)
  db.commitTransaction(...)
  ((w,b),account2)
}

Problems

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