2

This is the 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

Above is the suggested solution for Project Euler Q14 on wiki.haskell.org. The algorithm is largely the same to mine (but mine runs forever while this runs in 2sec).

Question:

In line 2, it calls syr n x. Suppose x = 3, x' = 10, 10 < n, it will proceed with then clause : a ! 10. But at this time, a ! 10 is not yet calculated. How does the program proceed then?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
pspencil
  • 295
  • 1
  • 10
  • 1
    Do ya wanna sort out that formatting? I don't think many people can read it... – AJF Sep 13 '15 at 15:26
  • @AJFarmar How should I sort out the formatting? Questions before code? – pspencil Sep 13 '15 at 15:38
  • If it were valid haskell code, that'd be nice, but I think I could do it for you now. I'll edit for a moment. – AJF Sep 13 '15 at 15:45
  • I guess he is talking about the indentation. But I would also simplify the code and drop "a": I would say `syrs n = listArray (1,n) ...` – Michael Sep 13 '15 at 15:46
  • 5
    Please post your own broken code in full. It's very hard to do mental multiple search/replace while reading code. – dfeuer Sep 13 '15 at 16:20
  • #14? That sounds... familiar: http://stackoverflow.com/questions/22416292/project-euler-14-tips-in-haskell. That being said, if you have _working_ code, http://codereview.stackexchange.com could be a better place. – Zeta Sep 13 '15 at 16:33
  • @AJFarmar Your edit changed the formatting from what was on the Haskell wiki. It's no longer a real quote. – melpomene Sep 13 '15 at 16:35
  • @Michael Actually that is my question 1. It turns out that adding `a` boosts performance in a way that I don't know. – pspencil Sep 14 '15 at 01:26
  • @pspencil - you should compile with `-O2` if you want to measure anything. 1) compiling with `-O2` has a bigger performance impact that wether you inline `a` or not. 2) If you compile with `-O2` I'm sure that it will not have any performance impact wether you inline `a` or not. 3) I'm still a Haskell beginner, so I cannot just answer all your questions... – Michael Sep 14 '15 at 05:50
  • @Michael I tried to compile with `ghc -O2 -o TEST TEST.hs`. I deleted a and changed `a ! x'` to `(syrs n) ! x'` (if this is what you mean). Before change, it finishes in 1 second. After, however, it did not finish in 1 minute, which I don't know why. – pspencil Sep 14 '15 at 08:03
  • By the way, when you say "mine runs forever", do you mean that it runs a long time, or that there's an infinite loop and it never terminates? – Justin L. Sep 14 '15 at 17:29
  • @JustinL. As my point 2 points out, I think there is an infinite loop. Bit by bit, I modified my code to look like what was given as the answer and at certain point, when those differ by the difference in point 2, there is an infinite loop error. (previously, there is no notification) – pspencil Sep 16 '15 at 06:44
  • ... and you still haven't included your code in the question. it is impossible to answer then. voting to close. SO is not your personal service (no offense intended), the Q&A entries must make sense on their own, to a casual reader 10 years from now. (to your question above, if you replace `a ! ...` with `(syrs n) ! ...`, you destroy memoization and cause recalculation, i.e. computation explosion. `a` stores the previously calculated result, without it there is no memoization. – Will Ness Sep 16 '15 at 12:24
  • your `syr` must be able to refer to _the same_ array when processing different arguments, so the results are stored in that array, and not recalculated; to be able to refer to the _same_ array you must _name_ it and refer to it by its name. ["if you name it, it will stay"](http://stackoverflow.com/a/11466959/849891). – Will Ness Sep 16 '15 at 12:31
  • @WillNess Thank you for your answer. As my program only differed from the given answer by tiny little details, I thought it would be better to point out those details than to leave it for you to spot the difference, not to mention the pain in corresponding variable names. Anyway, now, question 1 & 2 have already been solved and question 3 does not require my code so it doesn't matter now. I have re-edited the question. Is that clear enough now? (I want to keep the older questions as reference, but failed to find a strikethrough format). – pspencil Sep 17 '15 at 07:31
  • I've edited to remove all the irrelevant, draft stuff, to make the question specific. – Will Ness Sep 17 '15 at 11:01

1 Answers1

3

Haskell98 Report states, " array is strict in the bounds argument and in the indices of the association list, but nonstrict in the values". listArray is similar.

What this means is that the structure of an array is created right away – i.e. the n "cells" that are to hold the values – but the values themselves are lazy, as is usual in Haskell.

Your function's definition, simplified, is

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

With it,

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

When the value a ! 10 is needed, it is calculated according to the above definition, and then stored under the index 10 in the array a. Calculating it will proceed in the usual fashion, viz. a ! 5 will be demanded, triggering its calculation, and conditionally storing the result in the array.

So, in pseudocode,

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 = ....

The usual, recursive, lazy evaluation of Haskell.

Will Ness
  • 70,110
  • 9
  • 98
  • 181