`flipM` is unnecessarily slow

[ChickenProp]

I noticed that flipM is implemented with flipAL, which uses Eq constraints. I think it's O(n^2) but could instead be O(n log n) with something like

flipM = Map.fromListWith (++) . map (\(k, v) -> (v, [k])) . Map.toList

There are details to check here: are the values in the new map in the same order as with the current implementation? What kind of efficiency does it have if every value in the original map is equal? I think the answers are "yes" and "O(n)" respectively, but that's just from a quick glance. Even if it's not quite right, something like this should be possible.

[andreasabel]

Indeed:

missingh/src/Data/List/Utils.hs

Lines 273 to 282 in dbc657f

	flipAL :: (Eq key, Eq val) => [(key, val)] -> [(val, [key])]
	flipAL oldl =
	let worker :: (Eq key, Eq val) => [(key, val)] -> [(val, [key])] -> [(val, [key])]
	worker [] accum = accum
	worker ((k, v):xs) accum =
	case lookup v accum of
	Nothing -> worker xs ((v, [k]) : accum)
	Just y -> worker xs (addToAL accum v (k:y))
	in
	worker oldl []

missingh/src/Data/Map/Utils.hs

Lines 62 to 63 in dbc657f

	flipM :: (Ord key, Ord val) => Data.Map.Map key val -> Data.Map.Map val [key]
	flipM = Data.Map.fromList . flipAL . Data.Map.toList

There are details to check here: are the values in the new map in the same order as with the current implementation? What kind of efficiency does it have if every value in the original map is equal?

I consider this library legacy because there are well-maintained utility libraries like extra.
So this is why I wouldn't introduce any changes in missingh.
I expect the users of missingh to be legacy users that are satisfied with the status quo.

If you are very motivated to see this changed, though, I wouldn't oppose a PR.

[ChickenProp]

That's fair. I'm not very motivated myself, I just happened to notice this when browsing.