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.

Pre-Lab 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

  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/2023s2/studentfiles/lab08-1100_s2_2023

  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 reflect 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 file Lab08.hs. This file is pre-filled 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 type Bool

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 folds, 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

bars search times arrow-up