Functional Programming Cheat Sheet

Posted on August 10, 2017

What follows is translation from traditional programming constructs to how we might express the same, or similar, program using a Functional Programming approach. It is a loose translation, in no particular programming language syntax, then demonstrated in FP using the Haskell programming language.

In some of the examples, there will be reference to a function. This can be directly translated to what is used in languages such as Java and C# as an interface. For example, this Java interface…

interface Integer2String {
  String apply(Integer i);
}

…used at a call site with the value n…

i2s.apply(n);

…can be thought of as a function called i2s applied to a value n, using Haskell syntax:

i2s n

liftA2 on []

Given a function func, and two lists list1 and list2, loops first through list1, then list2 and apply a function to the element at that position.

given(func, list1, list2) {
  var r = List.empty
  for(var i = 0; i < list1.length; i++) {
    for(var j = 0; j < list2.length; j++) {
      r += list1[i].func(list2[j])
    }
  }
  return r
}

This can be written using liftA2 which works for many values, including lists. The first argument to liftA2 is the function to apply to the list elements. The subsequent arguments are the two lists.

liftA2 func list1 list2

The liftA2 function applies to “one loop within one more loop”. You can correlate the number 2 with the number of loops. There are other liftA* functions for embedding more inner loops.

This general pattern is called Applicative Functor and is described in the paper, Applicative Programming With Effects.

Option/Maybe monad

The Maybe data type, sometimes called the Option data type, can be thought of as a list with a maximum length of one. It is a type-safe substitution for what is often represented as null in other programming languages.

Given two possibly null values, x and y, then if either value is null, return null, otherwise apply a function (such as +) to the two values, knowing that they are not null:

given(x, y) {
  if (x == null) {
    return null
  } else if(y == null) {
    return null
  } else {
    return x + y
  }
}

This can be written using the >>= function, which is overloaded to work on many values, of which Maybe is one instance:

x >>= \p ->
y >>= \q ->
pure (p + q)

This particular code can also be written using liftA2:

liftA2 (+) x y

However, when the second null check depends on the value of the first one, then using the >>= function is required.

For example, given one value x, and a function test, which takes x as argument, for the second null check:

given(x, test) {
  if (x == null) {
    return null
  } else {
    val y = test(x)
    if(y == null) {
      return null
    } else {
      return x + y
    }
  }
}

This can be written using >>= but not liftA2.

x >>= \a ->
test x >>= \b ->
pure (a + b)

liftA2 on reader

Given two functions p and q, apply them to the same value x, then apply those two results to another function such as +.

given(x) {
  return p(x) + q(x)
}

Since liftA2 is overloaded to work on different structures as long as they all satisfy a similar pattern. We have already seen that lists and Maybe satisfy this pattern. However, functions that accept a single argument also satisfy this pattern. A function that accepts a single argument can also be used to simulate a function that accepts two arguments, by first accepting that one argument, and returning a function that then accepts one argument and takes it to a value. Since in this case we are describing (the simulation of) a two-argument function (called +), then we specifically want the 2 in liftA2. In common nomenclature, this specific instance is often called the reader instance.

liftA2 (+) p q

sequence on Maybe with list

Given a list of possibly null values, return either a list of definitely-not null values, or null itself.

// >>> given([notnull 1,null,notnull 3])
// null
// >>> given([notnull 1,notnull 2,notnull 3])
// notnull [1,2,3]
given(list) {
  var r = List.empty
  for(var i = 0; i < list.length; i++) {
    if(list[i] == null) 
      return null
    else 
      r.add(list[i])
  }
  return r
}

This can be written using the sequence function, which is overloaded on many values, including Maybe. Since Maybe values have either 0 values or 1 value inside, it can be used as a type-safe null value. Therefore the sequence function will accept a list of Maybe values, and return a Maybe list of values.

sequence list

sequence [Just 1,Nothing,Just 3] == Nothing
sequence [Just 1,Just 2,Just 3] == Just [1,2,3]

sequence on reader with list

Given a list of functions (or instances of an interface), and a value (x), collect the results of having applied each function to that value.

// >>> given([(+1),(*2),(/3)], 99)
// [100,198,33]
given(list, x) {
  var r = List.empty
  for(var i = 0; i < list.length; i++) {
    r.add(list[i].apply(x))
  }
  return r
}

Since the sequence function is overloaded, as we have also seen it work on Maybe values and, it can also work on values that are functions accepting one argument, since that meets the same pattern as Maybe as far as sequence is concerned.

sequence list x

sequence [(+1),(*2),(/3)] 99 == [100,198,33]

sequence on list with list

Given a list of lists, produce a list of lists, where each element of each input list appears (in order), with each element of the other lists. This is also known as the cartesian product.

// >>> given([[1,2],[3,4,5],[6,7]])
// [[1,3,6],[1,3,7],[1,4,6],[1,4,7],[1,5,6],[1,5,7],[2,3,6],[2,3,7],[2,4,6],[2,4,7],[2,5,6],[2,5,7]]
given(list) {
  var r = List.empty;
  for(var i = 0; i < list.length; i++) {
    var s = List.empty
    for(var j = 0; j < list[i].length; j++) {
      s.add(list[i][j])
    }
    r.append(s)
  }
  return r
}

The sequence function is also overloaded on [] values, not just Maybe and functions that accept an argument. Actually, it’s overloaded on many other things. These things are called applicative functors and sequence works on all of them.

sequence list

sequence [[1,2], [3,4]] == [[1,3],[1,4],[2,3],[2,4]]

join on reader

Given a function that accepts two (or more) arguments such as +, apply that function to the same argument.

given(x) {
  return x + x
}

The join function is overloaded to work on many values, including functions that take one argument. With one call to join, that argument will be passed to a function, then when another function is returned, that same value is passed in again, to return a value. To continue passing this argument, the join function can be composed with itself as many times as necessary.

join (+) x

kleisli composition on Maybe

Given a value (x), one function that might return null (func1), another function that might return null (func2), and a third function that might return null (func3), pass x to func3 and only if it does not return null, pass that return result into func2 and if that is not null, pass it to func1. If any of the functions return null then return null.

given(x) {
  func1result = func1(x)
  if(func1result == null) {
    return null
  } else {
    func2result = func2(func1result)
    if(func2result == null) {
      return null
    } else {
      func3(func2result)
    }
  }
}

The kleisli composition operator, called <=< is overloaded to work on many values, of which Maybe is one instance.

(func3 <=< func2 <=< func1) x

kleisli composition on reader

Given a value (x), a function (func1) that requires access to a variable (s) to compute its result, another function (func2) that also requires access to s, pass x to func2 and the return result of that to func1.

global const var s // accessible by func1 and func2

given(x, func1, func2) {
  return func1(func2(x))
}

We can use the reader with kleisli composition.

(func1 <=< func2) x s

kleisli composition on State

The State data structure is structurally equal to a function that passes a value in, potentially modifies it to a new value, and returns another, orthogonal value in association with that state changing. It can be used to to simulate updating variables, while maintaining the principles of Functional Programming.

Given a value (x), a function (func1) that requires access to, and may modify, a variable (s) to compute its result, another function (func2) that also requires access/modify to s, pass x to func2 and the return result of that to func1.

global var s // accessible/writable by func1 and func2

given(x, func1, func2) {
  return func1(func2(x))
}

We can use the State data structure to simulate the variable s.

evalState ((func1 <=< func2) x) s

sequence on reader with Maybe

Given a function (or instance of an interface), called func, which may be null, and a value (x), apply the function to the value. If the function is null, return null.

given(func, x) {
  if(func == null) {
    return null
  } else {
    return func.apply(x)
  }
}

The possibility for null can be simulated using the Maybe data type. Since Maybe can be treated as a list with a maximum length of one, we can also sequence this, and we can do it with many values that meet a certain pattern. A function that accepts one argument meets this pattern, so we can use sequence for this case.

sequence func x

choice on Maybe

Given two values (x and y), then if x is not null, return it, otherwise try y.

given(x, y) {
  if(x == null) {
    return y
  } else {
    return x
  }
}

In some programming languages, this expression might be written using a ternary operator:

given(x, y) {
  return x == null ? y : x
}

The C# programming language has a built-in operator (??) for this, called the elvis operator.

given(x, y) {
  return x ?? y
}

The choice operator in Haskell is called <|> and is overloaded to work on many different values, of which Maybe is one instance.

x <|> y

Do effect on condition

Given some boolean condition, if it is true, do something. If it is false, do nothing.

given(condition) {
  if(condition)
    doSomething()
}

Since Haskell values are always pure, including effects, they can be treated as values. That is, they can be passed to functions as arguments.

when condition doSomething

Do effect on not-condition

Given some boolean condition, if it is false, do something. If it is true, do nothing.

given(condition) {
  if(!condition)
    doSomething()
}

The when and unless functions can handled performing some effect based on a condition. Since the condition is negated, we want the unless function.

unless condition doSomething

Can you come up with any more patterns that translate in a helpful way? Let us know if you do.

> Tony Morris

Tony Morris is a programmer at the Queensland Functional Programming Lab.