Higher-Order Functions

• Takes functions as arguments
• Returns a function as a result

Why are They Useful?

• Common programming idioms can be encoded as functions within the language itself
• Domain specific languages can be defined as collections of higher-order functions
• Algebraic properties of higher-order functions can be used to reason about programs

Map

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

-- List comprehension
map f xs = [f x | x <- xs]

-- Recursion (for proof)
map f [] = []
map f (x:xs) = f x : map f xs

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f xs ys = map (uncurry f) $ zip xs ys

Filter

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

-- List comprehension
filter f xs = [x | x <- xs, f x]

-- Recursion
filter p [] = []
filter p (x:xs)
    | p x         = x : filter p xs
    | otherwise   = filter p xs

Fold

• Think of foldr non-recursively:
  • Replacing each (:) in a list by a given function,
  • Replacing each [] by a given value
• Benefits
  • Some recursive functions on lists are simpler to define using foldr
  • Properties of functions can be proved using algebraic properties of foldr e.g. fusion & banana split rule
  • Compiler knows better how to optimize

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr op v []     = v
foldr op v (x:xs) = x `op` foldr op v xs

foldl :: (a -> b -> b) -> a -> [b] -> a
foldl op v []     = v
foldl op v (x:xs) = foldl op (v `op` x) xs

unzip :: [(a, b)] -> ([a], [b])
unzip xs = foldr (\(x, y) (xs, ys) -> (x:xs, y:ys)) ([], []) xs

Examples:

sum :: [Int] -> Int
-- sum []     = 0
-- sum (x:xs) = x + sum xs
sum = foldr (+) 0

product :: [Int] -> Int
-- product []     = 1
-- product (x:xs) = x * product xs
product = foldr (*) 1

and :: [Bool] -> Bool
-- and []     = True
-- and (x:xs) = x && and xs
and = foldr (&&) True

length :: [a] -> Int 
-- length []     = 0
-- length (_:xs) = 1 + length xs
length = foldr (\_ y -> 1 + y) 0

reverse :: [a] -> [a]
-- reverse []     = []

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

(++ ys)  = foldr (:) ys
map f    = foldr (\x xs -> (f x):xs) []
filter f = foldr (\x xs -> if f x then (x:xs) else xs) []

Others

(.)

• Composition of 2 functions

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

• Point-free (argument-free)

sumOdds :: [Int] -> Int
-- sumOdds xs = sum (filter odd (filter (> 0) xs))
sumOdds = sum . filter odd . filter (> 0)

all

• If every element of a list satisfies a condition

all :: (a -> Bool) -> [a] -> Bool
all p xs = and [p x | x <- xs]

any

• If any element of a list satisfies a condition

any :: (a -> Bool) -> [a] -> Bool
any p xs = or [p x | x <- xs]

takeWhile

• Select elements from a list while predicate holds

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile p [] = []
takeWhile p (x:xs)
   | p x       = x : takeWhile p xs
   | otherwise = []

dropWhile

• Remove elements from a list while predicate holds

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

dropWhile p [] = []

dropWhile p (x:xs)
    | p x
        = dropWhile p xs
    | otherwise

= x:xs