6

我正在写一些代码，我想我可以从一个无限的元组列表中创建一个无限的映射。类似于以下内容： Map.fromList [(i,i+1)|i<-[1..]]

当然，我立刻发现 Data.Map 和 Data.Set 分别不支持无限 Maps 和 Sets。我注意到一个关于 Data.Set 的贪婪实现的类似问题fromList，并且在阅读了这里的答案之后，很明显 Set 可以实现惰性和贪婪，只是贪婪的实现更好。但是，我真的不明白为什么懒惰的实现Map.fromList不起作用。与密钥的存储方式有关吗？

4

1 回答 1

13

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

> let x = trie (\x -> x+1)
> untrie x 72
73
> untrie x 37
38
于 2012-04-21T19:44:35.370 回答