Putting functional programming to work

James Earl Douglas

June 26, 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 analogous) example

Problem space

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

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.

State change as a side effect

var account: List[Float] = ...

def deposit(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) }

Improvements

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

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:

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

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