这个listArray是如何填充的?

在使用暴力解决方案正确回答了欧拉问题92后,我通过线程92阅读了其他的haskell解决方案。 最后一个解决方案速度非常快,但我对如何实现一个数组显示数字0到567是否归结为以1(False)或89(True)结尾的链条感到困惑。

import Data.List
import Data.Array
import Data.Char

b = (is89!) . sum . map ((^2) . digitToInt) . show
is89 = listArray (0, 567) $ False:False:(map b [2..88] ++ [True] ++ map b [90..567])

我以为我理解了haskell的惰性以及它可以使用列表中的先前值来生成未来值的方式,例如生成素数,斐波那契数等。 但在这种情况下,索引似乎跳舞(在0到567的范围内)并且我迷失了索引的值如何结束False或True。

例如,第一个映射中的第一个值是2,当平方和求和时为4.但索引4尚未预先填充。 就我所见,预先填充的唯一值是0,1和89。

有人可以慢慢地告诉我如何填充这个数组

采纳答案:

Haskell的懒惰也只是计算每个值一次,而这个数组是一种相当经典的memoization技术。

所以我们被要求计算is89 ! 2 is89 ! 2 ,我们检查数组并看到元素尚未被评估,然后我们按照定义看到要评估它,我们需要评估is89 ! 4 is89 ! 4 ,所以我们这样做。 我们再次检查数组,看看它还没有被评估。 依此类推,我们检查58 ,然后最终到达89 ,我们检查数组并看到该值已被评估! (根据定义,它是True )。 然后我们回溯并更新索引58以便“被评估”并包含True ,依此类推372 ,这就是我们返回并说我们被问到的值是True

下次,假设我们被问到是is89 ! 11 is89 ! 11 ,我们检查数组,看看它还没有评估,我们需要is89 ! 2 is89 ! 2 ,但我们已经评估过那个! 所以我们只使用过去的评估结果。

最后,我们实现了一个查找表,该表只填充了所需的值,即memoization。

author: mniip

参考更多解答: How is this listArray populated? ,转载请保留出处这个listArray是如何填充的?及作者信息

Statement: We respect knowledge and authors. Since the content comes from the Internet and is intended for scientific research, any reprinters should retain the author's signature and origin. If you are the author of the content and feel in dispute, please contact email: 1076545519@qq.com. We will find out the situation and deal with it in time. We sincerely thank the author for his hard work.


更多:haskell