Mission 1 · Spec 4.12.1 – 4.12.2
Functions in the functional paradigm
Function types, domains and codomains, first-class objects, function application, partial application and composition.
- Starter 5 min
- Learn 20 min
- Lab 10 min
- Quiz 10 min
- Exam 15 min
A machine that makes machines
add x y = x + y. What do you think add 3 is, if you only give it one argument?
Reveal
A new function that adds 3 to whatever it's given. That's partial application: functions can return functions, because in functional programming functions are first-class objects.
Key ideas
Function type
f: A → B means f maps each element of its domain A to an element of its codomain B. Not every codomain value has to be an output.
First-class objects
Functions can be passed as arguments, returned from functions and assigned to names, like any other value.
Function application
Giving a function its arguments. add 3 4 applies add to 3 and 4.
Partial application
add :: Integer -> Integer -> Integer can be read as Integer -> (Integer -> Integer): add 3 returns a function Integer -> Integer.
Composition
g ∘ f applies f then g: (g ∘ f)(x) = g(f(x)). The codomain of f must match the domain of g. In Haskell: g . f.
Match the concept
Exam-style questions
1. f(x) = x + 2 and g(x) = 3x. Calculate (g ∘ f)(4) and (f ∘ g)(4).
[2 marks]Mark scheme
- (g ∘ f)(4) = g(6) = 18 (1)
- (f ∘ g)(4) = f(12) = 14 (1)
2. The function mult :: Integer -> Integer -> Integer multiplies two integers. Explain what mult 5 returns.
Mark scheme
- A function (of type Integer -> Integer) (1)
- that multiplies its argument by 5 (partial application) (1)
TUTOR NOTES
- Practical: try these in GHCi or an online Haskell REPL.
Mission 2 · Spec 4.12.3 – 4.12.4
Map, filter, fold and lists
Writing functional programs with higher-order functions, and processing lists with head, tail, empty tests, length, prepend and append.
- Starter 5 min
- Learn 15 min
- Lab 20 min
- Quiz 10 min
- Exam 15 min
No loops allowed
How would you total the squares of the even numbers in a list without writing a single loop?
Reveal
foldl (+) 0 (map (^2) (filter even xs)): filter keeps the evens, map squares them, fold adds them up.
Key ideas
map
Applies a function to every element, producing a new list. map (*2) [1,2,3] → [2,4,6]
filter
Keeps the elements that satisfy a condition. filter even [1,2,3,4] → [2,4]
fold (reduce)
Combines the elements into a single value using a function and a starting value. foldl (+) 0 [1,2,3] → 6
Lists
A list is a head (first element) and a tail (the rest, itself a list). head, tail, null (test for empty), length, prepend x : xs, append xs ++ [x].
Functional pipeline
Exam-style questions
1. xs = [4, 7, 2, 9]. Give the result of: (a) head xs (b) tail xs (c) map (+1) xs (d) foldl (*) 1 xs
Mark scheme
- (a) 4 (1)
- (b) [7, 2, 9] (1)
- (c) [5, 8, 3, 10] (1)
- (d) 504 (1)
2. Explain the purpose of the fold function.
[2 marks]Mark scheme
- Reduces a list to a single value (1)
- by repeatedly applying a combining function, starting from an initial value (1)
TUTOR NOTES
- Check: 4 × 7 × 2 × 9 = 504.