Dlaczego to wyrażenie Haskella jest takie wolne?

Question

Pracuję nad projektem Euler Problem 14. Oto moje rozwiązanie.

import Data.List 

collatzLength :: Int->Int 
collatzLength 1 = 1 
collatzLength n | odd n = 1 + collatzLength (3 * n + 1) 
       | even n = 1 + collatzLength (n `quot` 2) 

maxTuple :: (Int, Int)->(Int, Int)->Ordering 
maxTuple (x1, x2) (y1, y2) | x1 > y1 = GT 
       | x1 < y1 = LT 
       | otherwise = EQ 

biegnę następujące z GHCi

maximumBy maxTuple [(collatzLength x, x) | x <- [1..1000000]] 

wiem, że jeśli Haskell ocenia surowo, czas na to byłoby coś podobnego O (n). Ponieważ Haskell ocenia leniwie, wydaje się, że powinno to być ciągłe wielokrotne n. To trwa już prawie godzinę. Wydaje się bardzo nierozsądne. Czy ktoś ma jakiś pomysł, dlaczego?

Answer 1

Zakłada się, że funkcja collatzLength zostanie zapamiętana. Haskell nie wykonuje automatycznej zapamiętywania. Musisz to zrobić sam. Oto przykład użycia pakietu data-memocombinators.

import Data.List 
import Data.Ord 
import qualified Data.MemoCombinators as Memo 

collatzLength :: Integer -> Integer 
collatzLength = Memo.arrayRange (1,1000000) collatzLength' 
    where 
    collatzLength' 1 = 1 
    collatzLength' n | odd n = 1 + collatzLength (3 * n + 1) 
        | even n = 1 + collatzLength (n `quot` 2) 

main = print $ foldl1' max $ [(collatzLength n, n) | n <- [1..1000000]] 

To trwa około 1 sekundy, gdy skompilowano z -O2.

Answer 2

Aby można było znaleźć maksymalną listę, należy dokonać oceny całej listy.

Więc to obliczy collatzLength od 1 do 1000000 i collatzLength jest rekurencyjne. Najgorsze jest to, że twoja definicja collatzLength nie jest nawet rekurencyjna.

Answer 3

cL jest skrótem collatzLength

cL!!n podpórek collatzLength n

cL :: [Int] 
cL = 1 : 1 : [ 1 + (if odd n then cL!!(3*n+1) else cL!!(n `div` 2)) | n <- [2..]] 

prosty test:

ghci> cL !! 13 
10