HaskellのData.Mapによる動的プログラミング？

Question

私はHaskellで単純なdpアルゴリズムを実装しようとしています（これはProject EulerのCollat​​z推測問題です）。ここでは同等のC++は次のとおりです。

map<int,int> a; 
int solve(int x) { 
    if (a.find(x) != a.end()) return a[x]; 
    return a[x] = 1 + /* recursive call */; 
} 

だから私はHaskellで書いたコードは次のように見てしまった：

solve :: (Memo, Int) -> (Memo, Int) 
solve (mem, x) = 
case Map.lookup x mem of 
    Just l -> (mem, l) 
    Nothing -> let (mem', l') = {- recursive call -} 
       mem'' = Map.insert x (1+l') mem' 
      in (mem'', 1+l') 

（私は決して私はちょうどここStateモナドを再実装だと思いませんが、一瞬のためにそれを気にし）、それはほとんどのK = 1E6のパラメータに与えることができる最大値を見つけようとするの解決呼び出すコード：

foldl' 
(\(mem,ss) k -> 
    let (mem',x') = solve (mem, k) 
    in (mem', (x', k):ss)) 
(Map.singleton 1 1, [(1,1)]) [2..100000] 

上に書いたように、コードがスタックオーバーフローで失敗が。それは本当に大きな未評価のサンクを構築するので、これは予想される、私は理解する。だから私は使用しようとしました

x' `seq` (mem', (x',k):ss) 

foldl 'の中で、それはK = 1e5の正解を計算します。しかし、これはK = 1e6（12秒でスタックオーバーフロー）に失敗します。それで解決の最後の行で

mem'' `seq` l' `seq` (mem'', 1+l') 

を使ってみましたが、これは違いはありません（スタックオーバーフローがまだあります）。それから私は、これはdeepseqではなく、n * log（n）のアルゴリズムの時間計算量は二次作り、MEM「」は、マップ全体をウォークスルーおそらくので、非常に遅いです

mem'' `deepseq` l' `seq` (mem'', 1+l') 

を使用してみました。

これを実装する正しい方法は何ですか？私は計算全体を厳密にする方法を理解することができず、計算のどの部分がスタックオーバーフローをもたらすのかは確かではありませんが、マップであると思われます。私は配列などを使うことができましたが、ここで間違っていることを理解したいと思います。

Answer 1

32ビット符号付き整数型を使用している間は、スタックオーバーフローがなくなりません。一部の開始値では、チェーンは32ビットの範囲を離れ、負の数の無限ループを入力します。 IntegerまたはInt64またはWord64を使用してください。