在Haskell中使用Data.Map進行動態編程？

我想在Haskell中實現一個簡單的dp算法（這是來自Project Euler的Collatz猜想問題）;這裏是等價的C++：在Haskell中使用Data.Map進行動態編程？

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

（我認爲我只是重新實現狀態單子這裏，但從來沒有介意的時刻），這就要求解決試圖尋找它可給最多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]

如上所寫的代碼失敗堆棧溢出。據我瞭解，這是預料之中的，因爲它構成了一個非常大的未評估的thunk。所以我嘗試使用

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

inside foldl'，它計算出K = 1e5的正確答案。但是K = 1e6（堆棧在12秒內溢出）失敗。然後我嘗試使用

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

在解決的最後一行，但這沒有什麼區別（堆棧溢出仍然）。然後我試圖使用

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

這是非常慢的，大概是因爲deepseq遍歷整個地圖MEM「」，使得算法的時間複雜二次代替的n * log（n）的。

什麼是正確的方式來實現呢？我被卡住了，因爲我無法弄清楚如何嚴格執行整個計算，而且我不太確定計算的哪一部分會導致堆棧溢出，但我懷疑它是地圖。我可以使用例如數組，但我想知道我在這裏做錯了什麼。

來源

2012-04-10 Kirill

你是什麼意思「正確？」 – 2012-04-10 05:53:35

我的意思是大致相當於我想到的（C++）版本，但不會因堆棧溢出而失敗。 – Kirill 2012-04-10 06:00:08

當您使用32位有符號整數類型時，堆棧溢出不會消失。對於某些起始值，鏈條離開32位範圍並進入無限循環的負數。使用Integer或Int64或Word64。

來源

2012-04-10 06:18:16

啊，我的壞。它比使用Integer/Int64的C++慢5倍，但不會失敗。沒關係。謝謝。 – Kirill 2012-04-10 06:27:28

即使使用'foldl'，你的元組也不夠嚴格，嘗試添加一些'！'嚴格標籤。實際上Haskell的速度慢了五倍。 – 2012-04-10 13:43:43

@JeffBurdges隨着'seq's的嚴格。儘管如此，「最大值」可能太懶惰，如果這被用來找到最長的鏈。但沒有嚴格規定有助於防止無限循環。 – 2012-04-10 13:51:37

在Haskell中使用Data.Map進行動態編程？

回答

相關問題