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

Hi Felipe, Thanks a lot for your response. I thought I should describe what I want in a little more detail. You may have a better suggestion to solve the problem. I currently have a Set I want to take a couple of elements on either side of a given key. How can I do this? Here is a description of the subseq function in clojure. http://clojuredocs.org/clojure_core/clojure.core/subseq Thanks, Sunil. On Sun, Aug 21, 2011 at 6:00 PM, Felipe Almeida Lessa wrote:

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