Tại sao chức năng đệ quy này trong Haskell quá chậm?

Question

Tôi đang cố gắng bắt chước Sàng để tìm tất cả số nguyên tố ít hơn một số bằng cách sử dụng Haskell. Tôi đã tìm thấy chương trình Haskell khác sử dụng phương pháp Sieve với tốc độ tuyệt vời. Tuy nhiên chức năng đệ quy sau tôi đã viết là rất chậm. Mã như sau

sieve' :: Integer -> Integer -> [Integer] 

sieve' n 1 = [2 .. n] 

sieve' n (k + 1) | [x | x <- sieve' n k, x == k + 1] == [] = sieve' n k 

    |otherwise = [x | x <- sieve' n k, x == k + 1 || not (mod x (k + 1) == 0)] 



sieve :: Integer -> [Integer] 

sieve n = sieve' n n 

Rây 20 mất khoảng 2 phút. Rây 30 vẫn chưa kết thúc trong khi tôi đang viết câu hỏi này.

Bất cứ ai có thể giải thích tại sao hàm đệ quy này quá chậm. Cảm ơn vì bất kì sự giúp đỡ nào của bạn.

Answer 1

Điều khoản thứ hai của bạn là sieve' chức năng đang thực hiện cuộc gọi đệ quy (sieve' n k) hai lần, do đó làm cho thuật toán của bạn hoạt động theo thời gian.

Để khắc phục vấn đề này bạn có thể ràng buộc hạn đối với một số tên, do đó đảm bảo nó được đánh giá một lần:

sieve' n (k + 1) | [x | x <- rec, x == k + 1] == [] = rec 
    |otherwise = [x | x <- rec, x == k + 1 || not (mod x (k + 1) == 0)] 
    where 
    rec = sieve' n k 

Cập nhật để đáp ứng với một lời nhận xét hỏi tại sao các trình biên dịch không làm điều này tự động:

Loại chuyển đổi này, được gọi là CSE (loại trừ biểu hiện chung), không phải là tối ưu hóa nói chung, mà là một sự cân bằng giữa sử dụng thời gian và không gian, vì vậy quyết định tốt hơn cho lập trình viên.

Googling cho "CSE" tiết lộ một số cuộc thảo luận thú vị, một trong số đó tham chiếu this very good example từ năm 1987 cuốn sách của Simon Peyton Jones gọi là "Thực hiện chức năng lập trình Ngôn ngữ" (Ôi, cuốn sách này là gần như cũ như tôi)