COMP0020: Functional Programming Designing Functional Programs
COMP0020 Functional Programming Lecture 6
Designing Functional Programs
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 1 / 23
COMP0020: Functional Programming Designing Functional Programs
Contents
Answer to exercise
Currying and partial applications Approaches to design
Case analysis : example “reverse” Structural induction : example “startswith”
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 2 / 23
COMP0020: Functional Programming Designing Functional Programs
Stack recursion answer
|| threes is a function that takes a list of || numbers and returns the number of
|| occurrences of the number 3 in that list threes :: [num]− > num
threes [] = 0
threes (3 : rest) = 1 + (threes rest) threes (x : rest) = threes rest
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
3 / 23
COMP0020: Functional Programming Designing Functional Programs
Accumulative recursion answer
|| Alternative definition : fours :: [num] − > num
fours input = xfours where xfours xfours xfours
(input,0)
([],a) = a
((4 : rest), a) = xfours (rest, (a + 1)) ((x : rest), a) = xfours (rest, a)
Christopher D. Clack (University College London) COMP0020: Functional Programming
Academic Year 2019-2020
4 / 23
COMP0020: Functional Programming Designing Functional Programs
Currying
Functions that take more than one argument
Either collect arguments into a tuple
Or use “curried” definition (named after Haskell B. Curry)
A curried definition of a function that takes two arguments does not use a tuple. Compare curried function f and uncurried function g :
fxy =x+y g (x,y) = x + y
compare f with the lambda expression λx .(λy .(x + y )) The types of these functions are also different :
f ::num−>num−>num
g :: (num, num)− > num
Application is also different : (f 3 4) compared with g (3, 4)
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 5 / 23
COMP0020: Functional Programming Designing Functional Programs
Curried accumulative version
|| Alternative definition fives :: [num]− > num fives input =
xfives input 0 where
xfives []
xfives xfives
a =a
(5:rest) a =xfives rest (a+1)
(x : rest) a = xfives rest a
Christopher D. Clack (University College London)
COMP0020: Functional Programming Academic Year 2019-2020 6 / 23
COMP0020: Functional Programming Designing Functional Programs
Partial Applications
Only for curried functions
f :: num−> num−> num fxy=x+y
We can partially apply the function f to its first argument, and the result is a function of one argument :
Miranda (f 3) :: num − > num
We can give a name to a partial application :
fred = (f 3) main = fred 4
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 7 / 23
COMP0020: Functional Programming Designing Functional Programs
Partial Applications of operators
Operators have curried definitions and can also be partially applied
Miranda (+) :: num−> num−> num Miranda (+ 3) ::
num − > num
Operator sections :
Operator pre-sections : (3+)x ≡(3 + x), (2∗)x ≡(2 ∗ x), (5−)x ≡(5 − x), (9/)x ≡(9/x)
Operatorpost-sections:(+3)x≡(x + 3), (∗2)x≡(x ∗ 2), (/9)x ≡(x /9)
There is no post-section for the subtraction operator, because (−3) applies the unary minus operator to 3 to give negative 3.
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 8 / 23
COMP0020: Functional Programming Designing Functional Programs
Approaches to design
Case Analysis (see the book, Section 3.7.1)
consider what VALUES can occur as input to a function
use PATTERN MATCHING to match exact values or conditionals for relational tests
Structural Induction (see Section 3.7.2)
Helps you to write the “looping” part of a recursive function
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 9 / 23
COMP0020: Functional Programming Designing Functional Programs
Case Analysis
consider the function “myreverse”, which takes a list of anything and returns the list with all elements reversed :
myreverse :: [∗]− > [∗]
myreverse []
myreverse (x : []) myreverse (x : (y : [])) myreverse (x : (y : (z : []))) myreverse (x : rest)
= []
= (x : [])
= (y : (x : []))
= (z : (y : (x : []))) = ????
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
10 / 23
COMP0020: Functional Programming Designing Functional Programs
Case Analysis : “reverse”
To design the looping part of the function requires some thinking Look at the cases and their solutions and try to find a common theme In this case “reverse the rest of the list and put x at the end” :
myreverse (x : rest) = (myreverse rest) + + [x]
NB in the above code it is essential to put the item x inside a list (to create [x]) because the function ++ takes two lists as arguments. Compare this with the operator : (“cons”) which takes an element and a list of elements.
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 11 / 23
COMP0020: Functional Programming Designing Functional Programs
Case Analysis : “reverse”
Final version :
myreverse ::[∗]
myreverse []
myreverse (x : rest) = (myreverse rest) + + [x]
− > [∗] = []
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 12 / 23
COMP0020: Functional Programming Designing Functional Programs
Structural Induction
Induction versus Deduction Induction versus Structural Induction
Induction on Lists
Base Case
Induction hypothesis
Inductive step – you still need to do some thinking !
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 13 / 23
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “startswith”
The function “startswith” takes a two-tuple containing two lists of anything and returns True if the second list starts with the first list (otherwise it returns False)
E.g.
startswith ([1,2], [1,2,3,4]) returns True
startswith ([1,2], [2,3,4]) returns False
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 14 / 23
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “startswith”
Design Steps :
Specify the TYPE
Consider the General Case (the part that loops) before considering the base case
This helps to identify the parameter of recursion ! Consider the base case(s)
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 15 / 23
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “startswith”
Type
General case
startswith :: ([∗], [∗]) − > bool startswith ((x : xs),(y : ys)) =???
Possible induction hypotheses :
startswith (xs, (y : ys)) OR : startswith ((x : xs), ys) OR : startswith (xs, ys)
Which one of the above helps us to define startswith ((x : xs), (y : ys)) ?
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 16 / 23
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “startswith”
General case
startswith((x : xs),(y : ys)) =???
Use induction hypothesis : startswith (xs, ys) startswith ((x : xs), (y : ys))
= True, if (x = y) & startswith (xs, ys) = False, otherwise
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 17 / 23
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “startswith”
General case
Or, simply :
startswith ((x : xs), (y : ys))
= (x = y) & startswith (xs, ys)
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 18 / 23
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “startswith”
Base cases(s)
Because there are two parameters of recursion, we must consider two base cases : startswith ([], any)
and
startswith (any, [])
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 19 / 23
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “startswith”
Base case(s)
For the first base case, there is no obvious “right” or “wrong” solution – we choose to return True
startswith ([], any) = True For the second base case the result is obvious :
startswith (any, []) = False
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 20 / 23
COMP0020: Functional Programming Designing Functional Programs
Induction on Lists : “startswith”
The final solution is :
startswith :: ([∗], [∗])
startswith ([], any)
startswith (any, [])
startswith ((x : xs), (y : ys)) = (x = y) & startswith (xs, ys)
− > bool = True = False
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 21 / 23
COMP0020: Functional Programming Designing Functional Programs
Summary
Summary
Answer to exercise
Approaches to design
Case analysis : example “reverse” Structural induction :
Induction hypothesis
Inductive step
Base case(s)
Example “startswith”
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
22 / 23
COMP0020: Functional Programming Designing Functional Programs
Summary
END OF LECTURE
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 23 / 23