使用 Data.Map 实现 Haskell 中的动态规划？

Question

我正在尝试在Haskell中实现一个简单的动态规划算法（这是针对欧拉计划中的Collatz猜想问题）；以下是相应的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')

我觉得我在这里只是重新实现了一个状态单子，但暂且不管那个。调用solve的代码试图找到它可以为参数提供的最大值，最多为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')

在 solve 的最后一行加上代码并没有任何改变（仍然是栈溢出）。然后我尝试使用

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

这个过程非常缓慢，可能是因为deepseq遍历整个map mem''，使算法的时间复杂度从n*log(n)变成了二次方。

正确的实现方式是什么？我卡住了，因为我无法弄清楚如何使整个计算过程严格，并且我不太确定计算的哪个部分会导致堆栈溢出，但我怀疑是map。例如，我可以使用数组，但我想要理解我在这里做错了什么。

- Kirill

---

“Correct” 是什么意思？ - Robert Harvey

我的意思是一个大致相当于我心目中的（c++）版本，但不会因为堆栈溢出而失败。 - Kirill

Answer 1

当你使用32位有符号整数类型时，堆栈溢出问题将无法解决。对于某些起始值，链条会离开32位范围并进入负数的无限循环中。请使用Integer、Int64或Word64。

- Daniel Fischer

---

糟糕，我的错。使用Integer/Int64时比C++慢了五倍，但不会失败。没关系，谢谢。 - Kirill

你的元组看起来不够严格，即使你使用了 foldl'，尝试添加一些 ! 严格性标签。对于 Haskell 来说，五倍慢听起来还不错。 - Jeff Burdges

@JeffBurdges 对于 seq 来说，它已经足够严格了。如果用于查找最长链，则 maximum 可能过于懒惰。但是，没有任何严格性可以防止无限循环。 - Daniel Fischer