Tại sao đoạn mã Haskell này không phải đệ quy vô hạn?

Question

Để giúp tôi tìm hiểu Haskell, tôi đang làm việc thông qua các vấn đề trên Project Euler. Sau khi giải quyết từng vấn đề, tôi kiểm tra giải pháp của mình chống lại Haskell wiki trong một nỗ lực để tìm hiểu các phương pháp mã hóa tốt hơn. Dưới đây là the solution-problem 3:

primes = 2 : filter ((==1) . length . primeFactors) [3,5..] 

primeFactors n = factor n primes 
    where 
    factor n (p:ps) 
     | p*p > n  = [n] 
     | n `mod` p == 0 = p : factor (n `div` p) (p:ps) 
     | otherwise  = factor n ps 

problem_3 = last (primeFactors 317584931803) 

đọc ngây thơ của tôi của việc này là primes được định nghĩa về primeFactors, được xác định theo primes. Vì vậy, việc đánh giá primeFactors 9 sẽ thực hiện theo quy trình này:

1. Đánh giá factor 9 primes.
2. Yêu cầu primes cho phần tử đầu tiên, là 2.
3. Yêu cầu primes cho phần tử tiếp theo của nó.
4. Là một phần của quá trình này, hãy đánh giá primeFactors 3.
5. Yêu cầu primes cho phần tử đầu tiên, là 2.
6. Yêu cầu primes cho phần tử tiếp theo của nó.
7. Là một phần của quá trình này, hãy đánh giá primeFactors 3.
8. ...

Nói cách khác, các bước 2-4 sẽ lặp lại vô hạn. Rõ ràng là tôi đã nhầm lẫn, khi thuật toán kết thúc. Tôi đang làm gì ở đây?

Answer 1

primeFactors chỉ bao giờ đọc đến căn bậc hai của số mà nó đang đánh giá. Nó không bao giờ trông xa hơn trong danh sách, có nghĩa là nó không bao giờ "bắt kịp" với số mà nó đang thử nghiệm để đưa vào danh sách. Bởi vì Haskell là lười biếng, điều này có nghĩa là kiểm tra primeFactors không chấm dứt.

Điều khác cần nhớ là primes không phải là một hàm đánh giá danh sách mỗi khi bạn truy cập vào danh sách đó, mà là danh sách được xây dựng một cách lười biếng. Vì vậy, khi phần tử thứ 15 đã được truy cập một lần, truy cập vào phần tử thứ hai là "miễn phí" (ví dụ: nó không yêu cầu thêm bất kỳ phép tính nào).

Answer 2

primeFactors 3 không yêu cầu primes cho các phần tử tiếp theo của nó, chỉ là người đầu tiên, bởi vì 2*2 lớn hơn 3 đã

Answer 3

câu trả lời của Kevin là đạt yêu cầu, nhưng cho phép tôi để xác định các lỗ hổng trong logic của bạn. Đó là # 6 đó là sai. Vì vậy, chúng tôi đang đánh giá primeFactors 3:

primeFactors 3   ==> 
factor 3 primes   ==> 
factor 3 (2 : THUNK) ==> 
2*2 > 3 == True   ==> 
[3] 

Các thunk cần không bao giờ được đánh giá để xác định rằng primeFactor 3 là [3].