Introduction to Programming Languages/Noticeable High-Order Functions

Noticeable High-Order Functions

Some high-order functions are very common programming idioms. Three of the most famous examples are map, reduce and filter. The first example in this chapter is an implementation of the map function. It takes two arguments, a data-structure t and a mapping function f, and returns a new data-structure in which every element has been transformed by f. Usually map works on lists. Map does not add nor remove elements from the input list; thus, the input and output lists will have always the same size.

Reduce is used to transform a data-structure into a single value, given continuous applications of a binary operator. In SML reduce comes in two flavours: foldr and foldl. The first function, foldr, takes a binary function of type 'a * 'b -> 'b, a seed of type 'b, plus a list of type 'a list, and returns an element of type 'b that is called the reduction. The function foldr starts applying the binary operator from the right-side of the list towards its left side. Some examples are given below:

- foldr (op +) 0 [1,2,3,4];
val it = 10 : int

- foldr (op * ) 1 [1,2,3,4];
val it = 24 : int

- foldr (op ^) "" ["abc","def","ghi"];
val it = "abcdefghi" : string

- foldr (op ::) [5] [1,2,3,4];
val it = [1,2,3,4,5] : int list

- foldr (fn(a, b) => (a + b)/2.0) 0.0 [1.0, 2.0, 3.0, 4.0];
val it = 1.625 : real

The sequence of applications that are produced by a call to foldr. Notice that the list elements are combined in a right-to-left fashion.

The function foldl is very similar to foldr; however, it starts evaluating the binary operation from the left side of the list towards its right side. A few examples of use are given below:

- foldl (op +) 0 [1,2,3,4];
val it = 10 : int

- foldl (op * ) 1 [1,2,3,4];
val it = 24 : int

- foldl (op ^) "" ["abc", "def", "ghi"];
val it = "ghidefabc" : string

- foldl (op ::) [5] [1,2,3,4];
val it = [4,3,2,1,5] : int list

- foldl (fn(a, b) => (a + b)/2.0) 0.0 [1.0, 2.0, 3.0, 4.0];
val it = 3.0625 : real

The sequence of applications that are produced by a call to foldl. Contrary to foldr, in this case the list elements are combined from left to right. In this particular example foldr would produce a different result, given that string concatenation is not a commutative operation.

Sometimes foldl and foldr produce the same results when given the same operands. This outcome depends on the binary operator that these operations use. If the operator is both associative and commutative, then these functions will produce the same results for the same inputs. Otherwise, their results might be different.

A comparison between foldr and foldl. Each number is the result of applying either foldl or foldr onto the seed 0 and the list [1, 2, 3, 4]. As we can see, the result is the same only when the binary operator is commutative (C) and associative (A).

These three functions, map, foldr and foldl are very useful parallel skeletons. Map, for instance, can be completely parallelized, given a number of processors proportional to the size of the input list, as in the PRAM model. In other words, this function would execute in O(f) asymptotic time in this scenario, where O(f) is the complexity of applying the mapping function. Given a very large number of processors, i.e., proportional to the size of the input list, both foldr and foldl could have their complexity reduced to a logarithmic factor of the size of the input list. This observation has motivated the design of several high-performance frameworks, such as map reduce and radoop.

An example showing a parallel resolution of a call to foldr. The binary operator can be independently applied on pairs of operands whenever this operator is associative and commutative.

Our last high order function is filter. This function has the type ('a -> bool) -> 'a list -> 'a list. This function takes two arguments: a predicate, that is, a function that returns true or false to a given input, and a list. Filter returns a new list that contains only those elements that cause the predicate to be true. Some examples in SML can be seen below:

- List.filter (fn s => hd (explode s) = #"p") ["grape", "pineaple", "pumpkin", "strawberry"];
val it = ["pineaple","pumpkin"] : string list

- List.filter (fn x => x > 2) [1,2,3,4,5];
val it = [3,4,5] : int list