Learning goals

  • To be able to explain precisely what a higher-order function is and what the type of a higher-order function is
  • To be able to explain precisely higher-order functions on lists including map, filter, foldr and foldl
  • To be able to explain and understand the recursive definitions of common higher-order functions on lists
  • To be able to use higher-order functions, including map, filter , foldr and foldl , for solving programming problems in Haskell
  • To be able to explain and use function composition in Haskell

Higher-order functions

Functions that either takes a function as an argument or returns a function.
Lecture talks about
map, which applies a given function to a given list

filter which does the same, but selects all elements from the list that satisfy the predicate in the function.

foldr (for ‘fold right’) abbreviates the below simple pattern of (primitive) recursion. Example use: sum = foldr (+) 0, where the operator section (+) is the operator to apply and 0 is the base case value. Another example: or = foldr (||) False.

f [] = v
-- <op> is some generic operator
f (x:xs) = x <op> f xs

-- Mental model for foldr
-- You can imagine it non-recursively as replacing the cons : operator with the given operator and empty list [] with the v (base case) value in the 'alternative' list representation.
-- Worked example:
sum [1,2,3,4]
-- is equivalent to
foldr (+) 0 (1:(2:(3:(4:[]))))
-- so you can imagine it just transforms it to
(1+(2+(3+(4+0))))

You can even define length using foldr:

-- We need to pass the lambda because this use case doesn't
-- quite match the aforementioned recursive pattern that foldr
-- matches. But by passing a lambda, we can make it work for this use case.
length = foldr (\_ n -> 1 + n) 0
-- You can imagine it doing
length [1,2,3,4]
-- being the same as
length (1:(2:(3:[])))
-- evaluates to
1+(1+(1+0))
-- resulting in
3

Likewise for reverse:

reverse = foldr (\x xs -> xs ++ [x]) []
-- Explanation
reverse [1,2,3]
reverse (1:(2:(3:[])))
(([] ++ [3]) ++ [2]) ++ [1]
[3,2,1]

When using foldr rather than explicit recursion, the GHC is able to use algebraic properties to perform program optimisations.

The library function (.) returns the composition of two functions as a single function, i.e. function composition.

odd :: Int -> Bool
odd = not . even

The library function all checks if every element of a list satisfies a given predicate.

The library function any checks if any element of a list satisfies a given predicate.

The library function takeWhile selects elements from a list while a predicate holds for all the elements.

The library function dropWhile drops elements from a list while a predicate holds for all the elements.

foldl vs. foldr

-- Imagine a function with a type like this
f :: a -> a -> a
-- And you have a list like this
[a1, a2, a3, a4]
-- A left fold does: f (f ( f a1 a2) a3) a4
-- While a right fold does: f a1 (f a2 (f a3))

-- Right fold implementation:
foldr :: (a -> a -> a) -> [a] -> a
foldr f [] = error "empty list"
foldr f [x] = x
foldr f (x:xs) f x (foldr f xs)

-- Left fold implementation:

Flashcards