Вопросы, касающиеся решения Haskell Project Euler 14

Question

Это Question 14.

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 Report states, «array строго по аргументу границ и по индексам списка ассоциаций, но нестрогий в значениях». listArray аналогичен.

Что это означает, что структура массива создается сразу – т.е. п«клеток», которые хранятся значения – но и значения сами ленивы, как это обычно бывает в Хаскелле.

определение вашей функцией, упрощена, является

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.