Note [Deterministic UniqFM]

A @UniqDFM@ is just like @UniqFM@ with the following additional
property: the function `udfmToList` returns the elements in some
deterministic order not depending on the Unique key for those elements.

If the client of the map performs operations on the map in deterministic
order then `udfmToList` returns them in deterministic order.

There is an implementation cost: each element is given a serial number
as it is added, and `udfmToList` sorts its result by this serial
number. So you should only use `UniqDFM` if you need the deterministic
property.

`foldUDFM` also preserves determinism.

Normal @UniqFM@ when you turn it into a list will use
Data.IntMap.toList function that returns the elements in the order of
the keys. The keys in @UniqFM@ are always @Uniques@, so you end up with
with a list ordered by @Uniques@.
The order of @Uniques@ is known to be not stable across rebuilds.
See Note [Unique Determinism] in GHC.Types.Unique.


There's more than one way to implement this. The implementation here tags
every value with the insertion time that can later be used to sort the
values when asked to convert to a list.

An alternative would be to have

  data UniqDFM ele = UDFM (M.IntMap ele) [ele]

where the list determines the order. This makes deletion tricky as we'd
only accumulate elements in that list, but makes merging easier as you
can just merge both structures independently.
Deletion can probably be done in amortized fashion when the size of the
list is twice the size of the set.