Computing percentiles

Question

I am writing a program that will generate a bunch of data. I would like to find various percentages on these data.

The obvious way to do this is to store the data in some sorted container. Are there any Haskell libraries that offer a container that is automatically sorted and offers quick random access to arbitrary indexes?

An alternative is to use an unordered container and do the sorting at the end. I do not know if it will be faster. In any case, we still need a container that offers fast random access. (Array, maybe ...)

Suggestions?

(Another alternative is to plot a histogram and not store the entire data set in memory. But since the goal is to calculate percentiles very accurately, I don’t want to go that route. I also don’t know the range of my data until I I will generate it ...)

Answer 1

Are there any Haskell libraries that offer a container that is automatically sorted and offers quick random access to arbitrary indexes?

Yes, this is your good old Data.Map . See elemAt and other features in the Indexed category.

Data.Set does not offer them, but you can emulate it using Data.Map YourType () .