Minor containers API changes

Liyang HU haskell.org at liyang.hu
Wed Nov 30 07:54:06 CET 2011

Evan Laforge <qdunkan <at> gmail.com> writes:
> > 5) `toDescList` exists in Map, but not in IntMap, Set or IntSet.
> Without this function
> there's no way to (efficiently) iterate over a map backwards, which is
> pretty essential for an ordered collection!

How about using the Down/Dual/Desc/Converse/Opposite/Reverse newtype discussed
in another recent thread, and providing for Data.Map:

  reverse :: Map k a -> Map (Reverse k) a
  reverse Tip = Tip
  reverse (Bin n k a l r) = Bin n (Reverse k) a (reverse r) (reverse l)

(Arguably we also need reverse' :: Map (Reverse k) a -> Map k a. Hmm...)

Only problem right now is that Map is spine-strict, so the above is O(n).
Would this fuse with to(Asc)List?


More information about the Libraries mailing list