Foundations of Computer Science/Higher Order Functions

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Higher Order Functions[edit]

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 and and and we can create a function so that .

Examples[edit]

map[edit]

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

The built in map block (function) is used to apply a 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.

The built in map block (function) is used to apply a block (function) to each and every element in a list. Because the function passed in takes two parameters when the function is applied to a element of the list the same element is used as both parameters.

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[edit]

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

This block applies the addition function to each and every item in the list to calculate the total.

This block uses the built-in reduce function in Snap! to calculate 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[edit]

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.

This block takes two (reporter) blocks as input parameters and reports a new block as the output. The function of the new block is the composition of the two functions represented by the two input blocks - when the new block is called it takes the input to the new block, applies the two functions (specified when the new block is created) to the input, and reports the result.

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.

The compose block is called to form a composed block (function) from the two input blocks. The composed block is then applied to the input value of 3. The result of this block call is 1+2+3=6.

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.