Suggested Homework #3

Problem 1: Suppose that the following list of bindings was entered into the OCaml interpreter in the sequence shown. For each binding, write down :
(a) If the expression is accepted, the value bound ("fun" for functions) and its type,
(b) If the expression is rejected due to a type error, "type error",
(c) If the expression is rejected due to an unbound variable, the name of the variable that is not bound. Recall that if a type error occurs, then the variable binding does not happen. Check your answers by entering this sequence into the interpreter.


- let foo (f,g) = fun x -> (f x,g x);;

- let a = (foo ( (fun x -> x*x), (fun x -> [x]) )) 4;;

- let b = (foo ( (fun x -> -x), (fun x -> 0::x) )) (4,[4]);;

- let bar (f,a) = fun b -> f (a,b);;

- let sum (a,b) = a+b;;

- let c = (bar (sum,1));;

- let d = c 2;;

- let f = (bar (bar,bar)) sum;;

- let g = f 4;;

- let h = g 4;;

- let i = h 4;;

- let j = i 4;;

Problem 2: In each part below you are required to complete the implementation of a function by filling in the appropriate expressions in the blanks (parts marked ... ).

(a) mapFns : ('a -> 'b) list * 'a list -> 'b list, a function that takes a list of functions and a list of arguments and applies each function to its respective argument and returns the result.
mapFns ([fun x -> -x;fun x -> x+2;fun x -> x*x],[7;8;9]) evaluates to [-7;10;81].
```
  let rec mapFns (fs,xs) =
  match (fs,xs) with 
    ([],_) -> ...
  | (_,[]) -> ...
  | (f::fs,x::xs) -> ...
```
(b) compose : ('a -> 'b) * ('c -> 'a) -> ('c -> 'b), a function that takes two functions, f(x) and g(x), and returns their composition, f(g(x)) (compose (fun x -> ~x,fun x -> x+3)) 8 evaluates to ~11..
```
  let 
compose (f,g) = ... ;;  
```
(c) iterate : ('a -> 'a) * int -> 'a -> 'a takes a function f(x) and an integer n and returns f(f(f(f ... f(x)))) where f is composed with itself n times.
(iterate (fun x -> x + 1) 5) 6 evaluates to 11 and
(iterate (fun x -> []::x) 3) [[1]; [2]] evaluates to [[]; []; []; [1]; [2]]
```
  let rec iterate (f,n) =
  match n with
     0 -> ...
  | _ -> compose ((...),(...))
  ;;
```