list sorting

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

list sorting

John Meacham
is there a function floating around for _efficiently_ sorting a list of
lists that will not evaluate any more of the lists than is needed to
sort them properly and does not re-compare the common prefix of said
lists?

as in,
sortLists :: Ord a => [[a]] -> [[a]]
sortLists = ...

if it proves faster in the general case than 'sort', then a RULES
pragma might be in order to use it instead when sorting lists. a very
common case being sorting strings.

        John

--
John Meacham - ⑆repetae.net⑆john⑈
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: list sorting

Adrian Hey
Hello,

On Thursday 19 Jan 2006 1:29 am, John Meacham wrote:

> is there a function floating around for _efficiently_ sorting a list of
> lists that will not evaluate any more of the lists than is needed to
> sort them properly and does not re-compare the common prefix of said
> lists?
>
> as in,
> sortLists :: Ord a => [[a]] -> [[a]]
> sortLists = ...
>
> if it proves faster in the general case than 'sort', then a RULES
> pragma might be in order to use it instead when sorting lists. a very
> common case being sorting strings.

Well I think you could produce this with tries :-) I have a small
implementation for String(Maps) here..
 http://homepages.nildram.co.uk/~ahey/HLibs/Data.StringMap/

But I can't remember if I made it lazy enough for what you want.

I was thinking I should generalise this for Sets and Maps of Lists
once a common API has been agreed. But I'm not going to have much
time to work on any of this for a couple of weeks now.

Regards
--
Adrian Hey


 
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: list sorting

Ketil Malde-2
In reply to this post by John Meacham
John Meacham <[hidden email]> writes:

> is there a function floating around for _efficiently_ sorting a list of
> lists that will not evaluate any more of the lists than is needed to
> sort them properly and does not re-compare the common prefix of said
> lists?

Sort by head, then recursively sort the tails each bucket?

-k
--
If I haven't seen further, it is by standing in the footprints of giants

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: list sorting

John Meacham
On Thu, Jan 19, 2006 at 10:29:20AM +0100, Ketil Malde wrote:
> John Meacham <[hidden email]> writes:
>
> > is there a function floating around for _efficiently_ sorting a list of
> > lists that will not evaluate any more of the lists than is needed to
> > sort them properly and does not re-compare the common prefix of said
> > lists?
>
> Sort by head, then recursively sort the tails each bucket?

yeah, that is the algorithm I am thinking of. but I was curious if
someone has already done the nitty gritty work of actually coming up
with a super-optimized version with all the tweaks due to careful
profiling and whatnot.

        John

--
John Meacham - ⑆repetae.net⑆john⑈
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: list sorting

Jan-Willem Maessen
In reply to this post by Ketil Malde-2

On Jan 19, 2006, at 4:29 AM, Ketil Malde wrote:

> John Meacham <[hidden email]> writes:
>
>> is there a function floating around for _efficiently_ sorting a  
>> list of
>> lists that will not evaluate any more of the lists than is needed to
>> sort them properly and does not re-compare the common prefix of said
>> lists?
>
> Sort by head, then recursively sort the tails each bucket?

On a related note, a carefully-tweaked implementation of
   group . sort
would be really handy, and just what the doctor ordered in this case.

-Jan-Willem Maessen

>
> -k
> --
> If I haven't seen further, it is by standing in the footprints of  
> giants
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries