COMP0020: Functional Programming Example Programs
COMP0020 Functional Programming Lecture 14
Lists as Functions
2 : reversed lists
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 1 / 18
COMP0020: Functional Programming Example Programs
Motivation
Primarily to give a better understanding of, and facility with, higher order functions
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 2 / 18
COMP0020: Functional Programming Example Programs
Contents
Preamble (repeated from last lecture)
Curried functions
Higher order functions (functions as args)
Higher order functions (function as result)
Example :
reminder : normal lists as functions
new : adding elements to a list in reverse order
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 3 / 18
COMP0020: Functional Programming Example Programs
Preamble (1)
Recall CURRIED functions :
fabc=(a+b)
Can help to think of binary tree giving syntax of the function applied to its arguments :
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 4 / 18
COMP0020: Functional Programming Example Programs
Preamble (2)
Recall HIGHER ORDER functions :
fabc=c(ab)
c must be a function (of at least one argument)
a must be a function (of at least one argument)
e.g. f (*2) 4 (+1)
= (+1) ((*2) 4) = 1 + (2 * 4)
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 5 / 18
COMP0020: Functional Programming Example Programs
Preamble (3)
Recall HIGHER ORDER functions can return functions :
gab=(+a) main = g 3 4 5
Too many args ? No!
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 6 / 18
COMP0020: Functional Programming Example Programs
consabf =f nil f= f
headx = xh where
a b (error ”head of nil”) (error
False True
′A′ nil ′B′ z
′B′ z) h ′B′ z h z False
tail x
isnil x
habc=a = xt
where
tabc=b = xg
where gabc=c
”tail of nil”)
|| Example :
|| z=cons
|| y=cons ||
|| head y
|| → (cons
|| → cons
|| →h′B′
|| → ′B′
head tail isnil
↓↓↓
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
7 / 18
COMP0020: Functional Programming Example Programs
Consider :
head (tail (tail (cons a (cons b nil))))
→ (tail (tail (cons a (cons b nil)))) h → ( (tail (cons a (cons b nil)) t) h → ( ( (cons a (cons b nil)) t) t) h → ( ( cons a (cons b nil) t) t) h
→ ( ( t a (cons b nil) False) t) h → ( (cons b nil) t) h
→ ( cons b nil t) h
→ (t b nil False) h
→ nil h
→ h (error “head of nil”) (error “tail of nil”) True → error “head of nil”
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 8 / 18
COMP0020: Functional Programming Example Programs
Consider :
isnil nil
→ nil g
→ g (error “head of nil”) (error “tail of nil”) True → True
isnil (cons a nil)
→ (cons a nil) g → g a nil False → False
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
9 / 18
COMP0020: Functional Programming Example Programs
Reversed lists as functions !
Sometimes you may find that you need to add elements to a list, but that the elements arrive in the reverse order to the order in which you wish to process them.
Either save in a list and then reverse the list (slow)
Or use a special data type that allows you to add in reverse order but creates the list the right way
around !
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 10 / 18
COMP0020: Functional Programming Example Programs
Reversed lists as functions !
|| Type definition of a reversed list (called an ”rlist”) − it′s a function! rlist ∗ == [∗]−> [∗]
|| Definition of rcons which adds an element to a rlist (c.f . (:) :: ∗− > [∗]− > [∗])
rcons :: ∗ rcons v g =
−> rlist ∗ −> rlist ∗ f
where
f x = g (v : x)
which is the empty rlist
|| Definition of rnil rnil :: rlist ∗
rnil x = x
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
11 / 18
COMP0020: Functional Programming Example Programs
rlist (alternative definition for rcons)
rcons :: ∗−> rlist ∗ −> rlist∗ || ∗ −> ([∗]−> [∗])−> ([∗]−> [∗]) || ≡ ∗−> ([∗]−> [∗])−> [∗]−> [∗]
rcons v g x = g (v : x)
NB : for function types, type expressions bracket from the right. Thus :
num−> num−> num−> num ≡num−> (num−> (num−> num))
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 12 / 18
COMP0020: Functional Programming Example Programs
rlist
|| Defined previously : rlist ∗ == [∗]−> [∗] rcons v g x = g (v : x) rnil x = x
|| Definition of rhd which gives the head of the rlist (in correct sequence!) rhd :: rlist ∗ − > ∗
rhdg = hd(g[])
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 13 / 18
COMP0020: Functional Programming Example Programs
rlist
|| Defined previously : rlist ∗ == [∗]−> [∗] rcons v g x = g (v : x) rnil x = x
rhdg = hd(g[])
|| Example :
x = (rcons 2 (rcons 3 rnil)) main = rhd x
→ hd ((rcons 2 (rcons 3 rnil)) []) → hd ((rcons 3 rnil) (2 : []))
→ hd (rnil (3:(2: [])))
→ hd (3:(2: []))
→3
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
14 / 18
COMP0020: Functional Programming Example Programs
rlist
|| Defined previously : rlist ∗ == [∗]−> [∗] rcons v g x = g (v : x) rnil x = x
rhdg = hd(g[])
|| Turning an rlist into a list rlist2list :: rlist ∗ − > [∗] rlist2list r = r []
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
15 / 18
COMP0020: Functional Programming Example Programs
rlist
|| Defined previously : rlist ∗ == [∗]−> [∗] rcons v g x = g (v : x) rnil x = x
rhdg = hd(g[]) rlist2list r = r []
|| Example :
main = rlist2list (rcons ′A′ (rcons ′B′ rnil)) → rcons ′A′ (rcons ′B′ rnil) []
→ (rcons ′B′ rnil) (′A′ : [])
→ rnil (′B′ : (′A′ : []))
→ (′B′ : (′A′ : [])) ≡ [′B′,′ A′]
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
16 / 18
COMP0020: Functional Programming Example Programs
Summary
Summary
Two Examples :
reminder : normal lists represented by functions
new : adding elements to a list in reverse order
Motivation :
Primarily, to give a better understanding of, and facility with, higher order functions
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 17 / 18
COMP0020: Functional Programming Example Programs
Summary
END OF LECTURE
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 18 / 18