Haskell中的无限地图

Question

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

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

Answer 1

Data.Map实现为一个平衡的树(大概是二进制的,我认为); 如果没有对输入的一些预知,很难懒惰地创建和平衡无限二叉树!但是,您可能喜欢MemoTrie包,它使用惰性无限尝试(位).

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