I've been messing around with learning some functional programming and decided to pick up ML as my vehicle to do so. It's only been a few days since I picked up ML and maybe have spent about 5-6 hours total working through some problems. Anyway, on to my issue.
Normally when learning a language I go through a few project euler questions to get a feel for the syntax and operations. So I've been working on a problem that requires a factorial function. Although I keep getting an overflow error, normally to solve this in other languages I would add some memoization or rely on standard libraries to avoid it but my inexperience with ML makes memoization seem foreign.
I've tried something like this using tail recursion but no dice:
fun fact_helper (0,r:int) = r
| fact_helper (n:int,r:int) = fact_helper (n-1,n*r);
fun factorial n:int = fact_helper(n, 1);
Even using standard libs:
foldl op * 1 (List.tabulate(100, fn x => x + 1))
will cause an overflow.
I've done some googling but ML seems to have very sparse discussions or community. So I guess my question is what is an example or how should I go about writing my factorial function in a memoized way or in general how to avoid overflows in ML.
The problem is that your implementation relies on the Int.int datatype, which on SML/NJ is limited to 31 bits (see Int.precision). That means there's an upper bound to the values you can calculate. If you try to get over that limit, you'll get an Overflow exception:
- (Option.valOf Int.maxInt) + 1;
uncaught exception Overflow [overflow]
raised at: <file stdIn>
The solution is to use the IntInf structure, which provides arbitrary precision arithmetic:
open IntInf;
fun fact_helper (0,r:int) = r
| fact_helper (n:int,r:int) = fact_helper (n-1,n*r);
fun factorial n:int = fact_helper(n, 1);
factorial 50;
(* 30414093201713378043612608166064768844377641568960512000000000000 *)