Bản đồ vô hạn trong Haskell

Question

Tôi đã viết một số mã và tôi đã tìm ra rằng tôi có thể tạo một bản đồ vô hạn từ một danh sách vô hạn các bộ dữ liệu. Nội dung nào đó dọc theo các dòng sau: Map.fromList [(i,i+1)|i<-[1..]]

Tất nhiên, tôi đã phát hiện ra ngay lập tức rằng Data.Map và Data.Set không hỗ trợ Bản đồ và Bộ vô hạn tương ứng. Tôi nhận thấy một câu hỏi tương tự về việc thực hiện tham lam của Data.Set fromList, và sau khi đọc qua các câu trả lời here, rõ ràng là cả việc triển khai lười biếng và tham lam đều có thể cho Set, chỉ là những tham lam hoạt động tốt hơn. Tôi không thực sự hiểu, tuy nhiên, tại sao việc thực hiện lười biếng của Map.fromList sẽ không hoạt động. Một cái gì đó để làm với các phím được lưu trữ như thế nào?

Answer 1

Data.Map được triển khai dưới dạng cây cân bằng (khoảng nhị phân, tôi nghĩ); thật khó để tạo và cân bằng cây nhị phân vô hạn một cách uể oải mà không cần phải biết trước về đầu vào! Tuy nhiên, bạn có thể thích một cái gì đó giống như gói MemoTrie, trong đó sử dụng cố gắng vô hạn lười (bit) để thay thế.

> let x = trie (\x -> x+1) 
> untrie x 72 
73 
> untrie x 37 
38