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: 22 Feb 2020).

Question 1

Based on Exercise 10 in Week 04, implement an OCaml function of type string -> string -> string that concatenates two strings, using String.init (or Stringy.init if your OCaml installation is version-challenged).

Question 2

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

1. one that uses String.mapi (or Stringy.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 3

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

Implement a few palindrome generators of type string -> string, i.e., OCaml functions that map a string (which is not necessarily a palindrome) to a palindrome that contains this string. There is no need for unit tests here, your implementations can just be illustrated with a couple of examples. Each of them, however, should be motivated.

Question 5

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 6

Implement an OCaml function that reverses a palindrome.

Question 7

Implement an OCaml function of type string -> string that, given a string containing the successive characters c0, c1, c2, etc., constructs a string that contains the following successive characters:

• ' ', i.e., the space character,
• F_0 occurrences of c0, where F_0 is the first Fibonacci number,
• F_1 occurrences of c1, where F_1 is the second Fibonacci number,
• F_2 occurrences of c2, where F_2 is the third Fibonacci number,
• F_3 occurrences of c3, where F_3 is the fourth Fibonacci number,
• etc.

For any given string, characterize the length of the resulting string.

Resources

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

Version

Added the "abc" example in Question 2 [27 Feb 2020]

Created [22 Feb 2020]