程序代写代做代考 COMP0020: Functional Programming Designing Functional Programs

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 [num] − > [num]
insert x [] insert x (y :ys)
= [x]
= (x :(y :ys)), if (x [num] isort any = xsort any []
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