9.7 Higher-Order Functions on Arrays

When introducing arrays as data structures, we have seen that their processing was easily accomplished through the definition of recursive functions. The behavior of these functions was quite similar: the functions began by testing whether the array was empty, and, if not, the first element of the array would be processed, as well as the remaining elements by a recursive invocation.

As we saw in the previous section, when some functions have a similar behavior, it is advantageous to abstract them into a higher-order function. That is precisely what we are going to do now, with the definition of higher-order functions for three common cases of array processing: mapping, filtering and the reduction.

9.7.1 Mapping

The mapping operation transforms an array into another array by applying a function to each element of the first array. For example, given an array of numbers, we might be interested in producing another array containing the squares of these numbers. In this case, we say that we are mapping the square function onto an array to produce the array of squares. The function definition presents the typical pattern of recursion over arrays:

mapping_square(array) =

if array == []

[]

else

[array[1]^2, mapping_square(array[2:end])...]

end

Obviously, defining a function only to map the square is to over-particularize. It would be much more useful to define a higher-order function that maps any function on an array. That can be easily achieved by modifying the previous function:

mapping(f, array) =

if array == []

[]

else

[f(array[1]), mapping(f, array[2:end])...]

end

With this function, it is easy to produce, for example, the square of all numbers from \(10\) to \(20\):

> mapping(square, enumerate(10, 20, 1))
11-element Vector{Int64}:
100
121
144
169
196
225
256
289
324
361
400

The function mapping is already predefined in Julia with the name map. The implementation provided in Julia also allows mapping over multiple arrays simultaneously. For example, if we want to sum the elements of two arrays two by two, we can write:

> map(+,
enumerate(1, 5, 1),
enumerate(2, 6, 1))
5-element Vector{Int64}:
3
5
7
9
11

9.7.2 Filtering

Another useful function is the one that filters an array. The filtering is performed by providing a predicate that is applied to each element of the array. The elements which satisfy the predicate (i.e., for which the predicate is true) are collected in a new array. The definition is the following:

filtering(p, array) =

if array == []

[]

elseif p(array[1])

[array[1], filtering(p, array[2:end])...]

else

filtering(p, array[2:end])

end

Using this function we can, for example, get only the number divisible by \(3\) between \(10\) and \(20\):

> filtering(n -> n%3 == 0, enumerate(10, 20, 1))

3-element Vector{Int64}:

12

15

18

The function filtering is already predefined in Julia with the name filter.

9.7.3 Reduction

A third function that is very useful is the one that performs a reduction in an array. This higher-order function receives an operation, an initial element, and an array. It will reduce the array by applying the operation between all elements of the array. For example, to add all the elements of an array a\(=\)[e1, e2, ... en] we can make reduction(+, 0, a) and obtain e1\(+\)e2\(+\)... \(+\)en\(+\)0. Thus, we have:

> reduction(+, 0, enumerate(1, 100, 1))

5050

The function definition is the following:

reduction(f, v, array) =   if array == []     v   else     f(array[1], reduction(f, v, array[2:end]))   end

To see a more interesting example of the use of this function, let us consider the calculation of the factorial of a number. According to the traditional definition we have:

\[n! = 1\times 2\times 3\times \cdots{} \times n\]

In other words, it is the product of all the numbers between \(1\) and \(n\), i.e.:

factorial(n) = reduction(*, 1, enumerate(1, n, 1))

The initial element used in the previous examples was the neutral element of the selected operation, but it need not be so. An example where that does not happen is when determining the highest value existing in an array of numbers. In this case, the function that we will use to successively combine the values of the array is the max function defined in the section Selection, which returns the greatest of two numbers. If a is the array of numbers [e1, e2, e3, ...], the greatest of those numbers can be obtained by max(e1, max(e2, max(e3, ...))), which corresponds to an array reduction using the max function. All we have to do now is determine the initial element to be used. One hypothesis is to use the negative infinity \(-\infty\), since any number will be greater than it. Another more simple hypothesis is to use any of the elements of the array, particularly the first as it is the one with easiest access. Thus, we can define:

max_array(array) = reduction(max, array[1], array[2:end])

The reduction function is already predefined in Julia with the name reduce, which receives as arguments the operation used to combine the elements of the array, the array and, optionally, the initial element. If omitted, the initial element is assumed to be the neutral element of the operation.

However, the associativity of the reduce function is unclear; to ensure left or right associativity, Julia provides the functions foldl and foldr, respectively.

On the one hand, the expression foldr(f, i, [e1, e2, ..., en]) en))] calculates f(e1, f(e2, ... f(en, i))).

On the other hand, the function foldl performs the combination of elements in a different order: foldl(f, i, [e1, e2, ..., en]) calculates f(... f(f(e1, i), e2), ..., en).

Keep in mind that applying the functions foldl and foldr is equivalent only when the combination function is commutative and associative.

9.7.4 Exercises 46

9.7.4.1 Question 174

Consider a surface represented by a set of three-dimensional coordinates, as presented in the following figure:

Assume that these coordinates are stored in an array of arrays in the following format:

Define the function surface_interpolation that receives an array with the previous format, starts by creating an array of splines in which each spline \(S_i\) passes through the points \(p_{i,0}, p_{i,1},\ldots,p_{i,5}\), as shown in the following image on the left, and ends up using this array of splines \(S_0,S_1,\ldots,S_5\) to make a smooth interpolation of sections, as shown in following image on the right: