[Haskell-cafe] Histogram creation

[Duncan Coutts]

On Mon, 2008-11-10 at 18:05 +0100, Bertram Felgenhauer wrote:
> Alexey Khudyakov wrote:
> > Hello!
> > 
> > I'm tryig to write efficient code for creating histograms. I have following
> > requirements for it:
> > 
> > 1. O(1) element insertion
> > 2. No reallocations. Thus in place updates are needed.
> > 
> > accumArray won't go because I need to fill a lot of histograms (hundrends)
> > from vely long list of data (possibly millions of elements) and it will
> > traverse input data for each histogram.
> 
> That's just not true, for GHC's implementation of accumArray at least,
> which goes via the ST monad.

Perhaps I misunderstood but I think Alexey means that he wants to
accumulate several different histograms (ie different arrays) but to
only make one pass over the input data. The form of accumArray does not
make that possible (unless one managed to pack the different histograms
into different parts of the same array).

If a fold using a pure persistent map type really is too slow then it
should still be possible to do an ST implementation in a reasonably
elegant way using a foldr on the input list, accumulating an ST action. 

Duncan