Functional Programming: int to bignum conversions

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<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<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
    | [] -> Some 0
    | hd::tl ->
      match aux tl (p*base) with
      | Some c->
        let bint = hd*p in 
        if bint < hd then None 
        else Some (bint+c)
      | None -> None in
  let c = List.rev b.coeffs in
  match aux c 1 with
  | Some c -> if b.neg then Some (-c) else Some c
  | None -> 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
    | [] -> Some acc
    | hd::tl ->
        let bint = hd*p in 
        if bint < 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 -> if b.neg then Some (-c) else Some c
  | None -> None

Naming

Camel case isn't forbidden by OCaml but isn't especially idiomatic. Your fromInt and toInt functions would fit better with other OCaml code as from_int and to_int. Further, from_int might fit better into existing OCaml libraries as of_int.

toInt

There's an awful lot of logic in this function that seems to revolve around handling negative numbers in the coeffs list. If we stripped that out, we could just write the following. Of course, this still doesn't handle integer overflow.

let to_int {neg; coeffs} =
  let raw = List.fold_left (fun i x -> i * base + x) 0 coeffs in
  raw * (if neg then -1 else 1)

But as it stands, we can't guarantee that a bignum value won't contain negative values in the coeffs list. What if we could?

Abstract types

First off, let's start building a module to organize this code.

module Bignum = struct
  let base = 1000

  type t = {neg: bool; coeffs: int list}

  let of_int n =
    let rec aux num =
      if num = 0 then []
      else abs (num mod base) :: aux (num/base)
    in
    {neg=n < 0; coeffs=List.rev (aux n)}

  let to_int {neg; coeffs} =
    let raw = List.fold_left (fun i x -> i * base + x) 0 coeffs in
    raw * (if neg then -1 else 1)
end

The problem is that we can still directly construct a Bignum.t value.

# Bignum.{neg=true; coeffs=[1; 2; 3]};;
- : Bignum.t = {Bignum.neg = true; coeffs = [1; 2; 3]}

But if we construct a module signature that only says the module has a type t and not anything about how that type is defined, we can render Bignum.t abstract.

module type BIGNUM = sig
  val base : int
  type t
  val of_int : int -> t
  val to_int : t -> int
end

module Bignum : BIGNUM = struct
  let base = 1000

  type t = {neg: bool; coeffs: int list}

  let of_int n =
    let rec aux num =
      if num = 0 then []
      else abs (num mod base) :: aux (num/base)
    in
    {neg=n < 0; coeffs=List.rev (aux n)}

  let to_int {neg; coeffs} =
    let raw = List.fold_left (fun i x -> i * base + x) 0 coeffs in
    raw * (if neg then -1 else 1)
end

Testing:

# Bignum.of_int 67;;
- : Bignum.t = <abstr>

Now, outside of the Bignum module's implementation, there is no way to directly modify a Bignum.t value, and such a value can only be created by Bignum.of_int. If the implementation is sound, this means we can control its contents and keep them in a valid state.

Integer overflow

As mentioned before, Bignum.to_int does not currently handle integer overflow very well. Doing things like adding or multiplying big numbers will eventually go past what an int can hold or why would we not just use int?

When the result overflows, instead of a larger number, we'll get a negative number. On each run through the fold we can calculate the next accumulated value. If that is less than the value we went in with, then that means we've overflowed trying to convert back to an int and we can raise an exception.

This really only becomes useful when you add in other operations on Bignum.t values that can generate new values that might not represent valid int values.

  let to_int {neg; coeffs} =
    let raw = 
      List.fold_left 
        (fun i x -> 
           let i' = i * base + x in 
           if i' < i then failwith "Integer overflow" 
           else i') 
        0 
        coeffs 
    in
    raw * (if neg then -1 else 1)