[Haskell-beginners] List -> Map -> List, to add duplicates?

[Arlen Christian Mart Cuss]

On Mon, 2011-06-06 at 21:43 -0400, Tom Murphy wrote:
> Hi All,
>      This seems like an inefficient way to do what I'm trying to do.

Intuition tells me it's inefficient, but on second thought:

You're trying to accumulate (and add) values for a matching given index
(in this case, the second argument of the tuple -- btw flipAssoc is
available as Data.Tuple.swap).

That necessarily means traversing the list, the whole time retaining
quick random access to update the value associated with a particular
index -- which is exactly what Maps are for, right? The code does
exactly what you want with the least complexity, AFAICS, though of
course it'd be nicer if there wasn't this List->Map->List.

I'd argue this isn't inefficient to do what you're doing, but I'd look
for a more general optimisation in the context this code comes from in
order to avoid such an operation from the start entirely. :) That may
involve keeping a single map, and updating it progressively as each pair
comes in (which you can do for the initial creation too, with a fold).

Cheers,

Arlen