[Haskell-beginners] How to convert a Data.Set to a Descending List?

[Felipe Almeida Lessa]

On Sun, Aug 21, 2011 at 5:18 AM, Sunil S Nandihalli
<sunil.nandihalli at gmail.com> wrote:
>  Is there a more efficient way to convert a Set to a descending list?
> I was looking for a function similar to Set.toAscList something like
> Set.toDecList . I feel first converting to a ascending list and then
> reversing may be in-efficient given that I actually don't need all the
> elements only a last couple of elements..

Implementing toDecList should be easy, but it's not implemented.  So I
can see a couple of ideas:

a) Instead of using a 'Set X', where X is your datatype, use 'Set (Rev X)' where

  newtype Rev t = Rev t
  instance Eq t => Eq (Rev t) where Rev x == Rev y = x == y
  instance Ord t => Ord (Rev t) where compare (Rev x) (Rev y) = compare y x

Then you would just need to use toAscList =).

b) If you need both the few first and few last elements to toAscList,
then option a doesn't work.  But if you really need just a few
elements, you may use maxKey:

  toDecList s =
    case maxView s of
      Nothing -> []
      Just (x, s') -> x : toDecList s'

  The problem is that 'take k . toDecList' take O(k log n) instead of O(k).

c) Data.Set.fold says that the order is unspecified.  But the current
implementation does the fold in ascending order.  You may cheat and
implement:

  toDecList s = fold (\a b -> b . (a:)) id s []

Cheers, =)

-- 
Felipe.