Tại sao đôi khi GHC từ chối lười biếng?

Question

Điều này đi vào vòng lặp vô hạn trên tryhaskell.org. Tôi không chắc tại sao.

last $ filter (<100) $ [2..] >>= (\a -> if 0 == (length $ filter (== 0) $ map (mod a) $ [2..a-1]) then (return a) else []) 

Answer 1

Nó không từ chối được lười biếng, nó chỉ là không có cách nào cho nó để biết rằng sau khi bạn nhận được tất cả các số nguyên tố < 100, không có bất kỳ hơn.

gì nếu chuỗi trông giống như

1, 2, ... 99, 100, 101, 102, 5, 103, ...

Nói cách khác, last không thể dự đoán Tương lai. Oh tôi ước gì.

Answer 2

Hãy tách rời mọi thứ, làm việc từ trong ra ngoài. Bắt đầu từ điều này:

last $ filter (<100) $ [2..] >>= (\a -> if 0 == (length $ filter (== 0) $ map (mod a) $ [2..a-1]) then (return a) else []) 

Đầu tiên xem xét map (mod a) [2..a-1]. Đây chỉ là một biến đổi của một danh sách hữu hạn, do đó, không có vấn đề ở đây, và chúng tôi sẽ bỏ qua nó từ đây, đặt [..] vào vị trí của nó. Vì chúng tôi chỉ quan tâm đến việc chấm dứt, mọi danh sách hữu hạn đều tốt như danh sách khác.

Tương tự với số filter (== 0) [...]. Điều này chỉ có thể làm cho danh sách ngắn hơn, vì vậy chúng tôi có thể kết thúc với một danh sách trống để thay thế, nhưng chắc chắn hữu hạn. Vì vậy, bỏ qua điều này là tốt. Bây giờ hãy xem xét length [..] - chúng tôi biết danh sách là hữu hạn, vì vậy điều này sẽ chấm dứt tốt, đưa ra một số câu trả lời từ 0 trở lên. Chúng tôi sẽ bỏ qua câu trả lời cụ thể và đặt ? vào vị trí của nó. Vẫn còn tốt cho đến nay.

Lambda \a -> if 0 == ? then return a else [] đang sử dụng return trong danh sách đơn nguyên, vì vậy đây thay thế a với một trong hai [a] hoặc [], đó là tình cờ tương đương với Maybe, nhưng đó là một vấn đề khác. Một lần nữa, chúng tôi biết điều này sẽ hiệu quả, vì vậy chúng tôi bỏ qua các chi tiết và sử dụng \a -> [a?].

Liên kết đơn lẻ [2..] >>= \a -> [a?] thú vị hơn. (>>=) ở đây là concatMap và đối số đầu tiên là danh sách vô hạn. Ánh xạ từng phần tử vào một danh sách singleton và ghép nối rõ ràng là không có gì thay đổi, trong khi ánh xạ tới danh sách trống sẽ loại bỏ một phần tử, do đó, về cơ bản chỉ là filter. Tuy nhiên, đây không phải là không phải là vì chúng tôi đang lọc danh sách vô hạn mà không đảm bảo chắc chắn rằng mọi thứ sẽ vượt qua bộ lọc. Nếu bạn làm filter (const False) [0..] thì "kết quả" sẽ không có phần tử nào, nhưng việc tính toán sẽ không bao giờ kết thúc; các [] trong đầu ra của filter xuất phát từ việc tìm kiếm kết thúc của danh sách đầu vào, và điều này không có, và vì nó sẽ không bao giờ tìm thấy một yếu tố đầu tiên, kết quả chỉ là _|_.

Vì vậy, mọi thứ đã có vấn đề. Phần tiếp theo, filter (<100), làm cho mọi thứ tồi tệ hơn - chúng tôi lọc các phần tử ra khỏi danh sách nghiêm ngặt, sau đó lọc nó dựa trên một số giá trị, do đó, bằng đối số trên nếu chúng ta đi qua 100 trong kết quả tính toán sẽ treo.

Và sỉ nhục cuối cùng là last --Thư danh sách trong câu hỏi là vẫn vô hạn, nhưng sẽ bất đồng tại một số điểm chứ không phải là tạo ra nhiều yếu tố, vì vậy khi chúng tôi yêu cầu cho các phần tử cuối cùng chúng ta có thể thấy rằng nó sẽ thất bại trong việc chấm dứt cho nhiều lý do!

Điều bạn muốn làm ở đây trước hết là áp dụng kiến ​​thức của bạn rằng danh sách đang tăng lên và thay vì lọc danh sách, chỉ cần đặt tiền tố lên đến điểm mong muốn - ví dụ: takeWhile (<100) hơn filter (< 100). Lưu ý rằng điều này sẽ vẫn phân kỳ nếu không có phần tử nào lớn hơn 100 trong kết quả, vì takeWhile sẽ không biết thời điểm dừng.