[Haskell-beginners] Looking for a datastructure

[Ertugrul Soeylemez]

"Kees Bleijenberg" <k.bleijenberg at inter.nl.net> wrote:

> My program uses a very long list of (index,count) items. Index and count are
> Int's.
> The program updates the count values a lot. Therefor it uses the index as a
> key to update the belonging count value.
> After updating, the program needs the (index,count) pair with the least
> count value in the list.
> What is an approriate (fast) datastructure? My first idea was to use a heap.
> Problem with the heap is that I can't update the count value by its index
> fast.
> Any ideas?

Try Data.IntMap and Data.Map.  I think they have different asymptotics,
but they both do exactly what you want, so try both.  Because of the
purity I would estimate the total query time to O(log n) and the total
update time to O((log n)^2).


Greets,
Ertugrul


-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/