This chapter reviews approaches to exercises / questions and how to solve / answer them.
In Question 10 of the mini-project about strings, one is asked to implement String.map as an instance of String.mapi.
Towards solving this exercise, one should first describe String.map and String.mapi in the manner of the description in the chapter about strings:
Given a function f of type char -> char 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 and is defined as follows:
let string_of_char c =
String.make 1 c;;
Given a function f of type int -> char -> char 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.
Indeed if one is not able to describe the terms of the question, how can one hope to answer this question?
One should then reflect on how to simulate the computation carried out by String.map as an instance of String.mapi.
Concretely, given the string "abc", which function
One should then take a deep breath and write the skeleton of the solution:
let string_dot_map_as_an_instance_of_string_dot_mapi f s =
String.mapi
(fun i c ->
...)
s;;
And then one should fill the dots with the result of one’s reflection on how to simulate the computation carried out by String.map as an instance of String.mapi.
One should then check that one’s definition passes the unit tests associated to String.map.
And then one should compose a narrative to explain both the question and its answers based on the above.
In Question 11 of the mini-project about strings, one is asked to implement String.mapi as an instance of String.init.
Towards solving this exercise, one should first describe String.mapi and String.init in the manner of the description in the chapter about strings:
Given a function f of type int -> char -> char 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.
The lecture notes do not include such an essential description of String.init, which is only described informally in an interlude. So based on the essential description of nat_parafold_right in the chapter about primitive iteration to primitive recursion for natural numbers, one should compose this essential description:
Given, e.g., the non-negative integer 3, i.e., the result of evaluating:
succ (succ (succ 0))
and given a function f of type int -> char, String.init essentially yields the result of evaluating:
string_of_char (f 0) ^ string_of_char (f 1) ^ string_of_char (f 2)
One should then reflect on how to simulate the computation carried out by String.mapi as an instance of String.init. For example, what should the size of the resulting string be? And given an index, how could one get the character in the given string at that index?
Concretely, given a function f of type int -> char and the string "abc", which function
One should then take a deep breath and write the skeleton of the solution:
let string_dot_mapi_as_an_instance_of_string_dot_init f s =
String.init
...
(fun i ->
...);;
And then one should fill the dots with the result of one’s reflection on how to simulate the computation carried out by String.mapi as an instance of String.init.
One should then check that one’s definition passes the unit tests associated to String.init.
And then one should compose a narrative to explain both the question and its answers based on the above.
Anton: Thanks, Fourth Wall. I believe we are asked to implement String.map as an instance of String.init.
Alfrothul: How perceptive of you.
Anton: Not really, I just asked Fourth Wall.
Alfrothul: Be that as it may, towards solving this exercise, we should first describe String.map and String.init in the manner of the description in the chapter about strings:
Given a function f of type char -> char 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 and is defined as follows:
let string_of_char c =
String.make 1 c;;
Given, e.g., the non-negative integer 3, i.e., the result of evaluating:
succ (succ (succ 0))
and given a function f of type int -> char, String.init essentially yields the result of evaluating:
string_of_char (f 0) ^ string_of_char (f 1) ^ string_of_char (f 2)
Anton: OK. So we should now reflect on how to simulate the computation carried out by String.map as an instance of String.init. For example, what should the size of the resulting string be?
Alfrothul: This one is simple. It should have the same size as the given string.
Anton: Right:
let string_dot_map_as_an_instance_of_string_dot_init f s =
String.init
(String.length s)
(fun i ->
...);;
Alfrothul: OK. Now given an index, how can we get the character in the given string at that index? This one is simple too. With String.get of course.
Anton: So concretely, given a function f of type int -> char and the string "abc", which function
Alfrothul: Simple indeed:
let string_dot_map_as_an_instance_of_string_dot_init f s =
String.init
(String.length s)
(fun i ->
f (String.get s i));;
Anton: Indeed. And the unit tests?
Alfrothul: Let’s just reuse the ones we made for string_map earlier on.
Bong-sun: Your solution composes f and String.get s.
Anton: It does?
Bong-sun: Well, yes, look:
let compose f g =
fun x -> f (g x);;
let string_dot_map_as_an_instance_of_string_dot_init f s =
String.init
(String.length s)
(compose f (String.get s));;
Alfrothul: Indeed. fun i -> f (String.get s i) is an instance of compose applied to f and String.get s. Well spotted, Bong-sun.
Bong-sun (smiling): And this implementation passes the unit tests too.
Dana: So we were first asked to implement String.map as an instance of String.mapi, and then to implement String.mapi as an instance of String.init, and then to implement String.map as an instance of String.init.
Alfrothul: Right. And we directly implemented String.map as an instance of String.init.
Dana: How about we combine the two first implementations instead, to calculate the third?
Bong-sun: Let’s see. Following the chapter about inlining functions in Week 07, we should inline the definition of string_dot_mapi_as_an_instance_of_string_dot_init in the definition of string_dot_map_as_an_instance_of_string_dot_mapi, starting from:
let string_dot_map_as_an_instance_of_string_dot_mapi_as_an_instance_of_string_dot_init f s =
string_dot_mapi_as_an_instance_of_string_dot_init
(fun i c ->
f c)
s;;
Dana: Right. And then we unfold the call to string_dot_mapi_as_an_instance_of_string_dot_init:
let string_dot_map_as_an_instance_of_string_dot_mapi_as_an_instance_of_string_dot_init' f s =
let s = s
and f = fun i c -> f c
in String.init
(String.length s)
(fun i ->
f i (String.get s i));;
Alfrothul: And then we unfold the let-expressions:
let string_dot_map_as_an_instance_of_string_dot_mapi_as_an_instance_of_string_dot_init'' f s =
String.init
(String.length s)
(fun i ->
(fun i c -> f c) i (String.get s i));;
Bong-sun: And then we simplify the application of fun i c -> f c to i and String.get s i.
Alfrothul: And the result is our definition of string_dot_map_as_an_instance_of_string_dot_init.
Dana: Calculated, not invented. And also: no surprises, which is a good thing.
Added the “Concretely,” paragraphs, the section about implementing String.map as an instance of String.init, and the aftermath [26 Mar 2023]
Created [12 Mar 2023]