Higher-order functions

Higher-order functions are functions that take other function(s) as their argument(s). This mechanism allows functional languages to be more expressive and powerful. Higher-order functions enable encapsulating common programming patterns as functions. Here are few examples:

Map

Pattern: Create a new list by applying a function to all elements of an old list.

-- definition
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

-- square of numbers
Prelude> map (^2) [1..10]
[1,4,9,16,25,36,49,64,81,100]

-- length of words in a string list
Prelude> map length ["hello", "bye"]
[5,3]

Note that it is defined as “map takes a function (a -> b) and a list of type a as arguments and produces a list of type b as result”.

It is worth noting that map is polymorphic. Furthermore, it can be applied to itself to process nested lists:

Prelude> map (map signum) [[-100, 5, 0], [-9, -9, 0]]
[[-1,1,0],[-1,-1,0]]

Filter

Pattern: Create a new list by selecting elements of another list that meets a certain predicate.

-- definition
filter :: (a -> Bool) -> [a] -> [a]
filter f [] = []
filter f (x:xs) | f x = x : filter f xs
       	 	    | otherwise = filter f xs

-- odd numbers only
Prelude> filter odd [1..10]
[1,3,5,7,9]

-- vowels only
Prelude> filter (\x -> elem x "aeiou") ['a'..'z']
"aeiou"

Foldr

Pattern: process elements of the list using a right-asociative operator, i.e., for some operator $@$ and list $[a,b,c]$, we have $$ a @ (b @ c) $$ This is a recursive pattern with the following general structure:

f [] = v
f (x:xs) = x @ f xs

which can be encapsulated using foldr as:
foldr (@) v

So for an empty list, a value v is returned while for non-empty list, head is combined (using operator) with the result of recursively calling the function on tail. For example, instead of writing the sum function as follows:

sum :: Num a => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs

We could use foldr:

sum :: Num a => [a] -> a
sum = foldr (+) 0

A key observation can be made looking at the pattern that foldr is encapsulating: f (x:xs) = x @ f xs. The operator @ has two arguments - first is the head of the list and second is result of recursively applying f to the tail of the list. With this insight, we can write more functions beyond simple math operators. For example, recursive definition of reversing a list is:

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

Since expression for non-empty list contains 1. head of the list, x and 2. recursively applying reverse to the tail of the list, it meets the foldr pattern. So we can define our operator as (with head as the first argument and tail as the second argument):

\x xs -> xs ++ [x]

And then write our reverse using foldr as:

reverse :: [a] -> [a]
reverse = foldr (\x xs -> xs ++ [x]) []

Prelude> reverse "hello"
"olleh"
Prelude> reverse [1..5]
[5,4,3,2,1]

Foldl

Pattern: process elements of the list using a left-associative operator, i.e. for some operator $@$ and list $[a,b,c]$, we have $$ (a @ b) @ c $$ This is a recursive pattern with the following general structure:

f v [] = v
f v (x:xs) = f (v @ x) xs

which can be encapsulated using foldl as:
foldl (@) v

Here, v is the accumulator value which is returned for an empty list. For non-empty list, head is combined with accumulator using the operator and the function recursively called on this new accumulator and tail. Similar to foldr, addition can now be defined as:

add :: Num a => [a] -> a
add = foldl (+) 0

Although it looks similar to foldr, it is worth noting that while it is the last element that is processed first in foldr, in foldl head of the list is first element to be processed. When working with foldl pattern, it may be useful to think about how the operator @, processes the head x and the initial value of the accumulator v. For example, for reversing a list, head will be consed to empty list in first step. Therefore, our function becomes \xs x -> x:xs and we can write reverse like:

reverse' = foldl (\xs x -> x:xs) []

Prelude> reverse' "hello"
"olleh"
Prelude> reverse' [1..5]
[5,4,3,2,1]

Note that first argument now is the tail and second is the head.

(.)

Pattern: Composition, as in math: $f.g$

Composition allows to write nested functions more clearly without worrying about initial argument. For example, removing empty list from list of lists can be written as:

rmempty :: [[a]] -> [[a]]
rmempty = filter (not . null)

Prelude> rmempty [[1], [],[2]]
[[1],[2]]

Curry and uncurry

Pattern: Convert a function on pair to curried function and vice-versa

curry' :: ((a, b) -> c) -> a -> b -> c 
curry' f x y = f (x,y)

uncurry' :: (a -> b -> c) -> (a,b) -> c
uncurry' f (x,y) = f x y

More examples

check if all elements satisfy a predicate

Prelude> all Data.Char.isLower "hello"
True

check if any element satisfy a predicate

Prelude> any Data.Char.isUpper "hello"
False

take elements from a list while they satisfy a predicate

Prelude> takeWhile (/= ' ') "hello world"
"hello"

drop elements from a list while they satisfy a predicate

Prelude> dropWhile (\x -> sqrt x < 5) [1..30]
[25.0,26.0,27.0,28.0,29.0,30.0]