haskell - Haskell 中的记忆化和 Project Euler Problem 15

Question

我一直在学习一些 Haskell，并边做项目欧拉问题边做。我并不真正关心欧拉问题的答案(我可以很高兴地用暴力破解，或者用其他语言来做)，而是方法。

我坚持在合理的时间内完成问题 15。它询问 20x20 网格中从左上角到右下角的非回溯路线的数量。 Link here

我想说，很明显这个想法是内存(sp？)函数，但我不太确定如何做到这一点。我用谷歌搜索，发现了this在 Haskell Cafe 上，我天真地尝试适应，但最终得到了:

memRoute :: (Int,Int) -> Int
memRoute (x,y) = fromJust $ lookup (x,y) $ map (\t -> (t,route t)) [(x,y) | x <- [0..20], y <- [0..20]]

route (0,0) = 0
route (_,0) = 1
route (0,_) = 1
route (x,y) = memRoute (x-1,y) + memRoute (x,y-1)

它看起来很糟糕，而且性能很糟糕(比幼稚的版本慢很多)。问题是我不太明白 Haskell 内存是如何工作的。

以我的代码为例，有人愿意解释一下a)为什么我的代码这么慢
b)应该如何完成(不使用可变变量，这是我遇到的解决方案)
c) 在这种情况下内存是如何工作的？

Answer 1

在我看来，“内存”被严重高估了。没有一刀切的内存技术(在任何编程中语言)将每个单例计算变成一般计算。每个问题你都要搞清楚并组织一些东西来控制您需要的内存量使用。

在本例中，要获取 n x m 矩形的路径数，您不需要记住所有较小矩形的总数，仅适用于在任一方向上小一步的矩形。因此，您可以逐行建立，忘记所有总计随着你的移动越来越小的矩形。

在 Haskell 中，惰性非常适合这种情况。它缓解了记录要记住的内容的所有工作以及忘记什么 - 只需计算一个无限网格的总数所有可能的矩形，然后让 Haskell 完成其余的工作。

对于零行，您只有底线。不管时间有多长，到达终点的路径只有一条，所以路径的数量是重复 1。

要根据上一行计算网格中的一行，请从 1 开始(无论你有多高，只有一条直下的路)，然后在每一步中将相应的条目添加到一起上一行和当前行中的上一步。总而言之，我们有:

iterate (scanl (+) 1 . tail) (repeat 1) !! 20 !! 20

它会在 GHCi 提示符下立即计算出答案。