Functional Programming: int to bignum conversions I'm doing an exercise where I need to convert int to bignum in OCaml, for example:


123456789 -&gt; {neg:false; coeffs:[123;456;789]}



There were a lot of things going inside my head when writing the function, and it was a load of fun. However, I'm not really sure if this is the cleanest, and fastest way to do this.

type bignum = {neg: bool; coeffs: int list};;
let base = 1000;;

let fromInt (n: int) : bignum =
  let rec aux num:int list=
    if num==0 then
       []
    else 
       abs (num mod base) :: aux (num/base)
  in
  {neg=n&lt;0; coeffs=List.rev (aux n)}
;;


fromInt turns an int to a bignum. Things to note:


I decided to mod the number with the base, and then divide the number
by the base and use that as the input. This is so I can avoid having to do exponents on ints. Was actually pretty excited when I realized that.
Used abs on (num mod base) every recursive call. Do you think there is a cleaner way of doing this? The the reason I didn't abs it on the first call was because (-max_int) &lt;&gt; min_int
As you can see I'm using List.rev because I do it in reverse order. This is so I can avoid having snoc lists. I'm not really sure if it's the only way though so feel free to note me.


And here is toInt, which turns a bignum into an int.

let toInt (b: bignum) =
  let rec aux (b:int list) (p:int)=
     match b with
     |hd::[]-&gt; Some (hd*p)
     |hd::tl-&gt; (match aux tl (p*base) with
        |Some c-&gt; let bint = (hd*p) in 
                  if bint &lt; hd then None 
                  else Some (bint+c)
        |None -&gt; None)
     |[]-&gt;Some 0
  in
  let {neg=n; coeffs=x} = b in
  let c = List.rev x in
     match aux c 1 with
     |Some c-&gt; if n then Some (-c) else Some c
     |None -&gt; None
;;


I'm particularly not fond of the nested match statements, and there is probably still room for cleanup. Is there?
num==0 is misleading, use num=0 (although it has the same meaning for integers). Also, fromInt is spread over too many lines for my taste, I'd prefer the following choice of line breaks:

let fromInt (n: int) : bignum =
  let rec aux num : int list =
    if num=0 then []
    else abs (num mod base) :: aux (num/base) in
  {neg=n&lt;0; coeffs=List.rev (aux n)}


This is fine for short lists of coefficients. In general tail recursion is preferred. I drop type annotations below. I add type annotations during debugging if I start getting confusing type errors, other than that I put types of functions in the interface (.mli).

let fromInt n =
  let rec aux acc num =
    if num=0 then acc
    else aux (abs (num mod base) :: acc) (num/base) in
  {neg=n&lt;0; coeffs=aux n}


General note. I use the following kinds of line breaks with if..then..else depending on what fits in 80 columns and looks nice.

if test then blah
else blah

if test
then blah
else blah

if test
then
  blah
else
  blah


Now on to toInt. First, the way I would format it:

let toInt b =
  let rec aux b p =
    match b with
    | [] -&gt; Some 0
    | hd::tl -&gt;
      match aux tl (p*base) with
      | Some c-&gt;
        let bint = hd*p in 
        if bint &lt; hd then None 
        else Some (bint+c)
      | None -&gt; None in
  let c = List.rev b.coeffs in
  match aux c 1 with
  | Some c -&gt; if b.neg then Some (-c) else Some c
  | None -&gt; None


Again, it is interesting to explore the tail-recursive variant. I use my preferred style.

let toInt b =
  let rec aux acc p = function
    | [] -&gt; Some acc
    | hd::tl -&gt;
        let bint = hd*p in 
        if bint &lt; hd then None 
        else aux (bint + acc) (p*base) tl in
  let c = List.rev b.coeffs in
  match aux 0 1 c with
  | Some c -&gt; if b.neg then Some (-c) else Some c
  | None -&gt; None