The goal of this mini-project is to program with strings in OCaml.
Implement an OCaml function of type string -> string -> string that concatenates two strings, using String.init.
Hints:
This question is a warmup the two subsequent questions.
Implement an OCaml function that given 3 characters, yields a string containing these 3 characters. This implementation should pass the following unit test:
let test_warmup candidate =
(candidate 'a' 'b' 'c' = "abc");;
For starters, let us define an auxiliary function of type char -> string that, given a character, yields a singleton string that contains this character:
let string_of_char c =
String.make 1 c;;
The answer to the question is then straightforward:
let warmup c0 c1 c2 =
string_of_char c0 ^ string_of_char c1 ^ string_of_char c2;;
In words: each of the 3 given characters is mapped into a singleton string, and the 3 resulting singleton strings are concatenated.
Alternatively, one could use String.init:
let warmup_alt c0 c1 c2 =
String.init
3
(fun i ->
if i = 0
then c0
else (if i = 1
then c1
else c2));;
In words: given 3 and a function f of type int -> char, String.init applies f to 0, 1, and 2, which yield 3 characters. These 3 characters compose the resulting string.
As described in the section about Mapping a character-to-character function pointwise over a string, in Week 06, the library function String.map takes two arguments: a given function mapping a character to a character, and a given string. It applies the given function to each character of the given string and returns a string where each character is the result of applying the given function to the corresponding character in the given string.
Obviously, String.map is implemented with a for-loop: for each of the characters of the given string, the given function is applied.
Yal’-N-U-S,In the middle of the termstring_map_downIntro C-S in germGot a disk, a pad, berries in our bagAin’t gonna cut O-Caml no slack
This question is optional.
As described in the subsequent General interlude, still in Week 06, the library function String.mapi takes two arguments: a given function mapping an integer and character to a character, and a given string. It applies the given function to each character of the given string and its index in this string and returns a string where each character is the result of applying the given function to the corresponding index and the corresponding character in the given string.
Obviously, String.mapi is implemented with a for-loop: for each of the characters of the given string, the given function is applied to the current index of the for-loop and to the character at that index.
Implement two OCaml functions of type string -> string that reverse a string,
For example, these functions should map "abc" to "cba" and vice versa.
More generally, using
the following expression should evaluate to true:
let c0 = random_char ()
and c1 = random_char ()
and c2 = random_char ()
in string_reverse (warmup c0 c1 c2) = warmup c2 c1 c0
where string_reverse denotes a function that reverses a string.
Subsidiary question: can you express your recursive string-reversing function using nat_fold_right? If yes, do it, and if no say why.
For the purpose of this question, the reverse function of Question 05 is referred to as string_reverse.
For any strings denoted by s1 and s2, what is the relation between string_reverse s1, string_reverse s2, and s1 ^ s2?
Implement a unit-test function for string_reverse that puts this relation to the test.
A palindrome is a string such that enumerating its characters from left to right and from right to left give the same enumeration. So for example, “aba” and “abba” are palindromes, but “abc” isn’t.
Implement a generator of palindromes of type int -> string, i.e., an OCaml function that maps a non-negative integer n to a palindrome of length n. There is no need for unit tests here, your implementation can just be illustrated with a couple of examples, basically. Each of these examples, however, should be motivated.
Harald: Just?Alfrothul: Basically.Halcyon: Harrumph.
A palindrome detector is a function of type string -> bool, i.e., a predicate, such that applying it to a palindrome yields true whereas applying it to a string that is not a palindrome yields false.
It is a good idea to implement a simple palindrome detector that compares any given string with its reverse, to test your unit-test function. However, your recursive implementation should not first reverse the given string: it should operate in one pass over the given string.
Subsidiary question: can you express your recursive palindrome detector using nat_fold_right? If yes, do it, and if no say why.
Implement a function string_andmap that has type (char -> bool) -> string -> bool and that, given a predicate and a string, applies this predicate to each character of the string and returns the conjunction of the results. Your implementation should pass the following unit test:
let digitp c =
'0' <= c && c <= '9';;
let test_string_andmap candidate =
(candidate digitp "" = true) &&
(candidate digitp "123" = true) &&
(candidate digitp "abc" = false) &&
(candidate digitp "123abc" = false);;
Implement a function string_ormap that has type (char -> bool) -> string -> bool and that, given a predicate and a string, applies this predicate to each character of the string and returns the disjunction of the results. Your implementation should pass the following unit test:
let test_string_ormap candidate =
(candidate digitp "" = false) &&
(candidate digitp "123" = true) &&
(candidate digitp "abc" = false) &&
(candidate digitp "123abc" = true);;
What is the logic of making string_andmap return true when applied to the empty string, and of making string_ormap return false when applied to the empty string?
This question is optional.
Implement a function string_concatmap that has type (char -> string) -> string -> string and that, given a function and a string, applies this function to each character of the string and returns the concatenation of the results. Your implementation should pass the following unit test:
let test_string_concatmap candidate =
(candidate (fun c -> String.make 2 c) "abc" = "aabbcc");;
Remember show_string, the unparsing function for strings in Week 05? Implement it properly, i.e., so that it properly unparses strings that contain \ and " .
Goal of the game:
# Printf.printf "%s\n" (show_string "");;
""
- : unit = ()
# Printf.printf "%s\n" (show_string "abc");;
"abc"
- : unit = ()
# Printf.printf "%s\n" (show_string "ab\\cd");;
"ab\\cd"
- : unit = ()
# Printf.printf "%s\n" (show_string "\"");;
"\""
- : unit = ()
#
Created [27 Feb 2022]