Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
This homework document consists of 3 pages. Carefully read the entire document before you start coding.
Note: All functions, unless otherwise specified, should be polymorphic (i.e., they should work with any
data type). For example, if you are writing a method that should work for lists, the type must be 'a list,
and not int list.
1 Recursion and Higher-order Functions (60 points)
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 x (6) n
. 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 list. (6)
# 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 (6)
a predicate, and removes all the elements that satisfy the condition expressed in the predicate.
# 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- (6)
titions a list into equivalence classes according to the equivalence function.
# 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 (6)
j, to return the sublist from index i (inclusive) and j (not inclusive). We want such a slicing function
in OCaml as well.
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 i
th (inclusive) to the j
th (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- (6)
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