# 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.

!The built in map block (function) is used to apply a block (function)
to each and every element in a
list. 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. 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

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

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. 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. 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.

