COMP1100/1130 [2020 S1]:
PROGRAMMING AS PROBLEM SOLVING Research School of Computer Science
Menu
menu
» Labs » Week 8: Higher Order Functions
In this lab we cover higher order functions – particulary, 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.
Table of Contents
Pre-Lab Checklist
Higher Order Functions Recursive Higher Order Functions More List Manipulation
Folding up a list
Using higher order functions Extensions
Pre-Lab Checklist
You should have [nished 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. (See the lecture slides if you need a recap.)
Getting Started
1. 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/2020s1student[les/lab08
2. 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 > project-name. This means you are now the owner of this repository. The url in your browser should reaect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/lab08
3. Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.
4. Put your exercise solutions in the [le Lab08.hs. This [le is pre-[lled with un[nished functions that match the exercises below.
Put all of your solutions to the following exercises in the [le 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
as a function that takes zero arguments, and returns the number 3. The function taking no arguments and returning 3, and the number 3 itself, are precisely the same thing.
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:
It doesn’t look like a very useful function, but it’s our [rst 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
Suppose we want to have a version of the above function, applyOpInt that applies an operator (binary function) instead.
operator has type Integer -> Integer -> Integer, and the other two inputs n,m are both Integer’s.
Exercise 2
Modify the type signature of applyOpInt to make it as general as possible.
(Hint: Don’t just replace all the Integers in applyOpInt with a. It can be more general
than that.)
Submission required: Exercise 1+2 applyOpInt Exercise 2A
You might have seen before in high school the concept of function composition (denoted by the operator ∘). We can take two already existing functions, and de[ne a new function by applying the [rst function, and then the second.
For example, if f(x) = x2 and g(x) = x + 1, then (f∘g)(x)=f(g(x))=f(x+1)=(x+1)2 and (g∘f)(x)=g(f(x))=g(x2)=x2 +1.
We can do the same in Haskell. Unlike the above example, the types don’t even have to all be the same.
Using your newly written compose function, and given the two following functions:
try to de[ne the following functions, using only compose, square and inc. You should use the newly de[ned compose function, rather than just composing the functions yourself,
(Hint: Consider partial function application for quadThenInc. Do not just add one afterwards using +1.)
Submission required: Exercise 2A compose
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.
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)) the 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 3
Submission required: Exercise 3 myMap, incAll, negateAll, isLeast100All More List Manipulation
Implement the following higher order functions.
Exercise 4
myFilter takes two inputs: A list of type a
A function that takes a type a to a type Bool
It returns the same list, but only keeping those elements for which the function
evaluated to True.
Write the myFilter function.
Submission required: Exercise 4 myFilter Exercise 5
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.
(Hint: You may want to write this function by using a pattern match against both lists at once, by forming them into a tuple.)
Submission required: Exercise 5 myZipWith Exercise 6
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.
Make sure your function does something sensible when n is negative.
Submission required: Exercise 6 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)
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 folds, which (for the most part) use a binary operation over and over again to combine an entire list into one element. We [rst motivate fold by demonstrating some functions below that have a similar underlying structure, that we hope to replace using fold.
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.
We can capture the structure of the above functions in a general manner:
(The backticks around op allow you to write it as an in[x function, just like how we write 2 + 3instead 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 satis[es 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,
It’s also possible to implement a left fold, so the operators are evaluated in left associative order.
>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.
(Not all operators have identities, for example, the cons operator (:) has no identity, as there is no empty element for which e : [] = []).
Exercise 7
The de[nition 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.
Using higher order functions
Left and right folds are also common enough that they too are also prede[ned 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 8
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.
average :: [Double] -> Double
Computes the average of a list of Double. The average of the collection
{x1, x2, … , xn} is de[ned to be x1+x2+…+xn n
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.
three :: Integer three = 3
applyFunc :: (Integer -> Bool) -> Integer -> Bool applyFunc function int = function int
applyOpInt :: ???
applyOpInt operator n m = ???
Try and work out the type signature of applyOpInt, and then write the rest of the function.
Try to write a function compose that evaluates the composition of two functions, given an input. You will need to [gure out what the type should be. Try make it as general as possible.
compose :: ??? compose f g x = ???
square :: Integer -> Integer square x = x^2
inc :: Integer -> Integer inc x = x + 1
— | Computes the function f(x) = (x+1)^2
incThenSquare :: Integer -> Integer incThenSquare = ???
— | Computes the function f(x) = x^2 + 1
squareThenInc :: Integer -> Integer squareThenInc = ???
— | Computes the function f(x) = x+2
add2 :: Integer -> Integer add2 = ???
— | Computes the function f(x) = x^4 + 1
quadThenInc :: Integer -> Integer quadThenInc = ???
Function composition is such a useful function that it already exists in Haskell, as the operator (.). The composition operator (.) is in[x, 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.
incAll :: [Integer] -> [Integer] incAll list = case list of
[] -> []
x:xs -> (x+1) : incAll xs
Try to write the myMap function. Once you’ve done that, write out new de[nitions of incAll, negateAll and isLeast100All that use your newly de[ned myMap function.
> myFilter even [1,2,3,4,5]
[2,4]
> myF ilter (elem ‘e’) [“apple”, “plum”, “banana”, “pear”] [“apple”,”pear”]
> 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]
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]
>repeatApply (*2) 3 1
8
>repeatApply (++ ” NO”) 5 “OH” “OH NO NO NO NO NO”
These operations are so common, that are already available as part of the Haskell language. (They are named map, filter, zipWith respectively.)
sumList :: [Integer] -> Integer sumList list = case list of
[] -> 0
x:xs -> x + sumList xs
productList :: [Integer] -> Integer productList list = case list of
allTrue
allTrue
anyTrue
anyTrue
[] -> 1
x:xs -> x * productList xs
:: [Bool] -> Bool list = case list of
[] -> True
x:xs -> x && allTrue xs
:: [Bool] -> Bool 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]
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!
foldRight :: (a -> b -> b) -> b -> [a] -> b foldRight op e list = case list of
[] -> e
x:xs -> x `op` (foldRight op e xs)
>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
foldLeft :: (b -> a -> b) -> b -> [a] -> b foldLeft op e list = case list of
[] -> e
x:xs -> foldLeft op (e `op` x) xs
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
Rewrite all of the functions sumList, productList, allTrue, anyTrue, concatenate, doNothingList using either foldLeft or foldRight.
Submission required: Exercise 7 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 conaicts between your de[nition and the de[nition already present, which would cause errors when you attempt to load the [le in GHCi.
>positiveSum [1,-2,3] 4
magnitude :: [Double] -> Double
Computes the magnitude of a vector, represented as a [Double]. Magnitude of a vector
∣ ∣ ⎡⎢ x 1 ⎤⎥ ∣ ∣
is de[ned as ∣⎢ x2 ⎥∣ = √x21 + x2 + … + x2n (Hint: You will need the sqrt function,
∣⎣ ⋮ ⎦∣
∣ xn ∣
which computes square roots.)
dot :: [Double] -> [Double] -> Double
Computes the dot product of two vectors, represented by [Double]. The dot product is
⎡x1⎤ ⎡y1⎤
de[nedas⎢x2 ⎥⋅⎢y2 ⎥=x1y1 +x2y2 +…+x y
⎣ x ⋮ ⎦ ⎢⎣ y ⋮ ⎥⎦ n n nn
Submission required: Exercise 8 positiveSum, average, magnitude, dot Exercise 9
myMaximum :: [Integer] -> Integer
Finds 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 9 myMaximum Checkpoint
Extensions [COMP1100 Optional, COMP1130 Compulsory]
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 [gure out how to reverse a list using a fold.
Your solution should be of the form
where fold is replaced with either foldl or foldr, func is some function you’ll need to [gure 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
Submission required: Extension 2 mapFold Extension 3
Emulate a filter using a fold. (A predicate is a fancy word for a function that returns a boolean.)
Submission required: Extension 3 filterFold
Now is a good time to commit and push your work. If you’re in COMP1100, you can consider the lab completed.
reverseFold :: [a] -> [a]
reverseFold list = fold func basecase list
where
func a b = ?
Updated: 06 Jun 2020
Responsible Oocer: Director, RSCS
Page Contact:
Course Convenor
Contact ANU
Copyright
Disclaimer
Privacy
Freedom of Information
+61 2 6125 5111
The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906
basecase = ?
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 = ?
Rewrite the filterFold (or filter, as named in the Prelude) function from earlier, but using a fold.
filterFold :: (a -> Bool) -> [a] -> [a]
filterFold predicate list = fold func basecase list
where
func a b = ? basecase = ?