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
