Menu
I was writing some code and I figured that I'd be able to create an infinite map from an infinite list of tuples. Something along the lines of the following:
Map.fromList [(i,i+1)|i<-[1..]]
Of course, I discovered immediately that Data.Map and Data.Set do not support infinite Maps and Sets respectively. I noticed a similar question about Data.Set's greedy implementation of fromList, and, after reading over the answers here, it's clear that both lazy and greedy implementations are possible for Set, just that the greedy ones work better. I don't really understand, however, why a lazy implementation of Map.fromList wouldn't work. Something to do with how keys are stored?
511
As you all know, lists in Haskell can be infinite. This capability is a natural consequence of Haskell's lazy evaluation. An infinite list in Haskell is no problem since Haskell will lazily generate only as much of the list as is needed, when it is needed.
But in Haskell, you only need to allocate space for the items in the list that actually get evaluated. The two most basic functions for creating an infinite list are "repeat" and "cycle". The first makes an infinite number of the same element, while the second allows you to cycle through a specific series of elements.
Data.Map is implemented as a balanced tree (roughly binary, I think); it's hard to create and balance infinite binary trees lazily without some foreknowledge about the input! However, you might like something like the MemoTrie package, which uses lazy infinite tries (of bits) instead.
> let x = trie (\x -> x+1)
> untrie x 72
73
> untrie x 37
38
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
