Roman/Arabic Numeral Translator
- My first ocaml program translates between Arabic and Roman numerals.
It's a simple small program to help get more familiar with the
language. If you would like to take a look at it, here it is. Please
tell me what you think. I'm sure I did some naive newbie things, so
any constructive criticism would be welcome.
I don't know if this is an acceptable thing to post here, please let
me know if it's not and I won't do it again.
little add-on to build on the stdlib), you can write before & after
much simpler (also, your before isn't tail-rec .. your inner before2
should use an accumulator).
let before e l =
let rec before acc = function
|  -> List.rev acc
| x when x = e -> List.rev acc
| x :: xs -> before (x::acc) xs
in before  l;;
(* I reuse names since to me it's apparent what is in scope and not,
but just personal preference *)
let before e l = List.take_while ((<>) e) l;;
let after e l = List.drop_while ((<>) e) l;; (* I think this might
include e in the resulting list, so just add List.tl ( <stuff from
above> ) *)
I think you could possibly greatly simplify the code with more use of
HOFs, but without actually trying, it's hard to say exactly what :)
Anyways, just some very brief thoughts (and all my code untested).
- Shalom, Jonathan.
Not "should", but "may". Sometimes it's better to use
non-tail-recursive functions because it may be faster on typical
data. For example, there were attempts to rewrite List.map in
caml-list, and the current implementation, not tail-recursive,
was the fastest one on lists with length 0..10000, iirc.
After all, code with accumulators looks cluttered.
IMHO, accumulators should be used if there is stack overflow
on typical data, or if tail-rec code is faster (of course, speed
should be measured by profiler or similar, on real data and within
p.s./ thanks for combinator parsers, it was a good reading,
many things became clear for me.
- On Thu, 27 Apr 2006, erichof425 wrote:
> My first ocaml program translates between Arabic and Roman numerals.There are a couple of things that you could do to make your code
> It's a simple small program to help get more familiar with the
> language. If you would like to take a look at it, here it is. Please
> tell me what you think. I'm sure I did some naive newbie things, so
> any constructive criticism would be welcome.
> I don't know if this is an acceptable thing to post here, please let
> me know if it's not and I won't do it again.
reasonably fast. Specifically, you should use associative lists with
moderation, since finding an item requires to scan half of the list on
(* Lists of each Roman digit, its value, and its character representation *)
let digits = [I; V; X; L; C; D; M];;
let values = [1; 5; 10; 50; 100; 500; 1000];;
let chars = ['I'; 'V'; 'X'; 'L'; 'C'; 'D'; 'M'];;
(* Conversions for Roman digits *)
let int_of_roman_digit rd =
let digits_values = List.combine digits values in
List.assoc rd digits_values
The function int_of_roman_digit above is pretty inefficient because (1)
you build a whole list of pairs each time you want to convert a character
and (2) because you use an associative list anyway. Since these lists are
short anyway, it's not crime to use associative lists, but I suggest you
build them once and for all.
You can write directly a list of triplets:
let triplets = [ (I, 1, 'I');
(V, 5, 'V');
let digits_values = List.map (fun (x, y, _) -> (x, y)) triplets
let int_of_roman_digit rd = List.assoc rd digits_values
For a better efficiency, you can use the Hashtbl module.
With small ints (or chars) as keys, you can even use directly an array,
let roman_digits =
let a = Array.make 256 None in
List.iter (fun (x, y, z) -> a.(int_of_char z) <- Some (x, y)) triplets;
let find_roman_digit c = roman_digits.(int_of_char c)
Martin Jambon, PhD
Edit http://wikiomics.org, bioinformatics wiki
- dmitry grebeniuk wrote:
> IMHO, accumulators should be used if there is stack overflowOr if you are writing a general-purpose library, where you cannot make
> on typical data,
any assumptions about what is "typical data."
The Reluctant Geek: http://matt.gushee.net/rg/
- Shalom, Matt.
>> IMHO, accumulators should be used if there is stack overflowMG> Or if you are writing a general-purpose library, where you cannot make
>> on typical data,
MG> any assumptions about what is "typical data."
In any case (deep recursion in user code, for example) there is a
possibility of stack overflow, so user should better know how to use
options that tune stack size, than slowing down library code.
Of course, if speed doesn't differ much, the accumulators-pollution
is acceptable for general-purpose library.