CS314 Spring 2020
Assignment 6
1 OCaml Basics
(1) Write an OCaml function maxAbsoluteVal : int list → int that takes an
integer list l and returns the maximum absolute value of l.
Examples:
# maxAbsoluteVal [ ] ;;
- : int = 0
# maxAbsoluteVal [1;2;3;-4];;
- : int = 4
(2) Write an OCaml function getnthdigit : int→ int that gets the n-th digit
of an integer.
Examples:
# getnthdigit 12345 1;;
- : 1
# getnthdigit 31145 5;;
- : 5
(3) Implement prefix sum in OCaml, psum : int list → int list. The prefix
sum algorithm takes a sequence of numbers x0, x1, x2, ... as input and
returns a sequence of numbers y0, y1, y2, ... such that y0 = x0, y1 =
x0 + x1, y2 = x0 + x1 + x2 and so on.
Examples:
# psum [1; 2; 0; -7] ;;
- : int list = [1; 3; 3; -4] ;;
# psum [0; 1; 2; 3] ;;
- : int list = [0; 1; 3; 6]
# psum [ ] ;;
- : ’a list = [ ]
1
Note: You are not allowed to use OCaml’s imperative features. You
can use the programming constructs we have discussed in class until
lecture 17.
2 Lambda Calculus Review
(1) Let’s assume the S and K combinators:
• K ≡ λxy.x
• S ≡ λxyz.((xz)(yz))
Prove that the identify function I ≡ λx.x is equivalent to ((S K) K),
i.e.,
I ≡ SKK
(2) Use α/β-reductions to compute the final answer for the following λ-
terms. Your computation ends with a final result if no more reductions
can be applied.
(a) (λ x.x) (λ z.z) (λ y.11)
(b) (λ x.((λ z.(λ x. z x) 3) λ y.+ x y)) 5
(c) (λ z. ((λ y.z) ((λ x.x x)(λ x.x x)))) 25
2