标准 ML 斐波那契溢出

Question

我一直在学习一些函数式编程，并决定选择 ML 作为我的工具。我接触 ML 才几天时间，可能总共花了大约 5-6 个小时来解决一些问题。无论如何，关于我的问题。

通常在学习一门语言时，我会通过一些项目欧拉问题来了解语法和操作。所以我一直在研究一个需要阶乘函数的问题。虽然我不断收到溢出错误，通常为了用其他语言解决这个问题，我会添加一些记忆或依靠标准库来避免它，但我对 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);

即使使用标准库：

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

标准 ML 斐波那契溢出

Standard ML fibonacci overflow

recursion

functional-programming

sml

smlnj

ml