Further Programming Paradigms
Lecture 17: Higher Order Functions I (Function Composition)
Dr Martin Barrere, University of Surrey
(Slides designed by Prof. Paul Krause, University of Surrey)
Warning: Some Viewers may find this content
disturbing
What we are going to do
• Explore more the application of functions to other functions (“higher order
functions”)
• Explore function application and currying a little further
• Dip into the mathematics a little bit
• So we can start to think more about verification of functional programs
• This lecture mainly draws on Chapter 11 of Haskell: the craft of functional
programming
This is the power of functional programming
(but it is a little bit tricky)
Functions are data:
• Functions can be combined using operators
• Lambda abstractions allow us to define functions directly in expressions
• Functions can be the inputs and outputs of other functions
• It is possible to partially apply functions, so that functions are the results of
applying functions
Function composition
• Haskell uses the formal mathematical representation of functional composition
(f.g) x = f (g x)
• In the composition (f.g) x, g is applied first and then f is applied to the
result of (g x)
rotate :: Picture -> Picture
rotate pic = flipV (flipH pic)
• OR
rotate pic = [Link] pic f.g
a b c
g f
Function Composition II
In general, the constraints on which functions can be composed is expressed by
giving `.` the type:
(.) :: (b -> c) -> (a -> b) -> (a -> c)
type of f type of g type of f.g
So,
• The input of f and the output of g are of the same type: b.
• The result of f.g has the same input type as g (a) and the same output type of
f (b)
Note also, Composition is associative
• f.(g.h) is equal to (f.g).h for all f, g, h
• f.g.h means “apply h, then g, then f
Remember
• Order of function application goes from right to left:
rotate pic = [Link] pic
• Read as: flip horizontally, then flip vertically
• If you prefer, you can define your own operator that evaluates from left to right
but we will stay with the above in order to maintain consistency with the
underlying mathematical notation
