Consider adding fromFunction to Data.IntMap

[treeowl]

I believe Data.IntMap should be able to support

fromFunction :: Int -> Int -> (Int -> a) -> IntMap a

where the first two arguments bound the domain. Alternatively, there might be some fancy way to use a domain made up of multiple ranges.

[treeowl]

To really get the efficiency right, we'd have to make the Bin constructor lazy in the child maps, and strictify other code appropriately (perhaps using a smart constructor). We'd need to run some benchmarks to make sure that didn't cause problems.

[foxik]

I am not sure this is worth it, i.e., do people construct IntMaps in such a way? Would they use fromFunction instead of something trivial like fromList [(i, f i) | i<-[1..100]]?

Also it is not obvious what is the right type of fromFunction -- should we support different step-size than one? If we do, should arguments of fromFunction :: Int -> Int -> Int -> (Int -> a) -> IntMap a be

• lower_bound step upper_bound
• lower_bound step number_of_elements
• lower_bound upper_bound step
• lower_bound number_of_elements step

It is a shame we cannot easily use the [1,3..10] syntax :-)

Also note that if we do this, maybe we should create an equivalent function in IntSet, something like fromRange :: ... -> IntSet.

If you want to pursue this, please propose to libraries@haskell.org.

[treeowl]

We would need to explain, in the documentation, the rather substantial difference in performance characteristics. We also need to do this for Data.Sequence, in fact.

[treeowl]

I have since decided the required laziness is probably going to be way too much trouble to manage and also likely detrimental to performance.