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

Felipe Lessa felipe.lessa at gmail.com
Thu Dec 31 07:37:59 EST 2009

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

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


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


More information about the Haskell-Cafe mailing list