In the previous posts, we took a look at how functions are the core pieces in functional programming languages. We talked about pure functions, referential transparency, side effects and recursion in the previous posts. In this post, we are going to explore some properties of functions and how we can use them in a functional programming language.
A function is a black box that given an input always gives you back the same output. As we stated before, a function does not have any side effects; if it has any, it could be a procedure but not a function. Function is a term that comes from Mathematics and there is no concept of side effect in there. A function accepts a set of input values; we call that the domain of a function. The output of a function is called codomain and the set of outputs is called the image of the function. We can decompose them like this:
f: A -> B</code></pre>
Where A is the domain and B is the codomain. For example, for the function f(x) = 2x we can decompose it as it follows:
Where as we stated, A is the domain, B is the codomain and [2, 4, 6] is the image of the function.
Arity is the number of arguments that a function takes. We say that the arity of f(x: Int) is 1, or that is a unary function, or that is a function with one argument. Therefore, the arity of a function can be expressed with a number or the spring term. Unary, binary, ternary, etc... Are words that come from Latin, but mathematicians usually use Greek instead of Latin so usually they interchange those words for the same ones coming from Greek. We can say as well that the arity of a function is monadic, dyadic or triadic.
Function composition is one of the bases of functional programming. The idea is that if you have a function f = A->B and a function g = B->C you can create a 3rd function h = A->C which internally uses f and g to create that C, that is: h = g(f(x)). If we express it in mathematical terms we can say that h = f∘g readed as "h is equal to f after g" or what is the same: h = Cgf An example of function composition is:
We declared two functions intToString and stringToDouble, when we compose them we create a 3rd function which accepts an int and returns an double. So if we call it: composedFunction("32") it returns 32.0 which is the result after converting that String to int, and from that int to a Double. Notice that when composing functions, the functions are applied from right to left, this time: intToString and then stringToDouble. We can do the same without modifying the order of the functions with the function andThen, this will be like this:
val composedFunction2 = intToString _ andThen stringToDouble
This is the same and in my opinion less confusing. This last expression could be stated without infix operators as it follows:
val composedFunction2 = (intToString(_)).andThen(stringToDouble)
The idea behind higher-order functions is that functions are values, hence functions can be passed around as we do with Integers, Strings, etc... Functions that accept other functions as arguments or return functions are called higher-order functions. An example of a really common higher order function is map, its definition in Scala’s List class is:
def map[B](f: A => B): List[B]
The meaning of map is to apply a transformation to every element of the List and returning a new List with all the new transformed elements. If a language supports higher order functions, we say that the functions in that language are treated as first class citizens, that is, functions are first class functions. So when we refer to a programming language, we say that the language supports first class citizens but if we refer to a function, we say that the function is a first class function. One of the convenient usages of higher-order functions is to create inline functions, which we call anonymous functions or function literals. One example using the previously defined map, could be this:
List(1).map(i => i + 1)
As you can see, the function i => i + 1 is passed in as an argument of the map function.
Partial application means that for a function that accepts a number of arguments, N, we can fix or bind some of its arguments that it takes to reduce the arity of the function. Consider these two functions:
defsum(a: Int, b: Int) = a + b
defsumOfOneWith(a: Int) = sum(1, a)
Notice that sumOfOne partially applies the function sum reducing its arity to 1. This is super useful and if you take a look on the internet you will see some people using this technique as a replacement for dependency injection.
Currying is a technique that allows us to decompose a function with arity N (where N is > 1) in a chain of calls to smaller functions with arity 1. Let's see an example:
def sumCurried = (a: Int) => (b: Int) => a + b
sumCurried(1)(1) == 2
Now sumCurried returns a function which returns another function and that last one calculates the result. Doing that we reduced the arity of sum to 1 expressing it as a smaller function. Scala can automatically curry a function using the curried function, an example of the previous version of sum:
sum _ curried
This is a sample curry implementation:
def curry[A, B, C](f: (A, B) => C): A => (B => C) = a => b => f(a, b)
What it does, is to receive a function with arity 2 and return a function with arity 1 that returns another function with arity 1, and finally that function calls the given function with the required parameters. Take some time to digest this, and if you have the chance, play around a little until you understand the concept. It is a powerful technique but it takes some time to fully understand it. We can, as well, uncurry a function. It is the same concept but all the way around, so we take a function with less arity and we convert it to another with a higher arity. The dual of the previous function is:
def uncurry[A, B, C](f: A => (B => C)): (A, B) => C = (a, b) => f(a)(b)
This time it takes a function with arity 1 and it returns a function with arity 2 that finally applies those arguments to the original one.
Currying VS partial application
So, what is the difference between curry and partial application? As we stated before:
Currying: Ability to decompose a function with arity N (where N is > 1) in a chain of calls to smaller functions with arity 1
Partial application: Possibility to apply a function with a given set of arguments to reduce the original function arity. A requirement to do partial application is that the function is already curried so that we can apply arguments one by one
This is an example of how to apply currying to a binary function:
@ defaFunction(a: Int, b: String) : String = a.toString + b
defined function aFunction
@ val curriedFunction = curry(aFunction)
curriedFunction: Int => String => String = ammonite.$sess.cmd1$$$Lambda$2127/1053392896@788bebee
This is an example of how to partially apply a curried function: