Foundations of Computer Science/Higher Order Functions

Higher Order Functions

higher order functions offer a more powerful ways to generalize solutions to problems by allowing blocks to take blocks as parameters and returning a block as a return value. All other functions are called first order functions. An example higher order function in math is the derivative function which takes a function as the input and produces another function (the derivative of the first function) as the output. In computer science, a map function takes an arbitrary function and a data set (e.g. a list) and applies the function to each and every data item in the set. Another example is the reduce (or fold) function, which takes a input function and data set and produces the aggregation of all items in the data set using the function. For instance, if the input function is the addition the reduce function returns the sum of all items in the data set as the output. If the input function is multiplication, the reduce function produces the product of all items in the data set. Higher order function also allows us to create compositions of functions using existing functions on the fly. For example, given two functions $y=f(x)$ and $y=g(x)$ and $b=f(a)$ and $c=g(b)$ we can create a function $y=fg(x)=f(g(x))$ so that $c=fg(a)$.

Examples

map

The following script uses the built in map block/function to apply the same block/function to each and every element in a list.

To apply a different function we simply need to find or implement the function and use it as the first parameter to the map block. The next example uses the multiplication function that takes two parameters. Snap! is smart enough to detect that and use each element of the list as both parameters when the function is applied. So the result list should contain the elements from the original list multiplied to themselves.

This map block generalized this pattern of applying the same function to multiple data items into a block. It doesn't simply programming because someone has to write this map block (check the source code to see how complicated it is), but it makes programmers happier because it keeps the thinking part simpler. As programmers we are freed from worrying about the iteration of lists so that we can focus on the function that needs to be applied to the list.

reduce

The following two examples use the built-in reduce function in Snap! to calculate the sum and the product of a list of numbers.

Note that the reduce (combine with) function can take any function with two input parameters to aggregate a list of values to a single value. By using higher order functions we can create generalized solutions that can be customized to solve a larger set of problems.

return blocks as data

The following block demonstrates the use of blocks as data. In this block two reporter blocks are taken in as parameters, which are then used to form the report value - a new block. The new block applies the two input report blocks to some unknown input value. Note that the "ring" (gray frame) around the report value is very important. Whatever enclosed in the "ring" will be treated as data not programs. The application of the two functions will not be evaluated but will simply be returned as data without evaluation, which is what we wanted in this higher order function.

To use the composed function we can call the compose function with the two input functions and use the "call" block to execute the composed block against an input value as shown in the following script.

With this "compose" block we define new functions by combining existing functions on the fly - when we need them. This is a powerful way of generalization we cannot achieve without using higher order functions.