haskell - 已知缓存的功能替代方案 "answers"

Question

我认为形成这个问题的最好方法是举一个例子......所以，我决定问这个问题的实际原因是因为 Problem 55 on Project Euler 。在该问题中，要求找到 10,000 以下的 Lychrel 数的数量。在命令式语言中，我将获取导致最终回文的数字列表，并将这些数字推送到我的函数之外的列表中。然后，我会检查每个传入的号码，看看它是否属于该列表的一部分，如果是，则只需停止测试并得出结论，该号码不是 Lychrel 号码。我会对非 lychrel 数字及其前面的数字做同样的事情。

我以前做过这个，效果很好。然而，在 Haskell 中实际实现这一点似乎是一个很大的麻烦，而不向我的函数添加一堆额外的参数来保存前辈，以及一个绝对父函数来保存我需要存储的所有数字。

我只是想知道我是否缺少某种工具，或者是否有任何标准可以做到这一点？我读过 Haskell 那种“自然缓存”(例如，如果我想将奇数定义为 odds = filter odd [1..]，我可以随时引用它，但是当我需要动态地将元素添加到列表中时，它似乎变得复杂。

关于如何解决这个问题有什么建议吗？

谢谢。

PS:我不是在寻求 Project Euler 问题的答案，我只是想更好地了解 Haskell!

Answer 1

我相信您正在寻找memoizing 。有多种方法可以做到这一点。一种相当简单的方法是使用 MemoTrie包裹。或者，如果您知道您的输入域是一组有界数字(例如 [0,10000))，您可以创建一个数组，其中的值是您的计算结果，然后您可以使用您的输入对数组进行索引。不过，数组方法对您不起作用，因为即使您的输入数字低于 10,000，后续迭代也可能会轻松地增长到超过 10,000。

也就是说，当我用 Haskell 解决问题 55 时，我并没有费心做任何内存。事实证明，它的速度足以对所有输入数字运行(最多)50 次迭代。事实上，现在在我的机器上运行它需要 0.2 秒才能完成。