Understanding FP Concepts via Refactoring

Adam Rosien @arosien
Inner Product LLC inner-product.com

27 Apr 2019

Motivation
Dependencies
Recursive Functions
Recursive Data
Summary

Motivation

Dependencies

A => B

i eat dependencies for breakfast

def getUser(db: Db, uid: UId): User = ???

Curry

def getUser(db: Db):           UId => User = ???

def getUser(db: Db): UId => User = ???

Extract Class

class WithDb(db: Db) {
  def getUser(uid: UId): User = ???
}

def getUser(db: Db):   UId => User = ???

def saveUser(db: Db): User => Unit = ???

class WithDb(db: Db) {
  def getUser(uid: UId):    User = ???
  def saveUser(user: User): Unit = ???
}

Composition

def getThenSave(withDb: WithDb, uid: UId): Unit =
  withDb.saveUser(
    withDb.getUser(uid))

Classes?

( ಠ ʖ̯ ಠ)

def getUser(db: Db):   UId => User = ???

def saveUser(db: Db): User => Unit = ???

Push the dependency “later”

def getUser(uid: UId):    Db => User = ???

def saveUser(user: User): Db => Unit = ???

Composition

saveUser(
  getUser(uid))
// error: type mismatch;
//  found   : repl.Session.App3.Db => repl.Session.App3.User
//  required: repl.Session.App3.User
//     getUser(uid), //         Db => User
//     ^^^^^^^^^^^^

val getThenSave: Db => Unit =
  db =>
    saveUser(
      getUser(uid)(db))( // <-- *same* db here
        db)              // <-- and here

Write a helper

def getThenSave: Db => Unit =
  compose(
    getUser(uid), //         Db => User
    saveUser)     // User => Db => Unit

def compose[Dep, A, B](
  f:      Dep => A,
  g: A => Dep => B): Dep => B =
  dep =>
    g(
      f(dep))(
        dep)

case class Reader[Dep, A](run: Dep => A)

case class Reader[Dep, A](run: Dep => A) {
  def compose[B](that: A => Reader[Dep, B]): Reader[Dep, B] = 
    Reader { dep =>
      that(run(dep))
        .run(dep)
    }
}

Monad!

case class Reader[Dep, A](run: Dep => A) {
  def flatMap[B](f: A => Reader[Dep, B]): Reader[Dep, B] = 
    Reader { dep =>
      f(run(dep))
        .run(dep)
    }
}

def getUser(uid: UId): Reader[Db, User] =
  Reader(db => ???)

def saveUser(user: User): Reader[Db, Unit] =
  Reader(db => ???)

def getThenSave(uid: UId): Reader[Db, Unit] =
  for {
    user  <- getUser(uid)
    saved <- saveUser(user)
  } yield saved

What did we do?

We need our dependencies.

In OOP we can share them via scope (class). Composition is just function composition.

In FP, we want composition for everything: monadic composition for dependency sharing, function composition for logic.

Recursive Functions

Or, refactor like it’s 192x!

def fact(i: Int): Int =
  if (i <= 0) 1
  else i * fact(i - 1)

fact(5)
// res7: Int = 120

def fact(i: Int): Int =
  if (i <= 0) 1
  else i * fact(i - 1)

Recursion is known to cause headaches.

Make it the caller’s problem

def fact0(i: Int, f: Int => Int): Int =
  if (i <= 0) 1
  else i * f(i - 1)

ಠ‿ಠ

def fact0(i: Int, f: Int => Int): Int =
  if (i <= 0) 1
  else i * f(i - 1)

Curry

def fact0(f: Int => Int): Int => Int =
  i =>
    if (i <= 0) 1
    else i * f(i - 1)

fact0(???)(5)

I don’t want a `(Int => Int) => (Int => Int)` function, I want a `Int => Int` function!

Write a helper to do that.

def fact(i: Int): Int =
  Y(fact0)(i)

def fact0(f: Int => Int): Int => Int =
  i =>
    if (i <= 0) 1
    else i * f(i - 1)

def Y[A](f: (A => A) => (A => A)): A => A =
  ???

def Y[A](f: (A => A) => (A => A)): A => A =
  a => f(Y(f))(a)

(⊙_◎)

def Y[A](f: (A => A) => (A => A)): A => A =
  a =>     // A
    f(
      Y(f) // A => A
    )(     // A => A
      a)   // A

val fact: Int => Int =
  Y { f =>
    i => if (i <= 0) 1
         else i * f(i - 1)
  }

fact(5)
// res15: Int = 120

Very clever.

What did we do?

Locally, recursion itself can be an extraneous detail.

Factor it out, use a helper to put it back in.

(convert explicit recursion to continuation passing)

But wait, there’s more!

That helper can now do more than just recurse!

It can cache (memoize). It can do X.

And your code doesn’t know about any of it.

Recursive Data

DO NOT PANIC

sealed trait Bool
object Bool {
  case object True extends Bool
  case object False extends Bool
  case class And(l: Bool, r: Bool) extends Bool
  case class Or(l: Bool, r: Bool) extends Bool
  case class Not(b: Bool) extends Bool
}

def eval(b: Bool): Boolean =
  b match {
    case Bool.True      => true
    case Bool.False     => false
    case Bool.And(l, r) => eval(l) && eval(r)
    case Bool.Or(l, r)  => eval(l) || eval(r)
    case Bool.Not(b)    => !eval(b)
  }

eval(Bool.Not(Bool.And(Bool.True, Bool.False)))
// res16: Boolean = true

def pretty(b: Bool): String =
  b match {
    case Bool.True      => "true"
    case Bool.False     => "false"
    case Bool.And(l, r) => s"(${pretty(l)} && ${pretty(r)})"
    case Bool.Or(l, r)  => s"(${pretty(l)} || ${pretty(r)})"
    case Bool.Not(b)    => s"!${pretty(b)}"
  }

pretty(Bool.Not(Bool.And(Bool.True, Bool.False)))
// res17: String = "!(true && false)"

def eval(b: Bool): Boolean =
  b match {
    case Bool.True      => true
    case Bool.False     => false
    case Bool.And(l, r) => eval(l) && eval(r)
    case Bool.Or(l, r)  => eval(l) || eval(r)
    case Bool.Not(b)    => !eval(b)          
  }

sealed trait BoolF[A]
object BoolF {
  case class True[A]() extends BoolF[A]
  case class False[A]() extends BoolF[A]
  case class And[A](l: A, r: A) extends BoolF[A]
  case class Or[A](l: A, r: A) extends BoolF[A]
  case class Not[A](b: A) extends BoolF[A]
}

Recursion is not my data’s problem anymore!

with some helpers to fix type inference…

BoolF.not(
  BoolF.and(
    BoolF.`true`,
    BoolF.`false`))
// res20: BoolF[BoolF[BoolF[Nothing]]] = Not(And(True(), False()))

Problem: BoolF[BoolF[BoolF[BoolF[...

Put the recursion in helper data

case class Fix[F[_]](unfix: F[Fix[F]])

type Bool2 = Fix[BoolF]

val expr: Bool2 =
  Fix(BoolF.not(
    Fix(BoolF.and(
      Fix(BoolF.`true`),
      Fix(BoolF.`false`)))))

def eval2(b: BoolF[String]): String =
  b match {
    case BoolF.True()    => "true"
    case BoolF.False()   => "false"
    case BoolF.And(l, r) => s"($l && $r)"
    case BoolF.Or(l, r)  => s"($l || $r)"
    case BoolF.Not(b)    => s"!$b"
  }

No recursion in our interpreter!

What did we do

No recursion in our data.

No recursion in our interpreter(s).

Recursion Schemes encapsulate recursive traversals.

Summary

Dependency Injection

Do less in your functions: externalize dependencies.

(but not with scope, please!)

Provide them later:

via function parameters

en masse with the Reader Monad

Recursion (in functions)

Do less in your functions: receive the thing that does the recursion.

(recursion-as-a-dependency, recursion-as-a-service)

The Y-combinator is the basic technique.

You can then have this passed-in capability do more, without changing your core logic.

Recursion (in data)

Simplify your modeling primitives (algebras).

Simplify your interpreters.

Recursion Schemes glue it all together and provide flexible processing.

When you have a local problem…

make it the caller’s problem.

Then hide that problem from the caller’s caller.

These are functional programming abstractions.

They come from refactoring.

Thank you!

Adam Rosien @arosien

Inner Product LLC inner-product.com

Hire us to teach your team! ☝︎

Understanding FP Concepts via Refactoring

Motivation

Dependencies

Composition

Classes?

Composition

Monad!

What did we do?

Recursive Functions

Or, refactor like it’s 192x!

I don’t want a (Int => Int) => (Int => Int) function, I want a Int => Int function!

What did we do?

But wait, there’s more!

Recursive Data

DO NOT PANIC

What did we do

Summary

Dependency Injection

Recursion (in functions)

Recursion (in data)

Thank you!

I don’t want a `(Int => Int) => (Int => Int)` function, I want a `Int => Int` function!