OCaml rev_int function

Question

With my original code I kept getting Error: Parse error: [expr level ;] expected after "in" (in [expr]) on the line let numDigits = numDigits - 1 in

Original:

let rec rev_int num =
  if num / 10 == 0 then
     num
  else
    let temp = num mod 10 in

    let numDigits = String.length(string_of_int num) - 1 in

    if num < 0 then
      let numDigits = numDigits - 1 in
    else
      let numDigits = numDigits + 0 in

    let num = (num - temp) / 10 in
    temp * int_of_float(10.0 ** float_of_int numDigits) + rev_int num

With variations of:

if num < 0 then
   let numDigits = numDigits - 1 in;
else
   let numDigits = numDigits + 0 in;

---

if num < 0 then
   let numDigits = numDigits - 1 in
else begin
   let numDigits = numDigits + 0 in end

I revised the code and now it works, but I was wondering if there was a way to do it with nested if and less redundancy.

Revised:

let rec rev_int num =
  if num / 10 == 0 then
    num
  else
    let temp = num mod 10 in

    let numDigits = String.length(string_of_int num) - 1 in

    if num < 0 then
      let numDigits = numDigits - 1 in
      let num = (num - temp) / 10 in
      temp * int_of_float(10.0 ** float_of_int numDigits) + rev_int num
    else
      let numDigits = numDigits + 0 in
      let num = (num - temp) / 10 in
      temp * int_of_float(10.0 ** float_of_int numDigits) + rev_int num

Answer 1

It seems that in both branches you're doing the same calculation, so might want to begin by pushing the conditional in, obtaining:

let rec rev_int num =
  if num / 10 == 0 then
    num
  else
    let temp = num mod 10 in

    let numDigits = String.length(string_of_int num) - 1 in

    let numDigits = numDigits - (if num < 0 then 1 else 0) in
    let num = (num - temp) / 10 in
    temp * int_of_float(10.0 ** float_of_int numDigits) + rev_int num

Just an initial thought to get you started on improving the code.

Answer 2

Nested ifs are just a minor problem with this function. A much bigger problem is that the algorithm is poor.

It appears that you want to reverse the digits of an integer. To do that, you are doing all kinds of costly conversions, like string_of_int, float_of_int, and int_of_float. In particular, converting an int to a string actually involves many operations behind the scenes — just so that you can figure out how many places to left-shift your number!

What you want is a recursive algorithm that only manipulates the least-significant digits of numbers.

let rev_int num =
  let rec rev_int' n m = match n with
    | 0 -> m
    | n -> rev_int' (n / 10) (10 * m + (n mod 10))
  in rev_int' num 0

Answer 3

From the revised version:

Factor the common code from both branches:

let rec rev_int num =
  if num / 10 == 0 then
    num
  else
    let temp = num mod 10 in

    let numDigits = String.length(string_of_int num) - 1 in

    let numDigits = numDigits - (if num < 0 then 1 else 0) in
    let num = (num - temp) / 10 in
    temp * int_of_float(10.0 ** float_of_int numDigits) + rev_int num

(num - temp) / 10 = num / 10 when temp = num mod 10:

let rec rev_int num =
  if num / 10 == 0 then
    num
  else
    let temp = num mod 10 in

    let numDigits = String.length(string_of_int num) - 1 in

    let numDigits = numDigits - (if num < 0 then 1 else 0) in
    let num = num / 10 in
    temp * int_of_float(10.0 ** float_of_int numDigits) + rev_int num

Inline temp definition, as it is a terrible name anyway, and avoid rebinding the same name multiple times:

let rec rev_int num =
  if num / 10 == 0 then
    num
  else
    let numDigits = String.length(string_of_int num) - 1 
                    - (if num < 0 then 1 else 0) in
    num mod 10 * int_of_float(10.0 ** float_of_int numDigits) 
    + rev_int (num / 10)

Maybe more idiomatic ocaml: use snake_case and pattern matching (with is also more efficient: you don't recalculate n / 10 twice) :

let rec rev_int num = 
  match num / 10 with
  | 0 -> num
  | q ->
    let num_digits = String.length (string_of_int num) - 1 
                     - (if num < 0 then 1 else 0) in
    num mod 10 * int_of_float (10.0 ** float_of_int num_digits) 
    + rev_int q

Answer 4

A local function which takes another argument provides a way to write this without repeatedly converting to a string and finding out how many digits are in it.

If we start with this number, we can simply count it down to 1 in our local function rev_int'.

let rev_int num =
  let num_as_str = string_of_int num in
  let num_digits = String.length num_as_str in
  let rec rev_int' num digits = 
    if digits = 1 then
      num
    else
      (num mod 10) * 
      int_of_float (10. ** float_of_int (digits - 1)) + 
      rev_int' (num / 10) (digits - 1)
  in
  rev_int' num num_digits

But a better approach would be to use that added argument as an accumulator and make this tail-recursive. This also gets rid of the floating point math.

let rev_int num =
  let rec rev_int' num acc =
    if num < 10 then
      acc * 10 + num
    else
      rev_int' (num / 10) (acc * 10 + num mod 10)
  in
  rev_int' num 0

Alternatively, we leverage sequences to factor out the work of getting the digits from any int, then fold (folds abstracting out the recursion with an accumulator idiom) over that sequence to generate the reversed int.

let rec digits_seq num () =
  Seq.(
    if num < 10 then 
      Cons (num, empty)
    else 
      Cons (num mod 10, digits_seq (num / 10))
  )

let rev_int num =
  num
  |> digits_seq
  |> Seq.fold_left (fun i x -> i * 10 + x) 0