Endless Maps in Haskell

Question

I wrote the code, and I decided that I could create an infinite map from an endless list of tuples. Something like the following: Map.fromList [(i,i+1)|i<-[1..]]

Of course, I immediately discovered that Data.Map and Data.Set do not support infinite Maps and sets, respectively. I noticed a similar question about Data.Set of a greedy implementation fromList , and after reading the answers here it is clear that both lazy and greedy implementations are possible to establish that greedy work better. However, I do not quite understand why the lazy implementation of Map.fromList will not work. Something related to how keys are stored?

Answer 1

Data.Map is implemented as a balanced tree (in my opinion, approximately binary); It's hard to create and balance infinite binary trees lazily, without any foresight of input! However, you might like the MemoTrie package, which instead uses lazy, infinite attempts (bits).

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