Alfrothul: Decimal integers As We Know Them are a shorthand for polymomials. For example:
12345 = 1 * 10^4 + 2 * 10^3 + 3 * 10^2 + 4 * 10^1 + 5 * 10^0
= (((1 * 10 + 2) * 10 + 3) * 10 + 4) * 10 + 5
Harald: Indeed. The first right-hand side is an ordinary polynomial, and the second the polynomial in Horner form.
Alfrothul: This Horner form suggests a way to convert a nonempty string of digits into the corresponding non-negative integer in base 10, by induction on the length of this string.
Halcyon: How about we name this function nat_of_digits?
Harald: That would be logical.
Vigfus (diligent): Here is a unit-test function for the implementation:
let test_nat_of_digits candidate =
(candidate "9" = 9)
&& (candidate "89" = 89)
&& (candidate "789" = 789)
&& (candidate "6789" = 6789)
&& (let n = Random.int 10000
in candidate (string_of_int n) = n)
(* etc. *);;
Vigfus: The last test exploits the fact that nat_of_digits is a left inverse of string_of_int for non-negative integers.
Alfrothul: Thanks, Vigfus, that’s pretty good!
Test test_nat_of_digits.
Alfrothul: We will also need a function to map a digit character into an integer:
let nat_of_digit c =
let () = assert ('0' <= c && c <= '9') in
int_of_char c - int_of_char '0';;
Explain nat_of_digit in your own words.
Harald: Well, we first need to check that the given string is nonempty:
let nat_of_digits s =
let n = String.length s
in let () = assert (n > 0) in
...
Alfrothul: Right. And then we need to define a recursive function over the length of the given string:
let nat_of_digits s =
let n = String.length s
in let () = assert (n > 0) in
let rec visit i =
if i = 0
then ...
else let i' = pred i
in let ih = visit i'
in ... ih ...
in visit ...;;
Harald: And initially, we should apply this recursive function to the last index of the string:
let nat_of_digits s =
let n = String.length s
in let () = assert (n > 0) in
let rec visit i =
if i = 0
then ...
else let i' = pred i
in let ih = visit i'
in ... ih ...
in visit (n - 1);;
Alfrothul: OK. Base case... Let’s see. We need to get the corresponding character in the string...
Harald: ...and convert it into an integer.
Guess what.
The fourth wall: Is he talking to us?The fifth wall: Not sure.
Alfrothul: Thanks, guys.
Harald: Nice solution, too.
Brynja: So, the induction step?
Harald: Well, we still need to get the corresponding character in the string...
Alfrothul: ...and convert it into an integer too.
Harald: And then we should add it, according to the Horner form.
Alfrothul: Pretty sure a multiplication by 10 is involved too.
Harald: Let me scribble something.
Alfrothul: On the wall?
The fourth wall: Oh, the ignominy.
Halcyon (cleverly): Well, the writing was on the wall.
Guess again. (You had been warned.)
Alfrothul: All right! And now for the unit tests:
let () = assert (test_nat_of_digits nat_of_digits);;
Harald: I can’t wait to load the file.
Vigfus: Woa, woa, woa.
Brynja (kindly): That was too fast?
Vigfus: Er, yes?
Brynja: How about we render the computation as a theater play?
Vigfus (grateful): Yes, let’s.
Halcyon: Can I play too?
Brynja: Yes, please. But we need a fourth actor.
The fourth wall: May I be of assistance?
Brynja: Wonderful, yes, thanks.
Vigfus: So?
Brynja: OK. I play nat_of_digits who is applied to "369". Vigfus, you play visit when it is applied to 2, Halcyon, you play visit when it is applied to 1, and Fourth Wall, you play visit when it is applied to 0. Remember to indent to convey the nesting of the calls. OK?
Everybody agrees, and Brynja gets started.
Brynja: Hello. I am nat_of_string and I am applied to "369". Let me compute its length – OK, it’s 3 since this string contains 3 characters, and I name it n. Since 3 is strictly positive, the assertion is satisfied and so the computation can continue.
Halcyon: And if n denotes 0?
Vigfus: Then the string would contain 0 characters, it would be the empty string, and the string we are given is supposed to be nonempty.
Halcyon: OK. Just for completeness, what if n denotes a negative integer?
The fourth wall: I think we are safe here, since no strings with a negative length exist in this Euclidean space.
Brynja: Right, thanks. So n denotes 3, and I get ready to call visit with the largest possible index for this string, namely n - 1, i.e., 2.
Vigfus: Yes, I remember Exercise 01.d this week.
Brynja: Good. So Vigfus, I call you with 2 as actual parameter.
Vigfus: Hello. I am visit and I am applied to 2. 2 is not 0, and so we are in the induction step. Let me name the predecessor of 2, i.e., 1, as i'. And let me call visit with i', i.e., 1, as actual parameter. So Halcyon, I call you with 1 as actual parameter.
Halcyon: Hello. I am visit and I am applied to 1. 1 is not 0, and so we are in the induction step. Let me name the predecessor of 1, i.e., 0, as i'. And let me call visit with i', i.e., 0, as actual parameter. So Fourth Wall, I call you with 0 as actual parameter.
The fourth wall: Hello. I am visit and I am applied to 0. 0 is 0, and so we are in the base case. Let me get the character at index 0 in "369", i.e., '3'. Since this character is a digit, I can convert it into an integer, namely 3. And then I return 3 to Halcyon.Halcyon: Thank you, Fourth Wall, for 3. As per the Horner form, let me multiply it by 10 – there we go, 30. I was applied to 1 so let me also get the character at index 1 in "369", i.e., '6'. Since this character is a digit, I can convert it into an integer, namely 6, which I add to 30. And then I return 36 to Vigfus.
Vigfus: Thank you, Halcyon, for 36. As per the Horner form, let me multiply it by 10 – there we go, 360. I was applied to 2 so let me also get the character at index 2 in "369", i.e., '9'. Since this character is a digit, I can convert it into an integer, namely 9, which I add to 360. And then I return 369 to Brynja.
Brynja: Thank you, Vigfus, for 369, and thank you all for participating.
The fourth wall: Always here if you need to bounce an idea off someone.
Brynja: Thank you most kindly.
She turns to Vigfus, who looks contemplative.
Brynja: Are things clearer now, Vigfus?
Vigfus: I think so, thanks. Can we play again with "x86" as an argument for nat_of_digits?
Brynja: Sure thing. I still play nat_of_digits who is applied to "x86". Halcyon, you play visit when it is applied to 2, Fourth Wall, you play visit when it is applied to 1, and Vigfus, you play visit when it is applied to 0. And you all indent to convey the nesting of the calls. OK?
Everybody agrees, and Brynja gets started.
Brynja: Hello. I am nat_of_string and I am applied to "x86". Let me compute its length – OK, it’s 3 since this string contains 3 characters, and I name it n. Since 3 is strictly positive, the assertion is satisfied and so the computation can continue. I get ready to call visit with the largest possible index for this string, namely n - 1, i.e., 2. So Halcyon, I call you with 2 as actual parameter.
Halcyon: Hello. I am visit and I am applied to 2. 2 is not 0, and so we are in the induction step. Let me name the predecessor of 2, i.e., 1, as i'. And let me call visit with i', i.e., 1 as actual parameter. So Fourth Wall, I call you with 1 as actual parameter.
The fourth wall: Hello. I am visit and I am applied to 1. 1 is not 0, and so we are in the induction step. Let me name the predecessor of 1, i.e., 0, as i'. And let me call visit with i', i.e., 0 as actual parameter. So Vigfus, I call you with 0 as actual parameter.
Vigfus: Hello. I am visit and I am applied to 0. 0 is 0, and so we are in the base case. Let me get the character at index 0 in "x86", i.e., 'x'. Since this character is not a digit, the assertion in nat_of_digit fails and the whole computation stops.
Brynja: OK Vigfus?
Vigfus: Yup.
The fourth wall: Maybe we could check at the outset that the given string only contains digits? Then there would be no recursive calls at all if a given string contains something else than a digit, and all the recursive calls would complete if the given string only contains digits.
Brynja: And we would do that how?
Vigfus: With String.map.
What do you think? Yes, exactly.
The fourth wall: BTW, thanks, guys.
Brynja: Er, sure. But why?
The fourth wall: For talking, well, to a wall.
Brynja: You do talk back.
The fourth wall: Yes, there is that.
Added entries in the general index [11 Mar 2022]
Added the postlude and the post-postlude [18 Feb 2022]
Created [13 Feb 2022]