Part 3: Higher-Order Functions

In this part of the course, we show how one can define list functions using accumulators, and when this new pattern should be used.

We then discuss how in Haskell, we can in general abstract recurring patterns into higher-order functions, and use this process to derive foldr and foldl'.

Finally, we discuss function composition and how we can now more and more often just combine known higher-order functions to achieve desired functionality rather than having to go via pattern matching.

Accompanying materials

3–1 Fast reverse

We discuss how we can make the reverse function significantly faster by introducing an accumulator.

Self Test

  • What does reverseAcc [1,2,3] [4,5,6] evaluate to?

  • Assignments A is asking you to define a function add on the type Nat of “Peano naturals”, and two possible solutions are

    data Nat = Zero | Suc Nat
  deriving Show

add1 :: Nat -> Nat -> Nat
add1 Zero    y = y
add1 (Suc x) y = Suc (add1 x y)

add2 :: Nat -> Nat -> Nat
add2 Zero    y = y
add2 (Suc x) y = add2 x (Suc y)

    In what way, if any, do the two versions of add have similarity to the two versions of reverse? Do you think there is a difference in efficiency here?

3–2 Strict Accumulators

We explain how accumulators can also help for other list functions such as sum, and why accumulators should in general be made strict by means of the BangPatterns language extension.

Self Test

  • Reimplement sum using a accumulator. Try to reproduce the stack overflow if the accumulator is not strict, and observe it disappears if you add it. (Note that you’ll have to start ghci with limited stack such as ghci +RTS -K1M.)

  • Implement length on lists using a strict accumulator.

3–3 Incremental Results

We see that function that want to produce results before the end of the list, or want to produce results incrementally, should not be written using accumulators.

Self Test

  • Which of the following functions should produce incremental or early results: filter, map, take, drop, all, and, words, inits, zip. (If there are any functions that you do not know or do not remember, use :i or :doc to find out more about them.)

  • Try to implement map using an accumulator. Do you succeed?

3–4 foldr

We explain how we can abstract from the “standard design pattern” on lists and thereby obtain the higher-order function foldr.

Self Test

  • Define or as a foldr.

  • Define filter as a foldr.

  • Consider the functions any, take and zip. Without actually doing it, how difficult do you think these are to implement using foldr, and why?

3–5 foldl’

We can also abstract from the “accumulating parameter pattern” on lists and thereby obtain the higher order function foldl'.

Self Test

  • Without actually implementing these, should the following functions be implemented using foldr or foldl'?
    1. A function that computes the average of a list of numbers.
    2. A function that computes a histogram of a list of numbers, i.e., it classifies the numbers according to their ranges.
    3. A function that tries to find an element in a list that satisfies a particular property.
    4. A function that removes adjacent duplicates from a list.
  • Should the maximum function be implemented using foldr or foldl'? Try to do so. What is the problem and how could one work around it? (Perhaps consider the Self Test for 2–12 once more.)

3–6 Function Composition

We introduce function composition that provides us with a nicer way to write “pipelines” of function calls. We also discuss more generally how we can, now that we know more functions, start writing functions not by pattern matching, but by combining other functions. We also discuss id and the explicit function application operator ($).

Self Test

  • Define replicate from assignment task B–13 as a function composition.

  • What is the difference between succ 3, succ $ 3 and succ . 3? Which ones work, which ones do not, and why?

  • What is the type of id id?

  • What does the function const do?

  • What does the function flip do?

  • What does the function (&) from Data.Function do?

  • What does the function on from Data.Function do? (Remember that you can use :doc to get some explanation on functions.)

3–7 Assignments C

Let’s get to the next block of assignments. You can find them here.

You can save this file to a local directory and then open it in your editor and GHCi. The file then contains further instructions and several skeletons of functions that you are supposed to complete, as well as a few other questions.

Note that in this public version of the course, there is no way to submit the assignments.

Continue this course

Next: Part 4: Parametric Polymorphism and Overloading.