A few higher-order functions #

We introduce a few convenient higher-order functions.

In Haskell #

filter #

The function filter retains elements of a list that satisfy a certain condition.

It can be defined as follows:

filter :: (a -> Bool) -> [a] -> [a]
filter f xs  = [x | x <- xs, f x]

Example. Let us first define an auxiliary function even that maps an Int to True iff it is even:

even :: Int -> Bool
even x = x `mod` 2 == 0  -- `mod` is the "modulo" function, used here in infix form

Then

filter even [1,4,5,4,6]

evaluates to [4,4,6].

Equivalently, instead of defining the function even, we could inline it (as an anonymous function) in the expression above, i.e. we could write

filter (\x -> x `mod` 2 == 0) [1,4,5,4,6]

retainIfEqual :: (Int -> Int) -> Int -> [Int] -> [Int]

retainIfEqual (^2) 4 [2,0,-2,-1,2]

[2,-2,2]

retainIfEqual :: (Int -> Int) -> Int -> [Int] -> [Int]
retainIfEqual f y = filter (\x -> f x == y)

Reminder. Because filter is curried, we can call it with its “first argument” only.

The result is a function, which takes as input the list to be filtered.

Example.

filter even

is a function. It retains the even numbers of a list of integers.

In other words,

filter even [1,4,5,4,6]

is syntactic sugar for

(filter even) [1,4,5,4,6]

Hint. A similar observation can be made for the functions map, all and any, introduced below.

map #

The function map applies a function to each element of a list.

It can be defined as follows:

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

Examples.

• map (+1) [1,4,5,4] evaluates to [2,5,6,5],
• map even [1,4,5,4] evaluates to [False,True,False,True], and
• map (\x -> x `mod` 2 == 0) [1,4,5,4] is equivalent.

trimOdds :: [[Int]] -> [[Int]]

trimOdds [[1,2,6,3],[2,4],[3,3,8],[5,3]]

[[2,6],[2,4],[8],[]]

trimOdds :: [[Int]] -> [[Int]]
trimOdds = map (filter even)

all and any #

The functions all and any have type

(a -> Bool) -> [a] -> Bool

The expression all f xs evaluates to True iff f x evaluates to True for every element x of the list xs.

The expression any f xs evaluates to True iff f x evaluates to True for at least one element x of the list xs.

Note. We will see how these two functions can be implemented in the section on linear recursion (fourth exercise).

Examples.

• all even [4,4,2] evaluates to True

• all even [1,4,5,4] evaluates to False

• all even [] evaluates to True

• any even [1,4,5,2] evaluates to True

• any even [1,3] evaluates to False

• any even [] evaluates to False

appearsIn :: (Eq a) => a -> [a] -> Bool

appearsIn :: (Eq a) => a -> [a] -> Bool
appearsIn x = any (x ==)

restrictTo :: (Eq a) => [a] -> [a] -> [a]

restrictTo :: (Eq a) => [a] -> [a] -> [a]
-- reuse the function `appearsIn` defined in the previous exercise
restrictTo xs ys = filter (\x -> appearsIn x ys) xs

takeWhile #

The function takeWhile has the same type has the function filter

takeWhile :: (a -> Bool) -> [a] -> [a]

The list takeWhile f xs is the longest prefix xs' of xs such that all f xs' evaluates to True.

We will see how it can be implemented in the section on linear recursion (last exercise).

Examples.

• takeWhile even [4,2,2,1,5,2,6] evaluates to [4,2,2]
• takewhile even [1,3] evaluates to []
• takewhile even [4,6,2] evaluates to [4,6,2]
• takewhile even [] evaluates to []

foldr and foldl #

foldr #

The function foldr aggregates the elements of a list.

Intuitively, foldr f z xs:

• aggregates the list xs with the aggregation function f, where
• z is the default aggregation value (for the empty list).

Example. foldr (+) 0 [1,2,3] evaluates to 6.
In this example:

• the aggregation function is +, and
• the default value is 0.

Definition. foldr can be defined recursively as:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x : xs) = f x (foldr f z xs)

Terminology. foldr (and its equivalent in other programming languages) is sometimes called a right‑associative fold, because it intuitively aggregates from right to left.

Examples.

• foldr (+) 0 [1,2,3] evaluates to 1 + (2 + (3 + 0)) = 6
• foldr (*) 1 [2,3,4] evaluates to 2 * (3 * (4 * 1)) = 24
• foldr (&&) True [True,False] evaluates to True && (False && True)) = False
• foldr (-) 0 [1,2,3] evaluates to 1 - (2 - (3 - 0)) = 2

or :: [Bool] -> Bool
or = foldr (||) False

myFunction :: (a -> Bool) -> [a] -> Bool
myFunction f = or . (map f)

foldl #

The function foldl is the left-associative fold.

Example. foldl (+) 0 [1,2,3] evaluates to ((0 + 1) + 2) + 3 = 6

Definition. foldr is defined as follows:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z []     = z
foldl f z (x : xs) = foldl f (f z x) xs

Note. Observe that foldl is tail recursive, whereas foldr is not.

Warning. foldr f and foldl f may differ, for the same aggregation function f.

Example.

• foldr (-) 0 [1,2,3] evaluates to 1 - (2 - (3 - 0)) = 2
• foldl (-) 0 [1,2,3] evaluates to ((0 - 1) - 2) - 3 = - 6

find #

The function

find :: (a -> Bool) -> [a] -> Maybe a

is defined in the Haskell module Data.List.

We will see how find can be implemented (and the meaning of Maybe a) in the section about the option type (second exercise).

The expression find f xs evaluates to:

• Just x if x is the first value in xs for which fs is True, and
• Nothing otherwise.

Examples.

• find even [1,4,5,2,6,1] evaluates to Just 4
• find even [1,3] evaluates to Nothing
• find even [] evaluates to Nothing

flip #

The function flip intuitively swaps the arguments of a function with two arguments in curried form.

It can be defined as follows:

flip :: (a -> b -> c) -> b -> a -> c
flip f y x = f x y

Example.

-- Checks whether a list contains an element
contains :: (Eq a) => [a] -> a -> Bool
-- flip the function `appearsIn` defined in exercise above
contains = flip appearsIn