标准ML fibonacci溢出

Question

我一直在学习一些函数式编程，并决定选择ML作为我的工具。我刚学到ML，大概花了5-6个小时来解决一些问题。不管怎样，关于我的问题。

通常，在学习一种语言时，我会通过几个euler项目来了解语法和操作。所以我一直在研究一个需要阶乘函数的问题。虽然我一直有一个溢出错误，通常为了用其他语言解决这个问题，我会添加一些回忆录或者依赖标准库来避免它，但是我在ML方面的经验让回忆录看起来很陌生。

我尝试过这样的方法，使用尾递归，但没有骰子：

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

即使使用标准的lib：

foldl op * 1 (List.tabulate(100, fn x => x + 1))

会导致溢出。

我已经做了一些谷歌搜索，但ML似乎有非常少的讨论或社区。因此，我想我的问题是，什么是一个例子，或者我应该如何以回忆录的方式编写我的阶乘函数，或者一般情况下，如何避免ML中的溢出。

Answer 1

问题是您的实现依赖于Int.int数据类型，SML/NJ上的数据类型仅限于31位(参见Int.precision)。这意味着你可以计算的值有一个上限。如果您试图超越这个限制，您将得到一个Overflow异常：

- (Option.valOf Int.maxInt) + 1;

uncaught exception Overflow [overflow]
  raised at: <file stdIn>

解决方案是使用IntInf结构，它提供任意精度算法：

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