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
addAllEven lst =
    foldl (\acc x ->
            if even x
            then acc + x
            else acc)
        0 lst

Summary

The higher-order functions filter, map, and fold abstract commonly used patterns for processing lists.

Published 5 Dec 2015