# Is this idiomatic ocaml code?

Please show me other ways I can solve this problem, not sure if I’m naively using recursion…

``````open Printf;;

let concat dest str n =
let rec aux buffer counter =
if counter = 0
then buffer
else aux (buffer ^ str) (counter - 1)
in aux dest n;;

let to_roman number =
let map_size = 13 in
let roman_keys = [1000; 900;500;400;100;90;50;40;10;9;5;4;1] in
let roman_values = ["M";"CM";"D";"CD";"C";"XC";"L";"XL";"X";"IX";"V";"IV";"I"] in
let rec iter n roman_numeral counter =
let key = List.nth roman_keys (counter - 1) in
let value = List.nth roman_values (counter - 1) in
let dif = n - (n mod key) in
let amount = (dif / key) in
if counter = map_size
then (concat roman_numeral value amount)
else iter (n - dif) (concat roman_numeral value amount) (counter + 1)
in iter number "" 1;;

printf "%s\n" (to_roman 2844);;

``````

It’s pretty good! Some suggestions:

• `List.nth` is a red flag, you should do the recursion by pattern matching on the list rather than with an integer `counter`
• Rather than having two lists that must have the same size, you can do a list of products `[ 1000, "M" ; 900, "CM" ; ... ]` to ensure that elements are paired correctly
• Small repetition on `concat roman_numeral ..` that could be avoided

Bonus:

• It doesn’t matter here as the outcome is very small, but repeated string concatenation with `^` could be slow in general, so you could attempt to use a single `String.concat` instead as an exercice
• Printf debugging tip: Use `\n%!` rather than `\n` in order to force the system to show the output as soon as possible (otherwise there could be a lag as printf bufferizes, and it can be confusing when debugging larger programs)
• You might want to try `ocamlformat` to get the indentation and parens right (and small syntaxic stuff like `;;` that is only used in the toplevel)
1 Like

Thank you! I will try to use this information to refactor the code a little bit.

Hmm on pattern matching on the list,
so refactor the parallel list into an assoc list
then how would I go about pattern matching?
I need to access the the list items in a iterative fashion, so should I take the head to process the key and value pair and then pass the tail back into the function?

Yes! (not sure how much hints you need, that’s exactly it )

`;;` only used in the toplevel… It is not completly true, since the compiler is happy with it, and if you remove it, `printf` would be used as 4th argument of `iter` like `iter number "" 1 printf`

I guess the we could get rid of `;;` here with `let () = printf "%s\n" (to_roman 2844)`.

Couple of suggestions. I usually ‘lift up’ any values which are constant i.e. not variable between function calls/iterations. Also because of precedence rules, you don’t need parentheses in some places: OCaml library : Ocaml_operators

``````let roman_kv = [
1000, "M";
900, "CM";
...
]

(* No need to hard-code it *)
let map_size = List.length roman_kv

let rec iter n roman_numeral counter =
let key, value = List.nth roman_kv (pred counter) in
let dif = n - n mod key in
let amount = dif / key in
if counter = map_size then concat roman_numeral value amount
else iter (n - dif) (concat roman_numeral value amount) (succ counter)

let to_roman number = iter number "" 1

let () = Printf.printf "%s\n%!" @@ to_roman 2844
``````
1 Like

Thank you for the advice !

1 Like

An idiomatic OCaml code won’t use `List.nth` if not needed.

Here a new example:

``````let roman2 number =
let rec roman2_aux n roman_numeral_prefix kv_list =
match kv_list with
| [] -> roman_numeral
| (key, value) :: tail ->
let dif = n - n mod key in
let amount = dif / key in
roman2_aux (n - dif) (concat roman_numeral_prefix value amount) tail
in
roman2_aux number "" roman_kv
``````

It uses `roman_kv` defined by yawaramin.

Also, letting the `List.fold_left` doing the recusion.

``````let roman3 number =
List.fold_left
(fun (str,n) (key,value) ->
let dif = n - n mod key in
let amount = dif / key in
(concat str value amount), (n - dif))
("",number) roman_kv
|> fst
``````

The idea is that `List.fold_left` takes `("", number)` as a starting value and iter through the given anonymous (lambda) function for each member of the list. This will give a new value `(str, 0)` and we apply `fst` which extract the `str` string.

Note `a_long_expression |> f` which is equivalent with `f( a_long_expression)`.

1 Like

A few suggestions:

Never use `^` to build a string incrementally, it is going to explode in your face eventually.
Instead, use a `Buffer.t` which is made for that.

``````let concat buf str n =
for _ = 1 to n do
done
``````

Associate the letters and the numbers by putting them in pairs. And use an array for easy indexing.

``````let roman =
[|
1000, "M";
900 , "CM";
500 , "D";
400 , "CD";
100 , "C";
90  , "XC";
50  , "L";
40  , "XL";
10  , "X";
9   , "IX";
5   , "V";
4   , "IV";
1   , "I";
|]
``````

Use a `Buffer.t` to build the result; avoid indexing calculations by starting your loop at 0; avoid giving different names to the same quantity by using shadowing. Avoid writing the continuation of `let ... in` in the same line. Use short names for integer variables (`i`, `n`, …).

``````let to_roman n =
let buf = Buffer.create 0 in
let rec iter n i =
if i < Array.length roman then begin
let key, value = roman_map.(i) in
let dif = n - n mod key in
let amount = dif / key in
concat buf value amount;
iter (n - dif) (i + 1)
end
in
iter n 0;
Buffer.contents buf
``````

Use `print_endline`.

``````let () =
print_endline (to_roman 2844)
``````

Cheers,
Nicolas

2 Likes

With `Buffer` and the yawaramin’s `roman_kv` list we have:

``````let concat2 buf str n =
for _ = 1 to n do
done

let roman4 number =
let buffer = Buffer.create 0 in
let _ = List.fold_left
(fun n (key,value) ->
let dif = n - n mod key in
let amount = dif / key in
concat2 buffer value amount;
n - dif)
number
roman_kv in
Buffer.contents buffer
``````

Note, we have also an `Array.fold_left`.

1 Like

Hi! if you are open to simplify a bit your algorithm you could do without `concat`:

``````let roman =
[
1000, "M";
900 , "CM";
500 , "D";
400 , "CD";
100 , "C";
90  , "XC";
50  , "L";
40  , "XL";
10  , "X";
9   , "IX";
5   , "V";
4   , "IV";
1   , "I";
]

let to_roman x =
let rec loop x rom = function
| [] -> rom
| (y, r) :: rest as list ->
if x >= y then loop (x - y) (rom ^ r) list
else loop x rom rest in
loop x "" roman
``````

Of course, as others said, for very long strings you should not use `^`, but in this case, you know that you have a small number of iterations, so this is perfectly acceptable.

2 Likes

Instead of concating in the loop, you could build a list, then `String.concat` it at the end ?

Yes, this would make:

``````let roman5 number =
let rec roman5_aux n kv_list =
match kv_list with
| [] -> []
| (key, value)::tail ->
if key <= n
then value :: roman5_aux (n-key) kv_list
else roman5_aux n tail
in
String.concat "" (roman5_aux number roman_kv)
``````