关于 Haskell Project Euler 14 解决方案的问题

Question

import Data.Array
import Data.List
import Data.Ord (comparing)

syrs n = a
  where 

    -- For those who don't want to lookup array in the reference
    -- the following line creates an array indexed from 1 to n 
    -- using the list provided. And a ! x is the syntax for a[x] in some other languages.

    a = listArray (1,n) $ 0 : [1 + syr n x | x <- [2..n]]   -------- 2
    syr n x = if x' <= n                                    -------- 1
            then a ! x'                                     -------- 1
            else 1 + syr n x'                               
      where 
        x' = if even x
             then x `div` 2
             else 3 * x + 1

main = print $ maximumBy (comparing snd) $ assocs $ syrs 1000000

以上是 Project Euler Q14 on wiki.haskell.org 的建议解决方案。该算法与我的算法大致相同（但我的算法会永远运行，而它会在 2 秒内运行）。

问题：

在第 2 行中，它调用 syr n x。假设x = 3、x' = 10、10 < n，它将继续then子句：a ! 10。但是此时，a ! 10还没有计算出来。那么程序如何进行呢？

Answer 1

Haskell98 报告 states, " array 在边界参数和关联列表的索引中是严格的，但在值中是非严格的" 。 listArray 相似。

这意味着立即创建数组的结构 – 即 n "cells" 用来保存值——但是 values 本身是惰性的，这在 Haskell 中很常见。

您的函数的简化定义是

import Data.Array
import Data.List
import Data.Ord (comparing)

syrs n = 
    a
    where 
    a = listArray (1,n) $ 0 : map syr [2..n]
    syr x = 
        if y <= n then 1 + a ! y else 1 + syr y
        where 
        y = if even x then x `div` 2 else 3 * x + 1

有了它，

a ! i === (0 : map syr [2..n]) !! (i-1) , i = 1..n
      === if i==1 then 0
                  else (map syr [2..n]) !! (i-2) , i = 2..n
      === if i==1 then 0
                  else syr i

当a ! 10的值需要时，根据上面的定义计算，然后存储在数组10下标a。计算它将以通常的方式进行，即。 a ! 5会被求出，触发其计算，有条件地将结果存入数组。

所以，在伪代码中，

syr x = a ! x     , if already calculated and stored in the array
      = 1 + syr y , storing the result in the array under x, if x <= n
      = 1 + syr y , otherwise
  where
  y = ....

Haskell.

的常规递归惰性求值

关于 Haskell Project Euler 14 解决方案的问题

Questions regarding Haskell solution of Project Euler 14

haskell

lazy-evaluation

memoization