Mini-project: Palindromes, string concatenation, and string reversal¶

The goal of this mini-project is to program with strings in OCaml.

Resources¶

The OCaml code for the present mini-project (latest version: 01 Oct 2022).

Question 01¶

Implement an OCaml function of type string -> string -> string that concatenates two strings, using String.init (and not using (^)).

Hints:

Check out String.init in the index.
Revisit Exercise 21 in Week 04.
Peruse the answer to Question 02 just below.

Question 02¶

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");;

Answer to Question 02¶

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.

Question 03¶

As described in the section about Mapping a character-to-character function pointwise over a string, in Week 05, 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.

In which order are the characters accessed in the given string? (Hint: use the tracing identity function over characters in the mini project about the underlying determinism of OCaml.)
Using a recursive function that operates over a natural number, implement a left-to-right version of String.map. Does applying your recursive function to an increasing index do the job?
Using a recursive function that operates over a natural number, implement a right-to-left version of String.map. Does applying your recursive function to a decreasing index do the job?

Food for thought:

Earlier in the lecture notes, String.map was characterized as follows:

Given a function f and, e.g., a string "abc", i.e., the result of evaluating:
string_of_char 'a' ^ string_of_char 'b' ^ string_of_char 'c'
String.map essentially yields the result of evaluating:
string_of_char (f 'a') ^ string_of_char (f 'b') ^ string_of_char (f 'c')
where string_of_char maps a character into a singleton string containing this character

How does this characterization mesh with

your answer to Question 03.a in this mini-project and
your answer to Question 02 in the mini-project about the underlying determinism of OCaml?

Yal’-N-U-S,

In the middle of the term

string_map_down

Intro C-S in germ

Got a disk, a pad, berries in our bag

Ain’t gonna cut O-Caml no slack

—pastiche of Six Strings Down

Question 04¶

As described in the subsequent General interlude, still in Week 05, 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.

In which order are the characters accessed in the given string?
Using a recursive function that operates over a natural number, implement a left-to-right version of String.mapi. Does applying your recursive function to an increasing index do the job?
Using a recursive function that operates over a natural number, implement a right-to-left version of String.mapi. Does applying your recursive function to a decreasing index do the job?

Food for thought:

Earlier on, String.mapi was characterized as follows:

Given a function f and, e.g., a string "abc", i.e., the result of evaluating:
string_of_char 'a' ^ string_of_char 'b' ^ string_of_char 'c'
String.mapi essentially yields the result of evaluating:
string_of_char (f 0 'a') ^ string_of_char (f 1 'b') ^ string_of_char (f 2 'c')
where string_of_char maps a character into a singleton string containing this character.

How does this characterization mesh with

your answer to Question 04.a in this mini-project and
your answer to Question 02 in the mini-project about the underlying determinism of OCaml?

Question 05¶

Implement two OCaml functions of type string -> string that reverse a string,

one that uses String.mapi, and
another that uses recursion over a non-negative integer.

For example, these functions should map "abc" to "cba" and vice versa.

More generally, using

the warmup function from Question 02 and
the random_char function from the chapter about unit tests, revisited in Week 04 (and from the chapter about strings in Week 05) that generates a random character,

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 or nat_parafold_right? If yes, do it, and if no say why.

Question 06¶

For the purpose of this question, the concatenation function of Question 01 is referred to as string_append and 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 string_append s1 s2?

Implement a unit-test function for string_reverse and string_append that puts this relation to the test.

Palindromes¶

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” and “xyzzy” aren’t.

Anton: Xyzzy, eh?

Alfrothul: Right. Like something is going to happen.

Anton: Well, let’s keep going.

Question 07¶

Implement a generator of non-trivial palindromes of type int -> string, i.e., an OCaml function that maps a non-negative integer n to a non-trivial palindrome of length n. There is no need for unit tests here, your implementation can simply be illustrated with a couple of examples. Each of these examples, however, should be motivated.

Interlude¶

Pablito: What is a generator of non-trivial palindromes?

Bong-sun: Let’s see. Can we think of a generator of trivial palindromes?

Pablito: Gotcha:

let random_lowercase_letter () =
  char_of_int (int_of_char 'a' + Random.int 26);;

let make_palindrome n =
  let () = assert (n >= 0) in
  String.make n (random_lowercase_letter ());;

Bong-sun: Yup. A string that repeats the same character is a trivial palindrome.

Pablito: Phew, my generator is not trivial.

Bong-sun: How does it work?

Pablito: It simply uses random_string, string_reverse, and string_append. What about yours?

Bong-sun: It follows the inductive specification of palindromes, and so it is structurally recursive.

Pablito: Ah. On another note, did you see Dana’s palindrome generator?

Bong-sun: I didn’t. What about it?

Pablito: It doesn’t concatenate strings.

Bong-sun: Wait. Oh. You mean it only uses String.init?

Pablito: Yes.

Bong-sun: Ha! Let’s see. It’s got to involve an even function. Let me think about that.

Question 08¶

A palindrome detector is a function of type string -> bool, i.e., a predicate: applying it to a palindrome yields true whereas applying it to a string that is not a palindrome yields false.

Implement a palindrome detector using recursion over a non-negative integer.

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.

Recommendation: use the following traced comparison function to visualize how your palindrome detector is proceeding:

let traced_compare_char c1 c2 =
  let () = Printf.printf "comparing '%c' and '%c'...\n" c1 c2 in
  c1 = c2;;

Subsidiary question: can you express your recursive palindrome detector using nat_fold_right or nat_parafold_right? If yes, do it, and if no, say why.

Question 09¶

This question is not optional.

Implement an OCaml function that reverses a palindrome.

Question 10¶

Implement String.map using String.mapi.

Question 11¶

Implement String.mapi using String.init.

Question 12¶

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?

Food for thought:

Could one implement a palindrome detector as an instance of string_andmap? If yes, implement it. If no, say why.
Assuming that one can implement a palindrome detector as an instance of string_andmap, what does one obtain if one replaces string_andmap with string_ormapi in this implementation?

Question 13¶

Implement a function string_andmapi that is to string_andmap what string_mapi is to string_map.
Implement a function string_ormapi that is to string_ormap what string_mapi is to string_map.

Food for thought:

Could one implement a palindrome detector as an instance of string_andmapi? If yes, implement it. If no, say why.
Assuming that one can implement a palindrome detector as an instance of string_andmapi, what does one obtain if one replaces string_andmapi with string_ormapi in this implementation?

Question 14¶

Implement a function check_string_append that has type string -> string -> string -> bool and that, given three strings, checks whether the third is the concatenation of the first and the second. Start by implementing a concise but telling unit-test function.

(Hint: use string_andmapi.)

Question 15¶

Implement a function check_string_map that has type (char -> char) -> string -> string -> bool and that, given a function and two strings, checks whether the second string is the result of applying String.map to the function and the first string. Start by implementing a concise but telling unit-test function.

(Hint: use string_andmapi.)

Question 16¶

Implement a function check_string_mapi that has type (int -> char -> char) -> string -> string -> bool and that, given a function and two strings, checks whether the second string is the result of applying String.mapi to the function and the first string. Start by implementing a concise but telling unit-test function.

(Hint: use string_andmapi.)

Question 17¶

Implement a function check_string_reverse that has type string -> string -> bool and that, given two strings, checks whether the second is the result of reversing the first. Start by implementing a concise but telling unit-test function.

(Hint: use string_andmapi.)

Question 18¶

Implement a function string_appendmap 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_appendmap 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 = ()
#

Question 19¶

Implement a function string_appendmapi that is to string_appendmap what string_mapi is to string_map.

Question 20¶

Implement string_map as an instance of string_appendmap.
Implement string_mapi as an instance of string_appendmapi.

Resources¶

The OCaml code for the present mini-project (latest version: 01 Oct 2022).

Version¶

In the light of the live-coding session in class (10 Mar 2023), rephrased Question 03 and Question 04 and added some food for thought. [11 Mar 2023]

Added a recommendation in Question 08 [11 Mar 2023]

Simplified Question 08 and added some food for thought in Question 12 and Question 13 [11 Mar 2023]

Added the interlude after Question 07 [11 Mar 2023]

Created [10 Jan 2023]

Mini-project: Palindromes, string concatenation, and string reversal¶

Resources¶

Question 01¶

Question 02¶

Answer to Question 02¶

Question 03¶

Question 04¶

Question 05¶

Question 06¶

Palindromes¶

Question 07¶

Interlude¶

Question 08¶

Question 09¶

Question 10¶

Question 11¶

Question 12¶

Question 13¶

Question 14¶

Question 15¶

Question 16¶

Question 17¶

Question 18¶

Question 19¶

Question 20¶

Resources¶

Version¶

Table Of Contents

Previous topic

Next topic

Navigation

Mini-project: Palindromes, string concatenation, and string reversal¶

Resources¶

Question 01¶

Question 02¶

Answer to Question 02¶

Question 03¶

Question 04¶

Question 05¶

Question 06¶

Palindromes¶

Question 07¶

Interlude¶

Question 08¶

Question 09¶

Question 10¶

Question 11¶

Question 12¶

Question 13¶

Question 14¶

Question 15¶

Question 16¶

Question 17¶

Question 18¶

Question 19¶

Question 20¶

Resources¶

Version¶

Table Of Contents

Previous topic

Next topic

Quick search

Navigation