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