Tại sao `fix` của haskell có vẻ gặp rắc rối với bộ dữ liệu?

Question

Tôi đang cố uốn cong đầu quanh các điểm cố định và các định nghĩa đệ quy.

này hoạt động:

>>> take 10 $ let x = (0:x) in x 
[0,0,0,0,0,0,0,0,0,0] 

này làm điều tương tự, có ý nghĩa đưa ra định nghĩa của fix:

>>> take 10 $ fix (\x -> (0:x)) 
[0,0,0,0,0,0,0,0,0,0] 

Bây giờ giả sử tôi bắt đầu rối tung xung quanh với cặp đệ quy định nghĩa:

>>> take 10 $ fst $ let (u,v) = (0:v,1:u) in (u,v) 
[0,1,0,1,0,1,0,1,0,1] 

OK, tôi sẽ có thể viết điều đó với fix quá, phải không?

>>> take 10 $ fst $ fix (\(u,v) -> (0:v,1:u)) 
*** Exception: <<loop>> 

Nhưng nó không hoạt động. Trừ khi tôi thực hiện thay đổi có vẻ nhỏ bé như sau:

>>> take 10 $ fst $ fix (\r -> let (u,v)=r in (0:v,1:u)) 
[0,1,0,1,0,1,0,1,0,1] 

Sự khác biệt quan trọng giữa hai ví dụ cuối cùng là gì?

Answer 1

Bạn muốn

take 10 $ fst $ fix (\ ~(u,v) -> (0:v,1:u)) 
         ^^^ 

để thực hiện các mô hình phù hợp với lười biếng. Trong let, mẫu LHS hoàn toàn lười biếng/không thể chối cãi.

Với đồng bằng \(u,v) -> ... đối số của lambda sẽ được yêu cầu trước khi bất kỳ đầu ra nào được tạo ra - điều này làm cho hàm quá nghiêm ngặt đối với fix. Những gì bạn cần là một cái gì đó như

take 10 $ fst $ fix (\p -> (0:snd p,1:fst p)) 

để đối số không bị ép buộc bởi lambda (không có hàm tạo nào phù hợp). Cách tiếp cận mẫu lười biếng tương đương với fst/snd ở trên.