COMP0020: Functional Programming Designing Functional Programs
COMP0020 Functional Programming Lecture 8
Designing Functional Programs
(2)
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 1 / 21
COMP0020: Functional Programming Designing Functional Programs
Contents
Structural induction : example “append”
Passing data between functions : “isort”
Modes of recursion : tail recursion and mutual recursion Removing mutual recursion
Lazy evaluation : infinite lists
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 2 / 21
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “append”
The “append” function takes two lists of anything and returns a single list consisting of all the elements of the first list, followed by all the element of the second list
Type :
append : : ([*], [*]) -> [*]
Possible Induction hypotheses :
append (xs, (y : ys)) OR : append ((x : xs), ys) OR : append (xs, ys)
to help define the general case :
append ((x : xs), (y : ys)) = ????
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 3 / 21
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “append”
Think about what each possible induction hypothesis would give you
For example, if we want to define the general case for append ([1,2,3], [4,5,6]) :
append(xs, (y : ys)) append((x : xs), ys) append(xs, ys)
gives gives gives
[2, 3, 4, 5, 6] − does that help? [1, 2, 3, 5, 6] − does that help? [2, 3, 5, 6] − does that help?
Christopher D. Clack (University College London)
COMP0020: Functional Programming Academic Year 2019-2020 4 / 21
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “append”
Answer : use append (xs, (y :ys)) as the induction hypothesis. Thus, there is only one parameter of recursion. The general case is :
Or, simply :
append ((x :xs), (y :ys)) = x : (append (xs, (y :ys))) append ((x :xs), any) = x : (append (xs, any))
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 5 / 21
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “append”
Base case (for parameter of recursion) :
append ([], (y :ys)) = ???? We choose the answer to be (y :ys)
Or, simply :
append ([], (y :ys)) = (y :ys) append ([], any) = any
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 6 / 21
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “append”
Final solution :
append :: ([∗], [∗])
append ([], any)
append ((x : xs), any) = x : (append (xs, any))
− > [∗] = any
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 7 / 21
COMP0020: Functional Programming Designing Functional Programs
Passing data between functions
A functional program usually contains several (many) functions Focus on how data passes between those functions
Example : insertion sort “isort”
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 8 / 21
COMP0020: Functional Programming Designing Functional Programs
Insertion Sort (specification)
Define “sorted list”
An empty list is already sorted
A singleton list is already sorted
The list (x :xs) is sorted if
⋆ x is less than all items in xs, AND
⋆ xs is sorted
NB only lists of numbers
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 9 / 21
COMP0020: Functional Programming Designing Functional Programs
Insertion Sort (strategy)
Start with two lists A and B
A is the input list
B is initially empty
One at a time, move an element from A to B Ensure that at all times B is sorted
We will need a function that can insert a number into a sorted list and return a sorted list
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 10 / 21
COMP0020: Functional Programming Designing Functional Programs
Insertion Sort (design)
The list B is an accumulator
So use accumulative recursion
Top-down approach : assume the function “insert” exists and design the rest of the program first
(leap of faith !) Then design “insert”
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 11 / 21
COMP0020: Functional Programming Designing Functional Programs
Insertion sort
||comments . . .
isort :: [num] − > [num] isort any = xsort any []
||comments . . .
xsort :: [num] − >[num] − > [num]
xsort [] sorted = sorted
xsort (x : xs) sorted = xsort xs (insert x sorted)
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 12 / 21
COMP0020: Functional Programming Designing Functional Programs
Insertion sort
Code for “insert”
||comments . . .
insert :: num − > [num] − > [num]
insert x [] = [x]
insert x (y :ys) = (x :(y :ys)), if (x
insert x [] insert x (y :ys)
= [x]
= (x :(y :ys)), if (x
xsort :: [num] − >[num] − > [num]
xsort [] sorted = sorted
xsort (x : xs) sorted = xsort xs (insert x sorted)
insert :: num − > [num] − > [num]
insert x [] insert x (y :ys)
= [x]
= (x :(y :ys)), if (x
mylast [] = error “no last item of empty list′′ mylast (x : []) = x
mylast (x : xs) = mylast xs
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 16 / 21
COMP0020: Functional Programming Designing Functional Programs More modes of recursion
More modes of recursion
2 : mutual recursion
nasty :: [char] nasty []
nasty (′(′: rest) nasty (x : xs)
− > [char]
= []
= xnasty rest
= (x : (nasty xs))
− > [char]
= error “missing end bracket′′
xnasty :: [char]
xnasty []
xnasty (′)′ : rest) = nasty rest xnasty (x : xs) = xnasty xs
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 17 / 21
COMP0020: Functional Programming Designing Functional Programs More modes of recursion
Removing mutual recursion
skip :: [char] skip []
skip (′(′: rest) skip (x : rest)
− > [char]
= []
= skip (doskip rest) = (x : (skip rest))
− > [char]
= error “missing end bracket′′
doskip :: [char]
doskip []
doskip (′)′ : rest) = rest doskip (x : xs) = doskip xs
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 18 / 21
COMP0020: Functional Programming Designing Functional Programs More modes of recursion
Lazy evaluation : infinite lists
Lazy evaluation of function arguments
Evaluate fst (24, (37 / 0))
Remember definition of fst :
fst : : (*,**) -> * fst (x,y) = x
Lazy evaluation of data constructors (e.g. the “cons” operator for lists)
Some forms of “bad” recursion may NOT result in infinite execution because lazy evaluation of data constructors means that they are evaluated ONLY AS FAR AS NECESSARY :
f : : num -> [num]
f x = (x : (f (x + 1))
main = hd (tl (f 34))
Another example :
ones = (1 : ones)
main = hd (tl (tl ones))
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
19 / 21
COMP0020: Functional Programming Designing Functional Programs
Summary
Summary
Structural induction : example “append”
Passing data between functions : example “isort” Modes of recursion : tail recursion and mutual recursion Removing mutual recursion
Lazy evaluation : infinite lists
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 20 / 21
COMP0020: Functional Programming Designing Functional Programs
Summary
END OF LECTURE
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 21 / 21