list sorting

Adrian Hey ahey at
Thu Jan 19 03:28:23 EST 2006


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..

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.

Adrian Hey


More information about the Libraries mailing list