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

はしても、標準的なLIBSを使用して：

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

は、オーバーフローが発生します。

私はいくつかの検索を行っていますが、MLは非常にまばらなディスカッションやコミュニティを持っているようです。だから、私の疑問は、例であると思いますか、私の階乗関数をメモ形式で書くか、一般にMLでオーバーフローを避ける方法を一般的に書くべきですか？

Answer 1

問題は、実装がInt.intデータ型に依存していることです.SML/NJでは31ビットに制限されています（Int.precision参照）。つまり、計算できる値の上限があることを意味します。その両方*整数

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