Loading ...
Sorry, an error occurred while loading the content.

Roman/Arabic Numeral Translator

Expand Messages
  • erichof425
    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
    Message 1 of 6 , Apr 26, 2006
    • 0 Attachment
      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.

      http://rafb.net/paste/results/zmongR17.html

      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.
    • Jonathan Roewen
      ... Haven t had a solid look, but if you use extlib (it s a marvellous little add-on to build on the stdlib), you can write before & after much simpler (also,
      Message 2 of 6 , Apr 26, 2006
      • 0 Attachment
        > http://rafb.net/paste/results/zmongR17.html

        Haven't had a solid look, but if you use extlib (it's a marvellous
        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).

        e.g.

        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 *)

        with extlib:

        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).

        Jonathan
      • dmitry grebeniuk
        Shalom, Jonathan. ... JR isn t tail-rec .. your inner before2 should use an accumulator). Not should , but may . Sometimes it s better to use
        Message 3 of 6 , Apr 26, 2006
        • 0 Attachment
          Shalom, Jonathan.

          >> http://rafb.net/paste/results/zmongR17.html

          JR> isn't tail-rec .. your inner before2 should use an accumulator).

          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
          real program).


          p.s./ thanks for combinator parsers, it was a good reading,
          many things became clear for me.

          --
          WBR,
          dmitry mailto:gds-mlsts@...
        • Martin Jambon
          ... There are a couple of things that you could do to make your code reasonably fast. Specifically, you should use associative lists with moderation, since
          Message 4 of 6 , Apr 26, 2006
          • 0 Attachment
            On Thu, 27 Apr 2006, erichof425 wrote:

            > 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.
            >
            > http://rafb.net/paste/results/zmongR17.html
            >
            > 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.

            There are a couple of things that you could do to make your code
            reasonably fast. Specifically, you should use associative lists with
            moderation, since finding an item requires to scan half of the list on
            average.

            (* 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,
            e.g.
            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;
            a

            let find_roman_digit c = roman_digits.(int_of_char c)



            Martin

            --
            Martin Jambon, PhD
            http://martin.jambon.free.fr

            Edit http://wikiomics.org, bioinformatics wiki
          • Matt Gushee
            ... Or if you are writing a general-purpose library, where you cannot make any assumptions about what is typical data. -- Matt Gushee The Reluctant Geek:
            Message 5 of 6 , Apr 27, 2006
            • 0 Attachment
              dmitry grebeniuk wrote:

              > IMHO, accumulators should be used if there is stack overflow
              > on typical data,

              Or if you are writing a general-purpose library, where you cannot make
              any assumptions about what is "typical data."

              --
              Matt Gushee
              The Reluctant Geek: http://matt.gushee.net/rg/
            • dmitry grebeniuk
              Shalom, Matt. ... MG Or if you are writing a general-purpose library, where you cannot make MG any assumptions about what is typical data. In any case
              Message 6 of 6 , May 4, 2006
              • 0 Attachment
                Shalom, Matt.

                >> IMHO, accumulators should be used if there is stack overflow
                >> on typical data,

                MG> Or if you are writing a general-purpose library, where you cannot make
                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.

                --
                WBR,
                dmitry mailto:gds-mlsts@...
              Your message has been successfully submitted and would be delivered to recipients shortly.