2

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

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

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

关于如何解决这个问题的任何建议？

谢谢。

PS：我不是要对 Project Euler 问题的答案，我只是想更好地了解 Haskell！

4

1 回答 1

7

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

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

于 2012-06-04T19:23:02.557 回答