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.
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.
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"]
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]
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]]
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"];
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
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
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"]
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
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]];
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of