haskell - Haskell 中的无限映射

Question

我正在写一些代码，我想我可以从一个无限的元组列表中创建一个无限的映射。类似于以下内容:Map.fromList [(i,i+1)|i<-[1..]]
当然，我立即发现 Data.Map 和 Data.Set 分别不支持无限 Maps 和 Sets。我注意到一个关于 Data.Set 的 fromList 贪婪实现的类似问题。 ，并且，在阅读了答案后here ，很明显，Set 既可以实现惰性实现也可以实现贪婪，只是贪婪的实现更好。但是，我真的不明白为什么 Map.fromList 的延迟实现行不通。与 key 的存储方式有关吗？

Answer 1

Data.Map被实现为平衡树(我认为大致是二元的)；如果没有对输入的一些预知，很难懒惰地创建和平衡无限二叉树!但是，您可能会喜欢 MemoTrie 之类的内容。包，它使用惰性无限尝试(位)代替。

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