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

[Sunil S Nandihalli]

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
<felipe.lessa at gmail.com> wrote:
> 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.
>