Lambda Calculus, Currying and higher order function

As we saw in lambda calculus functions can only accept one parameter, the process or techniques we use to convert a function with multiple arguments into the use of sequences of functions each with a single argument is called currying.

Suppose we have f(x,y)=x+y+xy from NxN to N as below, remember we assumed from the last post that we are not going to use prefix notation to have more simple expressions anymore:

λxy.x+y+xy

if we want to evaluate f(4,9) we can first evaluate f for x=2, which returns a function like h(y)=4+y+4y or h(y)=4+5y:

λxy.x+y+xy → λx.λy.x+y+xy → λx.(λy.x+y+xy) 4 → λy.4+y+4y → λy.4+5y

Now we have a function h which we can evaluate it for y=9, so h(9)=4+5*9=49 or in lambda calculus:

(λy.4+5y) 9 → 4+5*9 → 49

In this example we say that f(4,y) or h(y) is called curried of f for x=4 so instead of mapping NxN to N we man N to N to N, this will also be like λy.4+5y in its equivalent lambda form.

Note that a curried function is nothing like a function in programming languages that returns a function, the idea is something like the following pseudo code

int sampleF(int x, int y) {

  return x+y+xy

}

int curriedF(int x) {

  return sampleF(4,y) // suppose the language can returns a function

}

At the end of this post just let me note that there reverse operation which transfers subsequent calling of single argument functions to a function with multiple arguments is called un-currying. The currying and un-currying transformations sometimes are called functionalization and defunctionalization.

Higher order functions
A function that takes one or more functions as arguments and/or returns a function is called a higher order function and all other functions can't do any of these are called first order functions.

The forEach method of Java 8 for a List<Element> is a higher order function which we can use it like this:

List<Person> myList = new ArrayList<>();
myList.forEach((Person person) -> {
    System.out.print("Name:");
    System.out.println(person.getName());
    System.out.print("Family:");
    System.out.println(person.getFamily());
});

As you see the forEach accepts an anonymous function (in lambda syntax) as the parameter which can do anything (like printing name and family) on its passed person. You see the similarity between this piece of code and what we usually write in JQuery, this is the typical code writing in functional programming which we will talk about pretty soon.