Higher-order Functions

Earlier you learned through the lens of Ruby that higher-order functions receive other functions as parameters. Many common iteration patterns have been abstracted out into higher-order functions, including map, filter, and fold. Haskell provides these abstractions too.

Map

Suppose we want to lowercase a string in Haskell. The Data.Char module provides a toLower function for Char that will help, but first we need to visit each individual Char in the string. Since strings in Haskell are lists of Char, we can recurse through and lowercase each character as it lands in the head position. This definition of lowerAll adopts this explicitly recursive strategy and breaks the recursion into two subdefinitions with pattern matching:

import Data.Char

lowerAll :: String -> String
lowerAll "" = ""
lowerAll (first : rest) = toLower first : lowerAll rest

Or suppose we want to flip the sign of all numbers in a list. We could write this recursive function:

negateAll :: [Int] -> [Int]
negateAll [] = []
negateAll (first : rest) = negate first : negateAll rest

The two algorithms lowerAll and negateAll look very similar. They both follow the map pattern, transforming one collection into another by applying some transformation function to each element. Instead of writing this same pattern over and over again, the recursive process can be factored out into a higher-order map function.

The map abstraction may be implemented in Haskell as a function that accepts two parameters: the transformation function and a list. The list may be of any type a. It produces a list of a possibly different type b. The transformation function must therefore turn an a into a b. Thus the map function has this type signature:

map :: (a -> b) -> [a] -> [b]

The map function is defined succinctly using patterns. The base case for the empty list ignores the transformation function and yields the empty list:

map _ [] = []

The general case transforms the first element and conses it on the mapped tail:

map transform (first : rest) =
  transform first : map transform rest

The lowerAll and negateAll functions may be implemented much more succinctly as mere wrappers that pass along the appropriate transformation function and the list to map:

lowerAll text = map toLower text
negateAll xs = map negate xs

Haskell provides a builtin definition of map. We should use it rather than defining our own.

Filter

Suppose we want to extract just the capital letters from a String, and we write this recursive caps function:

caps :: String -> String
caps "" = ""
caps (first : rest) =
  if isUpper first then
    first : caps rest
  else
    caps rest

Or maybe we want the odd numbers from a list, so we write this recursive odds function:

odds :: [Int] -> [Int]
odds [] = []
odds (first : rest) =
  if odd first then
    first : odds rest
  else
    odds rest

These two algorithms look very similar. They both follow the filter pattern, extracting from a collection a subcollection containing only those members that meet some criteria. An abstraction of these algorithms may be implemented in Haskell with a higher-order filter function that accepts two parameters: a predicate function and a list. The list may be of any type a.

This definition of filter uses pattern matching in the formal parameters to break up the base and general cases:

filter _ [] = []
filter predicate (first : rest) =
  if predicate first then
    first : filter predicate rest
  else
    filter predicate rest

The base case doesn't need the predicate function, so it discards it with the _ wildcard. The general case does need the predicate, and it also destructures the list so the head can be examined singly.

The caps and odds functions may be written as mere wrappers that call filter:

caps text = filter isUpper text
odds xs = filter odd xs

Haskell provides its own definition of filter. We should use it rather than our own.

Fold

Suppose we want to sum up a list, and we write this recursive sum function:

sum' :: [Int] -> Int
sum' [] = 0
sum' (first : rest) = first + sum' rest

Or suppose we want the product of all elements of a list, and we write this recursive product' function:

product' :: [Int] -> Int
product' [] = 1
product' (first : rest) = first * product' rest

These two algorithms look very similar. Both implement the fold pattern, which is more abstract than the other two patterns. Folding is used to transform a collection to something else, one element at a time—and that's really the most we can say about it. The transformation is achieved by mixing in each element into some accumulating structure.

The fold function accepts three parameters, which are easiest to describe in reverse order:

• The third parameter is a list of any type a.
• The second parameter is an initial accumulator of any type b.
• The first parameter is a mixing function that accepts as parameters the current element of the list and the current accumulator. It produces the new accumulator.

The final accumulated value is returned by fold. The type signature reflects the function's abstractness:

fold :: (a -> b -> b) -> b -> [a] -> b

We have two ordering options for implementing this function:

1. Recurse on the tail first and then mix the head element into the returned accumulator. This is called a right fold because the right end of the list is mixed in to the accumulator first when the recursion reaches the base case.
2. Mix the first element into the current accumulator and then pass the resulting accumulator on to the recursion on the tail. This is called a left fold because the left end of the list is mixed in first.

Each fold has its advantages. If the mixing function is a left-associative operation, then a left fold is appropriate. If the mixing function is a right-associative operation, then a right fold is appropriate. Sometimes the associativity doesn't matter, as with addition and multiplication. In Haskell, left folds are generally more expensive because of Haskell's lazy evaluation mechanics. Right folds, on the other hand, are more likely to overflow the stack with recursive function calls.

The right-fold function foldr may be implemented using patterns. It recurses before mixing:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ _ [] = []
foldr mix accumulator (first : rest) =
  mix first (foldr mix accumulator rest)

The left-fold function foldl has the same interface. It mixes before recursing:

foldl :: (a -> b -> b) -> b -> [a] -> b
foldl _ _ [] = []
foldl mix accumulator (first : rest) =
  foldl mix (mix first accumulator) rest

The sum' and product' functions may be written as mere wrappers that call foldl:

sum' xs = foldl (+) 0 xs
product' xs = foldl (*) 1 xs

For the mixing functions, we pass the operators directly. They must be enclosed in parentheses so that they don't attach to any operands at the level of the call.

Haskell provides builtin definitions of foldr and foldl. We should use them rather than our own.