On Sun, 2008-03-09 at 23:04 -0400, Dan Doel wrote: > On Sunday 09 March 2008, Krzysztof Skrzętnicki wrote:
> > What do you think about this particular function? > > Some thoughts: > > 1) To get your function specifically, you could just use Data.Set.Set a > instead of Map a (). > > 2) What does it do with duplicate elements in the list? I expect it deletes > them. To avoid this, you'd need to use something like fromListWith, keeping > track of how many duplicates there are, and expanding at the end. > > 3) I imagine the time taken to get any output is always O(n*log n). Various > lazy sorts can be written (and I'd guess the standard library sort is written > this way, although I don't know for sure) such that 'head (sort l)' is O(n), > or O(n + k*log n) for getting the first k elements. However, Map, being a > balanced binary tree, doesn't (I think) have the right characteristics for > this. Sounds to me like we should try a heap sort. As a data structure it should have similar constant factors to Data.Map (or .Set) but a heap is less ordered than a search tree and gives the O(n + k*log n) property. Duncan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe