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