Tại sao biểu thức Haskell này lại quá chậm?

Question

Tôi đang làm việc với Project Euler Problem 14. Đây là giải pháp của tôi.

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 

Tôi đang chạy sau ra khỏi GHCi

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

Tôi biết rằng nếu Haskell đánh giá nghiêm ngặt, thời gian trên đây sẽ là một cái gì đó như O (n). Kể từ khi Haskell đánh giá lazily mặc dù, nó có vẻ như thế này nên được một số liên tục nhiều n. Điều này đã được chạy gần một giờ rồi. Có vẻ rất không hợp lý. Có ai có bất kỳ ý tưởng tại sao?

Answer 1

Bạn giả sử rằng chức năng collatzLength sẽ bị ghi nhớ. Haskell không tự động ghi nhớ. Bạn sẽ cần phải làm điều đó cho mình. Dưới đây là ví dụ sử dụng gói 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]] 

Điều này chạy trong khoảng 1 giây khi được biên dịch với -O2.

Answer 2

Để có thể tìm tối đa danh sách, toàn bộ danh sách cần được đánh giá.

Vì vậy, nó sẽ tính collatzLength từ 1 đến 1000000 và collatzLength là đệ quy. Điều tồi tệ nhất là, định nghĩa của bạn về collatzLength thậm chí không phải là đệ quy đuôi.

Answer 3

cL là viết tắt của collatzLength

cL!!n đứng cho collatzLength n

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

đơn giản kiểm tra:

ghci> cL !! 13 
10