Haskell không đánh giá Lazily takeWhile

Question

isqrt :: Integer -> Integer 
isqrt = floor . sqrt . fromIntegral 

primes :: [Integer] 
primes = sieve [2..] where 
sieve (p:ps) = p : sieve [x | x <- ps, x `mod` p > 0] 

primeFactors :: Integer -> [Integer] 
primeFactors n = takeWhile (< n) [x | x <- primes, n `mod` x == 0] 

Đây là mã của tôi. Tôi nghĩ rằng bạn đoán những gì tôi đang cố gắng làm: Một danh sách các yếu tố chính của một số cho trước bằng cách sử dụng danh sách vô hạn các số nguyên tố. Nhưng mã này không đánh giá uể oải.

Khi tôi sử dụng ghci và :l mycode.hs và nhập primeFactors 24, kết quả là [2, 3 (và con trỏ liên tục nhấp nháy ở đó) không có thêm Prelude> nhắc. Tôi nghĩ có vấn đề ở đó. Tôi đang làm gì sai?

Cảm ơn.

Answer 1

takeWhile không bao giờ chấm dứt đối số hỗn hợp. Nếu n là hỗn hợp, nó không có các yếu tố chính >= n, vì vậy takeWhile sẽ chỉ ngồi ở đó.

Áp dụng takeWhile vào danh sách số nguyên tố và sau đó lọc kết quả với n mod x, như thế này:

primeFactors n = [x | x <- takeWhile (<= n) primes, n `mod` x == 0] 

(<= được sử dụng thay vì < cho đúng đắn tối đa, do đó thừa số nguyên tố của một số nguyên tố sẽ bao gồm số đó).

Answer 2

Có một minh chứng về những gì sẽ xảy ra:

http://sketchtoy.com/67338195

Answer 3

Vấn đề của bạn không phải là trực tiếp takeWhile, mà là danh sách hiểu.

[x | x <- primes, n `mod` x == 0] 

Đối n = 24, chúng tôi nhận 24 `mod` 2 == 0 và 24 `mod` 3 == 0, vì vậy giá trị của danh sách hiểu này bắt đầu với 2 : 3 : .... Nhưng hãy xem xét phần ....

Việc hiểu danh sách phải tiếp tục kéo các giá trị từ primes và kiểm tra 24 `mod` x == 0. Vì không còn yếu tố chính nào của 24, sẽ không có gì vượt qua bài kiểm tra đó và được phát ra như là giá trị thứ ba của việc hiểu danh sách. Nhưng vì luôn có một nguyên tố khác để kiểm tra, nó sẽ không bao giờ dừng lại và kết luận rằng đuôi còn lại của danh sách trống.

Bởi vì điều này được đánh giá rất lười biếng, nếu bạn chỉ yêu cầu hai yếu tố đầu tiên của danh sách này thì bạn ổn. Nhưng nếu chương trình của bạn có nhu cầu thứ ba (hoặc thậm chí chỉ biết có hay không có là yếu tố thứ ba), thì việc hiểu danh sách sẽ chỉ xoay vòng mãi mãi để tìm ra.

takeWhile (< 24) tiếp tục kéo các phần tử khỏi đối số của nó cho đến khi tìm thấy phần tử không phải là < 24. 2 và 3 cả hai đều vượt qua bài kiểm tra đó, vì vậy takeWhile (< 24)không cần phải biết yếu tố thứ ba của việc hiểu danh sách là gì.

Nhưng nó không thực sự là vấn đề với takeWhile; vấn đề là bạn đã viết một danh sách hiểu để tìm tất cả các yếu tố chính (và không có gì khác), và sau đó cố gắng sử dụng một bộ lọc trên các kết quả để cắt đứt sự khám phá vô tận của tất cả các số nguyên tố cao hơn không thể là yếu tố.Điều đó không thực sự có ý nghĩa nếu bạn dừng lại để suy nghĩ về nó; theo định nghĩa, bất kỳ thứ gì không phải là yếu tố chính không thể là thành phần của danh sách đó, do đó bạn không thể lọc ra các yếu tố không lớn hơn n từ danh sách đó. Thay vào đó, bạn cần lọc đầu vào để hiểu danh sách đó để nó không cố gắng khám phá một không gian vô hạn, như câu trả lời của @ n.m.