4 Problems
• For problems 1 through 9 and 12 through 16, you may not use library functions or @.
• In problems 10 and 11, you may not use recursion, and instead must use the library functions specified.
• In problems 1 through 3 you must use forward recursion.
• In problems 4 through 6 you must use tail recursion.
• Problems 12 through 16 must be in continuation passing style.
Note: All library functions are off limits for all problems on this assignment, except those that are specifically required
(in problems 10 and 11.) For purposes of this assignment @ is treated as a library function and is not to be used..
4.1 Patterns of Recursion
For problems 1 through 6, you may not use library functions.
1. (3 pts) Write a function remove all : int list -> int -> int list such that remove all list
m returns a list in the same order as the input list, but with all the numbers equal to m removed. The function is
required to use (only) forward recursion (no other form of recursion). You may not use any library functions.
# let rec remove_all list m = … ;;
val remove_all : ’a list -> ’a -> ’a list =
# remove_all [2; 4; 3; 7; 2; 8; 2] 2;;
– : int list = [4; 3; 7; 8]
2. (5 pts) Write a function all from to : int -> int -> (int -> bool) -> int such that
all from to m n p tells the number of integers greater than or equal to m and also less than or equal to n
which satisfy a given predicate p : int -> bool. The function is required to use (only) forward recursion
(no other form of recursion). You may not use any library functions.
# let rec all_from_to m n p = … ;;
val all_from_to : int -> int -> (int -> bool) -> int =
# all_from_to (-5) 7 ((<) 0);; - : int = 7 # all_from_to 3 7 (fun x -> x mod 2 = 0);;
– : int = 2
3. (5 pts) Write a function separate : (’a -> bool) -> ’a list -> int * int such that
separate p l returns a pair of integers, the first indicates the number of elements of l for which p returns
true, and the second indicates the number of elements for which p returns false. The function is required to use
(only) forward recursion (no other form of recursion). You may not use any library functions.
# let rec separate p l = … ;;
val separate : (’a -> bool) -> ’a list -> int * int =
# separate (fun x -> x mod 2 = 0) [-3; 5; 2; -6];;
– : int * int = (2, 2)
2
wenwen xu
wenwen xu
4. (5 pts) Write a function all even : int list -> bool that returns whether every element in the input
list is even. The function is required to use (only) tail recursion (no other form of recursion). You may use mod
for testing whether an integer is even. You may not use any library functions.
# let rec all_even list = … ;;
val all_even : int list -> bool =
# all_even [4; 2; 12; 5; 6];;
– : bool = false
5. (6 pts) Write a function sum square : int -> int -> int such that sum square m n calculates
the sum of the squares of the elements strictly greater than m and strictly less than n if there are any, and 0
otherwise. The function is required to use (only) tail recursion (no other form of recursion). You may not use any
library functions.
# let rec sum_square m n = … ;;
val sum_square : int -> int -> int =
# sum_square 3 9;;
– : int = 190
6. (8 pts) Write a function concat : string -> string list -> string such that concat s l
creates a string consisting of the strings in the list l concatenated together, with a single space inserted between
consecutive elements. Also all strings equal to s should be excluded. The function is required to use (only) tail
recursion (no other form of recursion). You may not use any library functions.
# let rec concat s list = … ;;
val concat : string -> string list -> string =
# concat “hi” [“How”; “are”; “hi”; “you?”];;
– : string = “How are you?”
Stop: go back and make sure you used no library functions for problems 1 through 6.
4.2 Higher-Order Functions
For problems 7 through 9, you will be supplying arguments to the higher-order functions List.fold right and
List.fold left. You should not need to use explicit recursion for any of 7 through 11.
7. (7 pts) Write a value remove all base and function remove all rec : int -> int -> int
list -> int list such that (fun list -> List.fold right (remove all rec m) list
remove all base) computes the same results as remove all of Problem 1. There should be no use of
recursion or library functions in defining remove all rec.
# let remove_all_base = … ;;
val remove_all_base : …
# let remove_all_rec m n r = … ;;
val remove_all_rec : ’a -> ’a -> ’a list -> ’a list =
# (fun list -> List.fold_right (remove_all_rec 2) list remove_all_base)
[2; 4; 3; 7; 2; 8; 2];;
– : int list = [4; 3; 7; 8]
3
8. (7 pts) Write a value separate base and function separate rec : (’a -> bool) -> ’a -> int
* int -> int * int such that (fun p -> fun list -> List.fold right (separate rec
p) list separate base) computes the same results as separate of Problem 3. There should be no
use of recursion or library functions in defining separate rec.
# let separate_base = …
val separate_base : …
# let separate_rec p x (tl, fl) = …
val separate_rec : (’a -> bool) -> ’a -> int * int -> int * int =
# (fun p -> fun list -> List.fold_right (separate_rec p) list separate_base)
(fun x -> x mod 2 = 0)
[-3; 5; 2; -6];;
– : int * int = (2, 2)
9. (7 pts) Write a value all even base and function all even rec : bool -> int -> bool such that
List.fold left all even rec all even base computes the same results as all even of Problem
4. You may use mod for testing whether an integer is even. There should be no use of recursion or other library
functions in defining all even rec.
# let all_even_base = …
# let all_even_rec r x = … ;;
val all_even_rec : bool -> int -> bool =
# List.fold_left all_even_rec all_even_base [4; 2; 12; 5; 6];;
– : bool = false
10. (7 pts) Write a function concat2 : string -> string list -> string that computes the same
results as concat of Problem 6. The definition of concat2 may use List.fold left : (’a -> ’b
-> ’a) -> ’a -> ’b list -> ’a but no direct use of recursion, and no other library functions.
# let concat2 i list = …;;
val concat2 : string -> string list -> string =
# concat2 “hi” [“How”; “are”; “hi”; “you?”];;
– : string = “How are you?”
11. (8 pts) Write a function app all : (’a -> ’b) list -> ’a list -> ’b list list that takes
a list of functions, and a list of arguments for those functions, and returns the list of list of results from consecutively
applying the functions to all arguments, in the order in which the functions occur in the list and in the order in
which the arguments occur in the list. Each list in the result list corresponds to a list of applications of each function
to the given arguments. The definition of app all may use the library function List.map : (’a -> ’b)
-> ’a list -> ’b list but no direct use of recursion, and no other library functions.
# let app_all fs list = … ;;
val app_all : (’a -> ’b) list -> ’a list -> ’b list list =
# app_all [(fun x -> x > 0); (fun y -> y mod 2 = 0);
(fun x -> x * x = x)] [1; 3; 6];;
– : bool list list =
[[true; true; true]; [false; false; true]; [true; false; false]]
4
wenwen xu