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);;
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)
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?
;; 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
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).
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
With Buffer and the yawaramin’s roman_kv list we have:
let concat2 buf str n =
for _ = 1 to n do
Buffer.add_string buf str
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
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.
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)
(and small syntaxic stuff like 