All Articles

# List Processing with Higher-Order Functions

In imperative programming, loops are often used to process a list of items. A for-loop, in most cases, will take the following form.

``````for(var i = 0; i < 10; i++) {
console.log(i);
}
``````

In this example, every iteration has a state change. In particular, the value of `i` is mutated in order to keep track of where the loop is located. However, in functional programming, the convention is to have no mutation. As such, list processing is attained via recursion.

``````countDown :: Integer -> IO ()
countDown i
| i == 0 = print 0
| otherwise = print i >> countDown (i - 1)
``````

In this recursive program, the value of `i` is printed on every call to the function. On every call, a new value of `i` is passed into the next. Without a for-loop, the program was able to accomplish the same goal. However, some recursive strategies will have more lines of code than their for-loop counter-parts.

``````numEvens :: [Integer] -> Integer
numEvens lst = numEvensRec lst 0

numEvensRec :: [Integer] -> Integer -> Integer
numEvensRec [] acc = acc
numEvensRec (x:xs) acc =
if even x
then numEvensRec xs (acc + 1)
else numEvensRec xs acc
``````

In this example, recursion is used to count all the even numbers in a list by keeping track of their count in an accumulator. Since the signature `numEvens` only supports one argument, a helper function `numEvensRec` with an additional parameter is required to keep track of the count of even numbers.

With that said, list processing is repeated often enough that functional programming languages have built-in functions that do the same. They are called Higher-Order Functions, their name is derived from the fact that they take functions as arguments to accomplish what is needed.

#### Filter

The first higher-order function is `filter`. Its signature requires a predicate (a boolean function) and a list of types compatible with the predicate.

Since the example counts the amount of even numbers, the predicate in context is `even`, and the list is the list of numbers. The output of `filter` is a new list that contains all the values which yield true when applied to the predicate. The previous program can be rewritten using `filter`.

``````numEvens2 :: [Integer] -> Integer
numEvens2 lst =
toInteger (length (filter even lst))
``````

This program is significantly shorter than the original.

#### Map

Similarly, a program that manipulates all elements in a list can be written using `map`. Its signature requires a procedure and a list.

Suppose a program wants to make all even numbers into odd numbers, this can be accomplished using `map`.

``````makeOdd :: [Integer] -> [Integer]
makeOdd lst =
map (\x ->
if even x
then x + 1
else x)
lst
``````

The higher-order function `map` iterates through every item in the list, and checks whether a value is even. The procedure, denoted with `->`, performs the check and adds a value of one if the current number is even; thereby making the number odd. Once `map` is finished, a list with only odd values is returned.

#### Fold

Finally, a program that wants to perform a computation which carries over a previous result from an earlier part of the list, should use `fold`. Its signature requires a procedure, which applies to all values of the list, an initial value, and the list to be processed. Intuitively, `fold` aggregates the values in a list using a procedure, and returns a result.

A program that wants to add all even numbers in a list can use `fold` to accumulate addition throughout the list.

``````addAllEven :: [Integer] -> Integer
The higher-order functions `filter`, `map`, and `fold` abstract commonly used patterns for processing lists.