On Sun, Aug 21, 2011 at 5:18 AM, Sunil S Nandihalli
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.