¿Por qué esta expresión de Haskell es tan lenta?

Question

Estoy trabajando en el problema 14 de Project Euler. Aquí está mi solución.

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 

estoy ejecutando el siguiente de GHCi

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

Sé que si Haskell evaluado rigurosamente, el tiempo en esto sería algo así como O (n). Sin embargo, dado que Haskell evalúa perezosamente, parece que debería ser un múltiplo constante de n. Esto ha estado funcionando por casi una hora ahora. Parece muy irrazonable. ¿Alguien tiene alguna idea de por qué?

Answer 1

Suponiendo que la función collatzLength se memorizará. Haskell no hace memoria automática. Tendrás que hacer eso tú mismo. Aquí hay un ejemplo usando el paquete 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]] 

Esto ejecuta en aproximadamente 1 segundo cuando se compila con -O2.

Answer 2

Para poder encontrar el máximo de una lista, se debe evaluar toda la lista.

Así que se calculará collatzLength de 1 a 1000000 y collatzLength es recursivo. Lo peor es que su definición de collatzLength ni siquiera es recursiva.

Answer 3

cL es la abreviatura de collatzLength

cL!!n gradas para collatzLength n

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

Prueba simple:

ghci> cL !! 13 
10