Principles of Clean Functional Programming

Karl Bielefeldt

LambdaConf 2017 video

@softwarewhys

About me:

  • Embedded progammer roots
  • Microservices platform future

Agenda

  • General Tips
  • Principles you already know from imperative programming
  • Principles specific to functional programming
    • General
    • Iteration
    • Opportunities from immutability

Notes:

  • Not hard and fast rules
  • Examples are for readability
  • This talk only shows what to do, not how

General Tips

  • Don't stick with your first draft.
  • Build your repetoire of functions.
  • Don't forget to practice the "easy" parts.

Principles from imperative programming

Don't repeat yourself

// http://stackoverflow.com/q/36413148/389146
var typeName: String = ""
if (stringTypes.contains(label)) {
  typeName = "string"
} else if (floatingTypes.contains(label)) {
  typeName = "float"
} else if (encodingTypes.contains(label)) {
  typeName = "encoding"
} else if (rangeTypes.contains(label)) {
  typeName = "range"
}
val types = Map(stringTypes -> "string",
        floatingTypes -> "float",
        encodingTypes -> "encoding",
        rangeTypes    -> "range")

types find (_._1 contains label) map (_._2)
    getOrElse "label not found"

More principles from imperative programming

  • Don't nest excessively.
  • Use small functions.
// http://softwareengineering.stackexchange.com/a/342038/3965
const obj1 = { a:1, b:2, c:3, d:3 };
const obj2 = { a:1, b:1, e:2, f:2, g:3, h:5 };

const getXs = (obj, getX) =>
  Object.keys(obj).map(key => getX(obj)(key));

const getPctSameXs = (getX, filter = vals => vals) =>
  (objA, objB) =>
    filter(getXs(objB, getX))
      .reduce(
        (numSame, x) =>
          getXs(objA, getX).indexOf(x) > -1 ? numSame + 1 :
            numSame, 0
      ) / Object.keys(objA).length * 100;

const pctSameKeys =
    getPctSameXs(obj => key => key);
const pctSameValsDups =
    getPctSameXs(obj => key => obj[key]);
const pctSameValsNoDups =
    getPctSameXs(obj => key => obj[key],
        vals => [...new Set(vals)]);
const pctSameProps = getPctSameXs(obj => key =>
    JSON.stringify( {[key]: obj[key]} ));
function mapObject(obj, f) {
  return Object.keys(obj).map(key => f(obj, key));
}

function getPercentSame(obj1, obj2, f) {
  const mapped1 = mapObject(obj1, f);
  const mapped2 = mapObject(obj2, f);
  const same = mapped1.filter(x => mapped2.indexOf(x) != -1);
  const percent = same.length / mapped1.length * 100;
  return percent;
}

const getValues = (obj, key) => obj[key];
const valuesWithDupsPercent =
    getPercentSame(obj1, obj2, getValues);

Principles specific to functional programming

  • General
  • Iteration
  • Opportunities from immutability

General

Isolate I/O

Pure functions are easier to:

Reorder

Refactor

Parallelize

Typecheck

Share data between

Test

Compose

val conversions = List(
  (1000, "M"),
  (900,  "CM"),
  (500,  "D"),
  (400,  "CD"),
  (100,  "C"),
  (90,   "XC"),
  (50,   "L"),
  (40,   "XL"),
  (10,   "X"),
  (9,    "IX"),
  (5,    "V"),
  (4,    "IV"),
  (1,    "I"))

def intToRoman(number: Int): Unit = {
  if (number == 0) {
    println()
  } else {
    val (decimal, roman) =
      (conversions dropWhile (_._1 > number)).head

    print(roman)
    intToRoman(number - decimal)
  }
}
def intToRoman(number: Int): String = {
  if (number == 0) {
    ""
  } else {
    val (decimal, roman) =
      (conversions dropWhile (_._1 > number)).head

    roman + intToRoman(number - decimal)
  }
}

def printRoman = intToRoman _ andThen println

Don't try to eliminate all intermediate variables

// http://stackoverflow.com/a/15195230/389146
def foo(arguments: Seq[(String, String)],
        merges: Seq[(String, String)]) =
{
    val metadata: Seq[Attribute] = (arguments ++ merges)
    .groupBy(_._1)
    .map {
        case (key, value) =>
            Attribute(None, key,
                Text(value.map(_._2).mkString(" ") ), Null)
    }

    var result: MetaData = Null
    for(m <- metadata) result = result.append( m )
    result
}
def foo(arguments: Seq[(String, String)],
        merges: Seq[(String, String)]) =
  (arguments ++ merges).groupBy(_._1).map {
    case (key, value) => Attribute(None, key,
        Text(value.map(_._2).mkString(" ")), Null)
  }.fold(Null)((soFar, attr) => soFar append attr)

def foo(arguments: Seq[(String, String)], merges: Seq[(String, String)]) =
  (arguments ++ merges).groupBy(_._1).map {
    case (key, value) => Attribute(None, key, Text(value.map(_._2).mkString(" ")), Null)
  }.fold(Null)((soFar, attr) => soFar append attr)
type PairSeq = Seq[(String, String)]

def combineText(text: PairSeq): Text =
  Text(text.map(_._2).mkString(" "))

def foo(arguments: PairSeq, merges: PairSeq) = {
  val metadata = (arguments ++ merges)
    .groupBy(_._1)
    .map{case (key, value) =>
        Attribute(None, key, combineText(value), Null)
    }

  metadata.fold(Null)((xs, attr) => xs append attr)
}

Minimize pattern matching for standard library types

  • Overly general tool
  • Verbose and repetitive syntax
  • Easier to make error that typechecker can't catch
  • Often reinventing the wheel
When to use pattern matching?
  • When you need exhaustive matching on a sum type.
  • When you are extracting values on the left that are used on the right, especially complex nested extractions.
  • When there aren't existing more tailored functions that fit better.
  • When you've written it both ways and found it significantly cleaner.
def intToRoman(number: Int): String = {
  if (number == 0) {
    ""
  } else {
    val (decimal, roman) = number match {
      case x if x > 1000 => (1000, "M")
      case x if x > 900  => (900,  "CM")
      case x if x > 500  => (500,  "D")
      case x if x > 400  => (400,  "CD")
      case x if x > 100  => (100,  "C")
      case x if x > 90   => (90,   "XC")
      case x if x > 50   => (50,   "L")
      case x if x > 40   => (40,   "XL")
      case x if x > 10   => (10,   "X")
      case x if x > 9    => (9,    "IX")
      case x if x > 5    => (5,    "V")
      case x if x > 4    => (4,    "IV")
      case _             => (1,    "I")
    }

    roman + intToRoman(number - decimal)
  }
}
val conversions = List(
      (1000, "M"),
      (900,  "CM"),
      (500,  "D"),
      (400,  "CD"),
      (100,  "C"),
      (90,   "XC"),
      (50,   "L"),
      (40,   "XL"),
      (10,   "X"),
      (9,    "IX"),
      (5,    "V"),
      (4,    "IV"),
      (1,    "I"))

def intToRoman(number: Int): String = {
  if (number == 0) {
    ""
  } else {
    val (decimal, roman) =
    (conversions dropWhile (_._1 > number)).head

    roman + intToRoman(number - decimal)
  }
}

Don’t overuse lambdas

const obj1 = { a:1, b:2, c:3, d:3 };
const obj2 = { a:1, b:1, e:2, f:2, g:3, h:5 };

const getXs = (obj, getX) =>
  Object.keys(obj).map(key => getX(obj)(key));

const getPctSameXs = (getX, filter = vals => vals) =>
  (objA, objB) =>
    filter(getXs(objB, getX))
      .reduce(
        (numSame, x) =>
          getXs(objA, getX).indexOf(x) > -1 ? numSame + 1 :
            numSame, 0
      ) / Object.keys(objA).length * 100;

const pctSameKeys =
    getPctSameXs(obj => key => key);
const pctSameValsDups =
    getPctSameXs(obj => key => obj[key]);
const pctSameValsNoDups =
    getPctSameXs(obj => key => obj[key],
        vals => [...new Set(vals)]);
const pctSameProps = getPctSameXs(obj => key =>
    JSON.stringify( {[key]: obj[key]} ));
function mapObject(obj, f) {
  return Object.keys(obj).map(key => f(obj, key));
}

function getPercentSame(obj1, obj2, f) {
  const mapped1 = mapObject(obj1, f);
  const mapped2 = mapObject(obj2, f);
  const same = mapped1.filter(x => mapped2.indexOf(x) != -1);
  const percent = same.length / mapped1.length * 100;
  return percent;
}

const getValues = (obj, key) => obj[key];
const valuesWithDupsPercent =
    getPercentSame(obj1, obj2, getValues);

Don't jump out and back into monads

val in: Option[String] = ???
val out: Option[Int] = in match {
  case Some(x) => Try(x.toInt).toOption
  case None    => None
}
 Try(x.toInt).toOption}

Iteration

Functional programming doesn't have imperative loops like while and for loops, so instead we usually use                  .
Functional programming doesn't have imperative loops like while and for loops, so instead we usually use recursion higher-order functions.

Try to use higher-order functions instead of recursion

  • Harder to reason about
  • Overly general
  • Easy to accidentally overflow the stack
  • Easy to make too large
  • Easier to make mistakes the type checker can't catch
  • Often reinventing the wheel
When to use recursion?
  • When you've tried it both ways and found it cleaner
  • When the stop condition is complex
  • When you would typically use it in imperative programming
  • When the call stack manages data that you would otherwise have to manage manually
  • Often beneficial to use recursion to create a new higher-order function
def intToRoman(number: Int): String = {
  def stream = Stream.iterate((number, "")){
    case (decimal, roman) => val (decDigit, romDigit) =
        (conversions dropWhile (_._1 > decimal)).head
    (decimal - decDigit, roman + romDigit)
  }

  stream.dropWhile(_._1 > 0).map(_._2).head
}
def sumToN(n: Int): Int = {
    if (n == 0)
        0
    else
        n + sumToN(n-1)
}
@scala.annotation.tailrec
def sumToN(n: Int, acc: Int = 0): Int = {
    if (n == 0)
        acc
    else
        sumToN(n-1, acc+n)
}
def sumToN(n: Int): Int = (0 to n).sum

def sumToN(n: Int): Int = 0 to n reduce (_ + _)

Don’t use loop indices unless they are referenced directly by the problem statement

// http://stackoverflow.com/q/42306911/389146
def pair(a: Array[Int], target: Int): Option[(Int, Int)] = {

  var l = 0
  var r = a.length - 1
  var result: Option[(Int, Int)] = None
  while (l < r && result.isEmpty) {
    (a(l), a(r)) match {
      case (x, y) if x + y == target => result = Some(x, y)
      case (x, y) if x + y < target => l = l + 1
      case (x, y) if x + y > target => r = r - 1
    }
  }
  result
}
def findSum(a: Vector[Int],
            target: Int): Option[(Int, Int)] = {
  def stream = Stream.iterate(a){xs =>
    if (xs.head + xs.last > target)
        xs.init
    else
        xs.tail
  }

  stream.take (a.size - 1)
        .map {xs => (xs.head, xs.last)}
        .find {case (x,y) => x + y == target}
}

Look for opportunities to factor out loop structures

// http://stackoverflow.com/a/35051921/389146
def getOpt(p: (Int) => Boolean): Option[Tree[Int]] = {
  def _getOpt(tree: Tree[Int],
              p: (Int) => Boolean): Option[Tree[Int]] = {
    tree.children.map {t =>
        if(p(t.node))
            Some(t)
        else
            t.children.map(_getOpt(_, p))
    }
  }
}
def depthFirstTraverse[A](tree: Tree[A]): Stream[Tree[A]] =
  tree #:: (tree.children map depthFirstTraverse)
  .fold(Stream.Empty)(_ ++ _)

def getOpt(p: (Int) => Boolean): Option[Tree[Int]] =
  depthFirstTraverse(tree) find {x => p(x.node)}

Opportunities from immutability

Keep relationships between objects outside of the objects themselves

case class Room(description: String,
                monsters: List[Monster],
                loot: List[Loot],
                north: Option[Room],
                south: Option[Room],
                east:  Option[Room],
                west:  Option[Room])
case class Room(description: String,
                monsters: List[Monster],
                loot: List[Loot],
                doors: List[Direction])

val rooms = Map((0,0) -> Room("scary room",
                              List(scaryMonster),
                              List(coolLoot),
                              List(North)),
                (0,1) -> Room("fun room",
                              List(clown),
                              List(partyFavor),
                              List(South,East)))

Use small, flexible data structures and transform on demand

case class Board(forward: Map[String, Node],
                 reverse: Map[Node, String],
                 occupiedSquares: List[String],
                 nodes: List[Node])
val board: Map[String, Node] = ???
val occupiedSquares = board.keySet
...
val occupiedInRow =
    occupiedSquares filter {_ startsWith myRow}
val occupiedInCol =
    occupiedSquares filter {_ endsWith myCol}
  • General Tips

  • Principles you already know from imperative programming

  • Principles specific to functional programming

    • General
    • Iteration
    • Immutability

Questions?