[Haskell-cafe] Space Efficiency When Sorting a List of Many Lists

[Felipe Lessa]

On Thu, Dec 31, 2009 at 03:38:51AM -0700, Luke Palmer wrote:
> But if you're serious, you can probably do better than just generating
> them all and passing them to sort.  I get the impression that there is
> some structure here that can be taken advantage of.

Isn't what he wants a trie?  In particular, a Patricia trie?

If he cares about repeated elements then he can use a structure
like list-tries' Data.ListTrie.Patricia.Map.Ord.TrieMap[1].  The
values would be the number of times that sequence was seen.

Taking advantage of the list structure should give tremendous
speed improvements since fewer comparisions between the list
elements are made.  Also the trie will automatically share common
parts.

All that being said, I don't think I really understood OP's
problem :).

HTH!

[1] http://hackage.haskell.org/packages/archive/list-tries/0.1/doc/html/Data-ListTrie-Patricia-Map-Ord.html

--
Felipe.