程序代写代做代考 C data structure COMP0020: Functional Programming

COMP0020: Functional Programming
Example Programs
COMP0020 Functional Programming Lecture 13
Example Programs
1. Evaluating arithmetic expressions
2. lists as functions
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 7 / 57

COMP0020: Functional Programming
Example Programs
Contents
Programming examples.
writing an evaluator for arithmetic expressions
I using algebraic types and recursion lists as functions
I using higher order functions
1
2
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 8 / 57

COMP0020: Functional Programming
Example Programs
Programming Example 1
Writing an evaluator for arithmetic expressions Motivation :
I a common style of programming
I a good example of using algebraic types and recursion
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 9 / 57

COMP0020: Functional Programming
Example Programs
Specification
Write a Miranda program that :
I takes as input a representation of a simple arithmetic expression using the grammar given on the next page, and
I returns as output the value of that expression
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 10 / 57

COMP0020: Functional Programming
Example Programs
Grammar (BNF)
expression : : constant | expression op expression | ’(’ expression ’)’ op : : ’*’ | ’+’ | ’-’ | ’/’
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 11 / 57

COMP0020: Functional Programming
Example Programs
Preliminaries
Note that the specification asks for a “representation” of the expression to be input Therefore, we can ignore lexical analysis
We will also assume that parsing has been done, so we have the syntax tree
We can choose an algebraic type as our representation of that syntax tree, with appropriate constructors
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 12 / 57

COMP0020: Functional Programming
Example Programs
Algebraic types
expression ::=Constant num
| App expression operator expression
| Bracketed expression operator ::= Times | Plus | Minus | Divide
Compare with the BNF :
expression : : constant | expression op expression | ’(’ expression ’)’ op : : ’*’ | ’+’ | ’-’ | ’/’
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 13 / 57

COMP0020: Functional Programming
Example Programs
Test values
||(4) ú 5
test1 = App (Bracketed (Constant 4)) Times (Constant 5)
||(4 + 5)ú(3≠2) test2 = App
(Bracketed (App (Constant 4) Plus (Constant 5))) Times
(Bracketed (App (Constant 3) Minus (Constant 2)))
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 14 / 57

COMP0020: Functional Programming
Example Programs
Evaluator code
eval :: expression ≠ > num
eval (Constant x) eval (App e1 op e2) eval (Bracketed e)
= x
= evalop op (eval e1) (eval e2) = eval e
evalop:: operator ≠>num≠>num≠> num
evalopTimesxy evalop Plus x y evalopMinusxy evalopDividexy
= x ú y = x + y = x ≠ y = x/y
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 15 / 57

COMP0020: Functional Programming
Example Programs
Programming Example 2
Lists as functions Motivation :
I Better understanding of, and facility with, higher order functions and currying
I Example of how data can be implemented as a function (a “trick” — sometimes useful)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 16 / 57

COMP0020: Functional Programming
Example Programs
Preamble (1)
Recall CURRIED functions :
I fabc=(a+b)
I 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 2018-2019 17 / 57

COMP0020: Functional Programming
Example Programs
Preamble (2)
Recall HIGHER ORDER functions :
I fabc=c(ab)
I c must be a function (of at least one argument) I a must be a function (of at least one argument) I e.g. f (*2) 4 (+1)
= (+1) ((*2) 4) = 1 + (2 * 4)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 18 / 57

COMP0020: Functional Programming
Example Programs
Preamble (3)
Recall HIGHER ORDER functions can return functions :
I gab=(+a) main = g 3 4 5
I Too many args ? I No!
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 19 / 57

COMP0020: Functional Programming
Example Programs
Example 2 : Lists as Functions
We have already seen how the list (1 : (2 : (3 : []))) can be represented as
I Cons 1 (Cons 2 (Cons 3 Nil))
I Where Cons and Nil are constructors of an algebraic type
I The dierence being that this data structure is now of type mylist num and not of type [num] I This assumes the algebraic type definition :
mylist * : := Nil | Cons * (mylist *)
Now we consider a new representation :
I cons 1 (cons 2 (cons 3 nil))
I where cons and nil are functions ! (as follows 🙂
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 20 / 57

COMP0020: Functional Programming
Example Programs
Example 2 : Lists as Functions
The list (1 : (2 : (3 : []))) can be represented as
I cons 1 (cons 2 (cons 3 nil))
I where cons and nil are functions as follows :
consabf = f abFalse
nil f = f (error “head of nil”) (error “tail of nil”) True
x = cons ’A’ nil
y = nil is a partial application !
is a partial application !
Both cons and nil are partially applied — the final argument is only supplied when an element is selected or we test for nil
To see how it works, consider the definitions of head, tail and isnil
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 21 / 57

COMP0020: Functional Programming
Example Programs
consabf =f nil f= f
headx = xh where
head tail isnil
¿¿¿
tail x isnil x
habc=a = xt
where
tabc=b = xg
where gabc=c
|| Example :
|| z=cons
|| y=cons ||
|| head y
|| æ (cons
|| æ cons
|| æhÕBÕ
|| æ ÕBÕ
a b (error ”head of nil”) (error
”tail of nil”)
False True
ÕAÕ nil ÕBÕ z
ÕBÕ z) h ÕBÕ z h z False
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 22 / 57

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 2018-2019 23 / 57

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 2018-2019 24 / 57

COMP0020: Functional Programming
Example Programs
Summary
Summary
Programming examples
an arithmetic expression evaluator (simple) lists as functions (needs thought !)
1 2
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 25 / 57

COMP0020: Functional Programming
Example Programs
Summary
END OF LECTURE
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 26 / 57