Lab
Final review
Higher order function
• The type (‘a->’b) -> ‘c is equivalent to the type ‘a -> ‘b -> ‘c. (T/F)
Can we do partial application to the two types above?
For (‘a-> ‘b) -> ‘c , No, it only takes one argument
For ‘a -> ‘b -> ‘c, Yes, it takes `a and output a new function with type `b -> `c
2. Give the function definitions below
let rec foldl(f:’a*’b->’b)(acc: ‘b)(l:’a list):’b =
match l with
| [] -> acc
| x::xs -> foldl f (f(x,acc)) xs
let rec foldr (f:’a*’b->’b)(acc: ‘b)(l:’a list):’b =
match l with
| [] -> acc
| x::xs -> f(x, (foldr f acc xs))
foldl (fun (a,c) -> if a=0 then [a] else a::c) [] [3;0;2;1];;
foldr (fun (a,c) -> if a=0 then a::c else c) [] [1;2;0;3];;
A: They have different type
B: They evaluate to the same value
C: They are the same expression
D: They have both type int list -> int
E: A, B, C and D are all false
A. Type is decided during the definition,
B. first evaluate to [1;2;0], second evaluate to [0]. It’s good to walk through
3. let mystery1 d = foldr (fun (b, c) ->
if b = []
then c
else b::c) [] d
let rec mystery2 d =
match d with
| _ -> []
| (x::xs) ->
if x = []
then (mystery2 xs)
else (x::(mystery2 xs))
What is the type of mystery1?
mystery1 : ‘a list list -> ‘a list list
b=[] indicates b: ‘a list
b::c indicates c: `a list list
from definition of foldr, c is the return type of foldr
d has the type of : type(b) list , so d : `a list list
thus the answer
What is the type of mystery2?
mystery2 : ‘a list list -> ‘a list list
x=[] indicates x is ‘a list
match d with indicates d is `a list list
x::(mystery2 xs) indicates x could cons to the return of mystery2 xs,
then the return of mystery2 xs is ‘a list list
Are mystery1 and mystery2 equivalent where by equivalent we mean if provided with the same input they produce the same output? Please, explain.
Not equivalent.
mystery1 [[1]]= [[1]]
while
mystery2 [[1]]= []
due to mystery2 match the wildcard first
Consider the following two OCaml functions:
let rec mystery1 d = foldl (fun((a,b), c) ->
if a < b
then (a+b)::c
else b::c) [] d
let rec mystery2 d =
match d with
|(y,z)::xs ->
if y < z
then y+z+(mystery2 xs)
else z+(mystery2 xs)
| [] -> 0
What is the type of mystery1?
mystery1 : (int * int) list -> int list
(a+b)::c indicates a and b are int and c is int list
from definition of foldl, know type of (a,b) list is the type of d
What is the type of mystery2?
mystery2 : (int * int) list -> int
y
[4 Marks] Are mystery1 and mystery2 equivalent? (two functions are equivalent if and only when provided with the same input they produce the same output, or they both loop forever) Please, explain.
[Hint: think about what the OCaml interpreter would do when you give to mystery1 and mystery2 the same input]
Not equivalent. They have different types. Specifically, when provided with the same input they will produce two different outputs.
Type inference
type value = R of float | I of int | S of string | L of value list
let rec printer (arg,acc) =
match arg with
| S s ->acc
| L x ->(match x with
| (x::xs) -> printer (x,xs)
| _ -> [] )
|_ ->[arg]
A: ‘a list -> value list -> value list
B: value -> value list -> value list
C: value list -> ‘a list -> value list
D: value * value list -> value list
E: value * ‘a list -> ‘a list
Two ways to see that
• the comma (,) indicates tuple
• acc is the same type as [arg], as arg is value, so acc is value list
• another way to see is x is value, xs is value list and it passes to printer again at the acc position.
type value = R of float | I of int | S of string
let rec interpret mix l1 l2 =
match mix with
| [] -> (l1, l2)
| x::xs ->
match x with
| R(y) -> interpret xs (y::l1) l2
| _ -> interpret xs l1 (x::l2)
A: value list -> float list -> value list -> Value list * float list
B: value list -> value list -> float list -> Value list * float list
C: value list -> float list -> value list -> float list * value list
D: (value list * value list * float list) -> float list * value list
E: (value list * value list * float list) -> float list -> value list
F: value list -> value list -> float list -> float list -> value list
y::l1 indicates l1:float list
from match x with | R(y) , knows x:value
x::l2 indicates l2:value list
match mix with | x::xs indicates mix is value list
Grammar
A: ambiguous, left and right recursive
B: unambiguous, right recursive
C: unambiguous, left recursive
D: unambiguous, left and right recursive
E: A, B, C and D are all false
A: ambiguous, left recursive
B: ambiguous, left and right recursive
C: unambiguous, left recursive
D: unambiguous, left and right recursive
E: A, B, C and D are all false
Consider the following grammar:
Show the grammar is ambiguous (hint: parse trees):
0 = 0 = 0 have two parse trees
Rewrite the grammar to give precedence to < over = maintaining it ambiguous (you may need to introduce new non terminals):
Rewrite the grammar to give precedence to < over = and to be unambiguous: