1  Recursion and Higher-order Functions    

In this section, you may not use any functions available in the OCaml library that already solves all or most of the question. For example, OCaml provides a List.rev function, but you may not use that in this section.

1. Write a recursive function pow, which takes two integer parameters x and n, and returns xn. Also write a function float pow, which does the same thing, but for x being a float (n is still an integer). You may assume that n will always be non-negative.

2. Write a function compress to remove consecutive duplicates from a

# compress ["a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e"];;

- : string list = ["a"; "b"; "c"; "a"; "d"; "e"]

3. Write a function remove if of the type 'a list -> ('a -> bool) -> 'a  list, which takes a list and    a predicate, and removes all the elements that satisfy the condition expressed in the

# remove_if [1;2;3;4;5] (fun x -> x mod 2 = 1);;

- : int list = [2; 4]

4. Write a function equivs of the type ('a -> 'a -> bool) -> 'a list ->  'a  list list, which par-  titions a list into equivalence classes according to the equivalence

# equivs (=) [1;2;3;4];;

- : int list list = [[1];[2];[3];[4]]

# equivs (fun x y -> (=) (x mod 2) (y mod 2)) [1; 2; 3; 4; 5; 6; 7; 8];;

- : int list list = [[1; 3; 5; 7]; [2; 4; 6; 8]]

5. Some programming languages (like Python) allow us to quickly slice a list based on two integers i and j, to return the sublist from index i (inclusive) and j (not inclusive). We want such a slicing function in OCaml as

Write  a  function  slice  as  follows:  given  a  list  and  two  indices,  i  and  j,  extract  the  slice  of  the  list containing the elements from the ith (inclusive) to the jth (not inclusive) positions in the original list.

# slice ["a";"b";"c";"d";"e";"f";"g";"h"] 2 6;;

- : string list = ["c"; "d"; "e"; "f"]

Invalid index arguments should be handled gracefully. For example,

# slice ["a";"b";"c";"d";"e";"f";"g";"h"] 3 2;;

- : string list = []

# slice ["a";"b";"c";"d";"e";"f";"g";"h"] 3 20;

- : string list = ["d";"e";"f";"g";"h"];

6. Write a function called composition, which takes two functions as its input, and returns their compo- sition as the output.

 

# let square_of_increment = composition square increment;; val square_of_increment : int -> int = <fun>

# square_of_increment 4;; (* increments 4 to 5, and THEN computes square *)

- : int = 25

7. Write a function called equiv on, which takes three inputs: two functions f and g, and a list lst. It returns true if and only if the functions f and g have identical behavior on every element of lst.

#  let f i =  i *  i;;

val f : int -> int = <fun> # let g i = 3 * i;;

val g : int -> int = <fun> # equiv_on f g [3];;

• : bool = true

# equiv_on f g [1;2;3];;

• : bool = false

  8. Write a functions called pairwisefilter with two parameters: (i) a function cmp that compares two elements of a specific T and returns one of them, and (ii) a list lst of elements of that same type T. It returns a list that applies cmp while taking two items at a time from lst. If lst has odd size, the last element is returned “as is”.

# pairwisefilter min [14; 11; 20; 25; 10; 11];;

- : int list = [11; 20; 10]

# (* assuming that shorter : string * string -> string = <fun> already exists *)

# pairwisefilter shorter ["and"; "this"; "makes"; "shorter"; "strings"; "always"; "win"];;

- : string list = ["and"; "makes"; "always"; "win"]

9. Write the polynomial function, which takes a list of tuples and returns the polynomial function corre- sponding to that Each tuple in the input list consists of (i) the coefficient, and (ii) the exponent.

# (* below is the polynomial function f(x) = 3x^3 - 2x + 5 *) # let f = polynomial [3, 3;; -2, 1; 5, 0];;

val f : int -> int = <fun>  # f 2;;

- : int = 25

10. The power set of a set S is the set of all subsets of S (including the empty set and the entire set). Write a function powerset of the type 'a list -> 'a list list, which treats lists as unordered sets, and returns the powerset of its input You may assume that the input list has no duplicates.

# powerset [3; 4; 10];;

- : int list list = [[]; [3]; [4]; [10]; [3; 4]; [3; 10]; [4; 10]; [3; 4; 10]];