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: 23 Feb 2021).

Question 1

Implement an OCaml function of type string -> string -> string that concatenates two strings, using String.init.

Hints:

• Check out String.init in the index.
• Revisit Exercise 18 in Week 04.

Question 9

This (mislabeled, sorry) question is a warmup for Question 2 and Question 3 (optional) just below.

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

Question 2

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.

1. In which order are the characters accessed in the given string?
2. Using a recursive function that operates over a natural number, implement a left-to-right version of String.map. Your implementation will therefore simulate a for-loop that goes from the smallest index to the largest index in the string.
3. Using a recursive function that operates over a natural number, implement a right-to-left version of String.map. Your implementation will therefore simulate a for-loop that goes from the largest index to the smallest index in the string.

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 3 (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.

1. In which order are the characters accessed in the given string?
2. Using a recursive function that operates over a natural number, implement a left-to-right version of String.mapi. Your implementation will therefore simulate a for-loop that goes from the smallest index to the largest index in the string.
3. Using a recursive function that operates over a natural number, implement a right-to-left version of String.mapi. Your implementation will therefore simulate a for-loop that goes from the largest index to the smallest index in the string.

Question 4

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

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

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

Question 5

For the purpose of this question, the reverse function of Question 4 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.

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” isn’t.

Question 6

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.

Question 7

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.

1. Implement a palindrome detector using String.mapi.
2. Implement a palindrome detector using recursion over a non-negative integer.

Question 8 (not optional)

Implement an OCaml function that reverses a palindrome.

Question 10 (optional)

Implement String.map using String.mapi.

Question 11 (optional)

Implement String.mapi using String.init.

Resources

• The OCaml code for the present mini-project (latest version: 23 Feb 2021).

Version

Clarified that in Question 6, the given integer is the length of the resulting palindrome thanks to Ann Chen’s eagle eye [25 Feb 2021]

Moved Question 9 where it belongs, i.e., before Question 2 and Question 3 (optional) [24 Feb 2021]

Reordered the resource file, thanks to Max Han’s eagle eye [23 Feb 2021]

Completed the pastiche [22 Feb 2021]

Restated Question 6 and reordered the questions [21 Feb 2021]

Created [21 Feb 2021]