In this lab we cover higher order functions  particularly, functions that can take other functions as input. These can be used to avoid rewriting common code patterns, and generalise many patterns of recursion that we’ve already seen.
 PreLab Checklist
 Getting Started
 Higher Order Functions
 Recursive Higher Order Functions
 More List Manipulation
 Recap
 Folding up a list
 Using higher order functions
 Checkpoint
 Extensions (Optional)
PreLab Checklist
 You should have finished and submitted Labs 5 and 6.
 You are comfortable with writing simple functions using guards.
 You know what case statements and patterns are, and how to use them.
 You are comfortable with recursive functions over numbers and lists.
 You are familiar with the concept of partial function application from lectures.
Getting Started

Go to the project’s dashboard under the Project tab and click on the Fork button. The gitlab url for this lab is https://gitlab.cecs.anu.edu.au/comp1100/2023s2/studentfiles/lab081100_s2_2023

You will be asked where to fork the repository. Click on the user or group to where you’d like to add the forked project. You should see your own name here. Once you have successfully forked a project, you will be redirected to a new webpage where you will notice your name before
> projectname
. This means you are now the owner of this repository. The url in your browser should reflect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/lab08 
Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.

Put your exercise solutions in the file
Lab08.hs
. This file is prefilled with unfinished functions that match the exercises below.
This lab contains additional exercises for COMP1130 students. COMP1100 students are encouraged to attempt them once they have completed the compulsory exercises to receive the participation marks for the lab.
Put all of your solutions to the following exercises in the file Lab08.hs
.
Higher Order Functions
A higher order function is a function that takes other functions as input, or gives them as output. Functions that take other functions as input can help cut down on code duplication, as many functions we write have the same underlying recursive structure.
If you were asked to list some types in Haskell, things like String
,
Bool
, Integer
might come to mind. But you might not think of
Integer > String
as a type, rather, as a function that takes one
type and returns another.
The fact is that in Haskell, there is fundamentally no difference between simple types, and more complicated types that describe functions. They are two sides of the same coin. In fact, one can consider the following function:
three :: Integer
three = 3
It takes zero arguments, and returns the number 3. The function that takes no arguments and returns 3 is the same as the number 3 itself.
Furthermore, there’s no reason why functions can’t take other functions as input (if you consider 3 to be a function as above, then we’ve already been doing this the entire time).
Consider the following function:
applyFunc :: (Integer > Bool) > Integer > Bool
applyFunc function int = function int
It doesn’t look like a very useful function, but it’s our first
example of a higher order function. applyFunc
takes two inputs, one
being a function from Integer > Bool
and the second being the
Integer
to feed into that function. applyFunc
then does exactly
what the name implies — it applies the given function to the given
input.
Exercise 1
You might have seen before in high school the concept of function composition (denoted by the operator \(\circ\)). We can take two already existing functions, and define a new function by applying the first function, and then the second.
For example, if \(f(x) = x^2\) and \(g(x) = x+1\), then \((f \circ g)(x) = f(g(x)) = f(x+1) = (x+1)^2\) and \((g \circ f)(x) = g(f(x)) = g(x^2) = x^2 + 1\).
We can do the same in Haskell. Unlike the above example, the types don’t even have to all be the same.
Try to write a function compose
that evaluates the composition of
two functions, given an input. You will need to figure out what the
type should be. Try to make it as general as possible.
compose :: ???
compose f g x = ???
Using your newly written compose
function, and given the two
following functions:
square :: Integer > Integer
square x = x^2
inc :: Integer > Integer
inc x = x + 1
try to define the following functions, using only compose
,
square
and inc
. You should use the newly defined compose
function, rather than just composing the functions yourself,
(Hint: Consider partial function application for quadThenInc
. Do
not just add one afterwards using +1
.)
  Computes the function f(x) = (x+1)^2
incThenSquare :: Integer > Integer
incThenSquare = undefined  TODO
  Computes the function f(x) = x^2 + 1
squareThenInc :: Integer > Integer
squareThenInc = undefined  TODO
  Computes the function f(x) = x+2
add2 :: Integer > Integer
add2 = undefined  TODO
  Computes the function f(x) = x^4 + 1
quadThenInc :: Integer > Integer
quadThenInc = undefined  TODO
Submission required: Exercise 1 compose
Function composition is such a useful concept that it already exists
in Haskell, as the operator (.)
. The composition operator (.)
is
infix, just like (+)
or (:)
, meaning we put it in between it’s two
inputs. So instead of writing compose square inc 4
, we can write
(square.inc) 4
.
Recursive Higher Order Functions
So far, it doesn’t seem like higher order functions are very useful. Why would I need to a function to apply another function, when I can just do it directly? The real power comes when we combine functions taking other functions as input, with recursion.
As an example, consider the following three functions incAll
,
negateAll
and isLeast100All
. incAll
adds one (increments) each
integer in a list. negateAll
negates each boolean in a
list. isLeast100All
checks if each number in the list is at least
100, returning True
or False
for each element appropriately.
incAll :: [Integer] > [Integer]
incAll list = case list of
[] > []
x:xs > (x+1) : incAll xs
negateAll :: [Bool] > [Bool]
negateAll list = case list of
[] > []
x:xs > (not x) : negateAll xs
isLeast100All :: [Integer] > [Bool]
isLeast100All list = case list of
[] > []
x:xs > (x >= 100) : isLeast100All xs
> incAll [0,1,2,3]
[1,2,3,4]
> negateAll [False, False, True]
[True, True, False]
> isLeast100All [7,105,100,200]
[False, True, True, False]
Apart from swapping out the function applied to x
(either (+1)
, or
not
, or (>= 100)
) these functions are exactly the same, and the rest
of the code is duplicated. We’d like a way to make our code more
modular, so that the only thing that needs to change is the function
that we are applying to each element.
We will call our new function myMap
, which takes a function, and a
list, and applies that function to each element.
myMap :: ???
Try to make the type signature as general as possible. If you’re
having trouble working out the type signature, see the function
applyFunc
above, and see how brackets are used to indicate that one
of the inputs to the function is itself, another function.
Exercise 2
Try to write the myMap
function. Once you’ve done that, write out
new definitions of incAll
, negateAll
and isLeast100All
that use
your newly defined myMap
function.
Submission required: Exercise 2 myMap
, incAll
, negateAll
, isLeast100All
More List Manipulation
Implement the following higher order functions.
Exercise 3
myFilter
takes two inputs:
 A list of type
a
 A function that takes a type
a
to a typeBool
It returns the same list, but only keeping those elements for which
the function evaluated to True
.
Write the myFilter
function.
> myFilter even [1,2,3,4,5]
[2,4]
> myFilter (elem 'e') ["apple", "plum", "banana", "pear"]
["apple","pear"]
Submission required: Exercise 3 myFilter
Exercise 4
myZipWith
takes three inputs:
 Two lists.
 A binary function with inputs that match the types of the two lists.
Output is the result of taking pairs of successive elements from each list, and applying the operation.
Write the myZipWith
function.
> myZipWith (+) [1,2,3] [5,10,20]
[6,12,23]
> myZipWith (==) ["hello","cow"] ["world","cow"]
[False, True]
> myZipWith (elem) [3,6,1] [[1,2,3],[10,20,30],[1, 0, 1]]
[True,False,True]
(Hint: You may want to write this function by using a pattern match against both lists at once, by forming them into a tuple.)
myZipWith func list1 list2 = case (list1,list2) of
([],[]) > ???
(? ,? ) > ???
For lists of different length, a reasonable interpretation would be to throw an error, as we cannot pair all the elements up. Here, we would like you to discard the extra elements of the longer list. As an example:
> myZipWith (+) [1,2,3] [10,20,30,40,50]
[11,22,33]
Submission required: Exercise 4 myZipWith
Exercise 5
repeatApply
takes 3 inputs:
 A function
f
, with the same input and output type.  An integer
n
, indicating the number of times to apply the function.  An element
x
with suitable type to insert into the function.
Output is the result of applying the function f
to x
, n
many
times. (So if n=3
, the output should be f(f(f(x)))
. Applying f
zero many times just returns x
unchanged.) Make the type as general
as can be.
Write the repeatApply
function.
> repeatApply (*2) 3 1
8
> repeatApply (++ " NO") 5 "OH"
"OH NO NO NO NO NO"
Make sure your function does something sensible when n
is negative.
Submission required: Exercise 5 repeatApply
Recap
We’ve written higher order functions to perform operations like:
 Applying a function to each element in a list. (
myMap
)  Choosing some elements from a list based on some condition. (
myFilter
)  Combining two lists with an operation (
myZipWith
)
These operations are so common, that are already available as part of
the Haskell language. (They are named map
, filter
, zipWith
respectively.)
By writing the recursive structure once, we can then reuse the same code over and over again elsewhere, saving both on errors, and on time spent writing.
Folding up a list
The last higher order function we will discuss are fold
s,
which (for the most part) use a binary operation over and over again to
combine an entire list into one element. We first motivate fold
by demonstrating some functions below that have a similar underlying
structure, that we hope to replace using fold
.
sumList :: [Integer] > Integer
sumList list = case list of
[] > 0
x:xs > x + sumList xs
productList :: [Integer] > Integer
productList list = case list of
[] > 1
x:xs > x * productList xs
allTrue :: [Bool] > Bool
allTrue list = case list of
[] > True
x:xs > x && allTrue xs
anyTrue :: [Bool] > Bool
anyTrue list = case list of
[] > False
x:xs > x  anyTrue xs
concatenate :: [[a]] > [a]
concatenate list = case list of
[] > []
x:xs > x ++ concatenate xs
doNothingList :: [a] > [a]
doNothingList list = case list of
[] > []
x:xs > x : (doNothingList xs)
> sumList [1,2,3,4]
10
> productList [1,2,3,4]
24
> allTrue [True,False,True]
False
> allTrue [True, True]
True
> anyTrue [False, True, False]
True
> anyTrue [False, False]
False
> concatenate ["Hello","World","!"]
"HelloWorld!"
> doNothingList [1,2,3]
[1,2,3]
These functions follow the same style of folding an entire list down into a value using a binary operator.
Often that value will have the same type as the elements of the list,
but the last function doNothingList
shows that this is not
necessary.
This indicates that folding is a much stronger property that just “squish a list into a single element”. For the most part, folding is used in that manner, but folding is more accurately thought of as “traversing the list, and remembering a key piece of information along the way”. See the extension exercises at the end for more!
We can capture the structure of the above functions in a general manner:
foldRight :: (a > b > b) > b > [a] > b
foldRight op e list = case list of
[] > e
x:xs > x `op` (foldRight op e xs)
(The backticks around op
allow you to write it as an infix function,
just like how we write 2 + 3
instead of + 2 3
.)
When we hit the base case for the list, we need to choose a value e
that is suitable to return for the empty list. The value for the base
case e
, referred to as the identity, is usually an identity for
the operator op
, that is, it satisfies the property that for any
x
, that x
op e = e
op x = x
.
The reason this is called a right fold is because the order the operator is evaluated in is right associative.
As an example:
> foldRight (+) 0 [1,2,3]
> 1 + (foldRight (+) 0 [2,3])
> 1 + (2 + (foldRight (+) 0 [3]))
> 1 + (2 + (3 + (foldRight (+) 0 [])))
> 1 + (2 + (3 + 0))
6
It’s also possible to implement a left fold, so the operators are evaluated in left associative order:
foldLeft :: (b > a > b) > b > [a] > b
foldLeft op e list = case list of
[] > e
x:xs > foldLeft op (e `op` x) xs
> foldLeft (+) 0 [1,2,3]
> foldLeft (+) (0 + 1) [2,3]
> foldLeft (+) ((0 + 1) + 2) [3]
> foldLeft (+) (((0 + 1) + 2) + 3) []
> ((0 + 1) + 2) + 3
6
Summary of operators and identities
Looking at the above examples, we see the following identity elements.
Function  Operator  Identity  Description 

sumList 
+ 
0 
Adding zero 
productList 
* 
1 
Multiplying by one 
allTrue 
&& 
True 
Logical AND with True 
anyTrue 
 
False 
Logical OR with False 
concatenate 
++ 
[] 
Concatenating an empty list 
(Not all operators have identities, for example, the cons operator (:)
has no
identity, as there is no empty element for which e : [] = []
).
Exercise 6
Rewrite all of the functions sumList
, productList
, allTrue
, anyTrue
,
concatenate
, doNothingList
using either foldLeft
or foldRight
.
The definition of each function should only take up one line. Be
careful with doNothingList
, as you’ll need to consider whether a
right or left fold is appropriate.
Submission required: Exercise 6 sumList
, productList
, allTrue
, anyTrue
,
concatenate
, doNothingList
These functions actually already exist in the Haskell Prelude as
sum
,product
,all
,any
,concat
. We chose different names here to avoid
conflicts between your definition and the definition already present,
which would cause errors when you attempt to load the file in GHCi
.
Using higher order functions
Left and right folds are also common enough that they too are also
predefined in Haskell, as foldl
and foldr
respectively. Now that
you’ve seen higher order functions, use these and others available in
the Prelude to implement each of the following functions.
Your solution should take up a single line, and should not use guards, patterns or explicit recursion. You should try to do it only using higher order functions.
Exercise 7
Implement positiveSum
, average
, magnitude
, dot
using higher order
functions.
positiveSum :: [Integer] > Integer
Computes the sum of only the positive numbers in the list, ignoring negative numbers.
> positiveSum [1,2,3]
4
average :: [Double] > Double
Computes the average of a list of Double
.
The average of the collection \(\{x_1, x_2 ,\ldots, x_n\}\)
is defined to be:
\(\frac{x_1 + x_2 + \ldots + x_n}{n}\)
magnitude :: [Double] > Double
This computes the magnitude of a vector, represented as a [Double]
.
Magnitude of a vector is defined as:
\[\left \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} \right = \sqrt{x_1^2 + x_2^2 + \ldots + x_n^2}\](Hint: You will need the sqrt
function, which computes square roots.)
dot :: [Double] > [Double] > Double
Computes the dot product of two vectors, represented by [Double]
.
The dot product is defined as:
\(\begin{bmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n
\end{bmatrix}
\cdot
\begin{bmatrix}
y_1 \\
y_2 \\
\vdots \\
y_n
\end{bmatrix}
= x_1 y_1 + x_2 y_2 + \ldots + x_n y_n\)
Submission required: Exercise 7 positiveSum
, average
, magnitude
, dot
Exercise 8
myMaximum :: [Integer] > Integer
This find the maximum element in a list. (Obviously, don’t just cheat
and use maximum
or minimum
to help you here.)
Write the myMaximum
function using either foldLeft
or foldRight
.
(Hint: This one is tricky, and will require a fold. max
and min
don’t
really have an identity element, so what will you use instead?)
Submission required: Exercise 8 myMaximum
Checkpoint
Now is a good time to commit and push your work. This completes the primary activities of this lab.
Extensions (Optional)
Advanced Folding Techniques
So far we have mostly been treating a fold as a way to combine an entire list into a single element. Folding is actually a vastly more general technique. Folding recurses through a list, while remembering some piece of information, and updating that piece of information at each step through the list. That information could be the sum of all the elements seen so far, but it could also be a new list that’s being constructed, or a value of some other type.
The following exercises may be easier if you’re comfortable with lambda functions, but it’s not necessary to know them to proceed.
Extension 1
Try and figure out how to reverse a list using a fold.
Your solution should be of the form
reverseFold :: [a] > [a]
reverseFold list = fold func basecase list
where
func a b = ?
basecase = ?
where fold
is replaced with either foldl
or foldr
, func
is
some function you’ll need to figure out, and basecase
is the element
you return for an empty list, which you’ll also have to work out. If
you wish, you can replace func directly with an anonymous function, or
rename a
and b
to more useful names.
(Hint: Will it be a right fold or a left fold? Does it matter?)
Submission required: Extension 1 reverseFold
Extension 2
Rewrite the mapFold
(or map
, as named in the Prelude) function
from earlier, but using a fold.
mapFold :: (a > b) > [a] > [b]
mapFold f list = fold func basecase list
where
func a b = ?
basecase = ?
Submission required: Extension 2 mapFold
Extension 3
Rewrite the filterFold
(or filter
, as named in the Prelude) function from earlier, but using a fold.
Emulate a filter
using a fold. (A predicate is a fancy word for
a function that returns a Boolean.)
filterFold :: (a > Bool) > [a] > [a]
filterFold predicate list = fold func basecase list
where
func a b = ?
basecase = ?
Submission required: Extension 3 filterFold