Functional counterpart of counting-sort?
Hi all, I’m sorry if this is a trivial question. Everybody knows the counting sort algorithm to sort an array of integer values, which runs in O(n) time, circumventing the O(n log n) lower bound by avoiding comparison operations. Of course, that only works for integers. However, it seems to me that it essentially relies on the availability of a O(1) indexing operation on the array, not on algebraic or logical properties of the set of the integers. Do any of you know if it is possible to sort a _list_ of integers in O(n) time in a (lazy) purely functional language? I’d say no, but given all the crazy laziness tricks out there, I can’t say for sure ;) Even if no: any theoretical considerations on why not? Greetings, Nicola
On Sun, Sep 06, 2015 at 07:29:23PM +0200, Nicola Gigante wrote:
Do any of you know if it is possible to sort a _list_ of integers in O(n) time in a (lazy) purely functional language?
Are you familiar with discrimination? http://hackage.haskell.org/package/discrimination
Il giorno 06/set/2015, alle ore 19:36, Tom Ellis
On Sun, Sep 06, 2015 at 07:29:23PM +0200, Nicola Gigante wrote: Do any of you know if it is possible to sort a _list_ of integers in O(n) time in a (lazy) purely functional language?
Are you familiar with discrimination?
Well, no, I wasn't aware of it at all! Thank you! It seems what I'm looking for! I'll read the papers pointed in the doc, but does anyone have a few words to say on what "discrimination" is all about? Greetings, Nicola
This video should help in explaining what the library is about. It's a talk
by Edward Kmett, the author of the library, and he goes into the motivation
and internals of the library:
https://youtu.be/cB8DapKQz-I
Don't worry if you don't get everything in the first watch though, I've
watched it a couple of times, and have still worked my way through only the
first half of it, maybe ;)
Reading the papers before hand might help too.
Enjoy!
Vivitsu
On Sun, Sep 6, 2015 at 23:33 Nicola Gigante
Il giorno 06/set/2015, alle ore 19:36, Tom Ellis < tom-lists-haskell-cafe-2013@jaguarpaw.co.uk> ha scritto:
On Sun, Sep 06, 2015 at 07:29:23PM +0200, Nicola Gigante wrote: Do any of you know if it is possible to sort a _list_ of integers in O(n) time in a (lazy) purely functional language?
Are you familiar with discrimination?
Well, no, I wasn't aware of it at all! Thank you!
It seems what I'm looking for! I'll read the papers pointed in the doc, but does anyone have a few words to say on what "discrimination" is all about?
Greetings, Nicola _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
participants (3)
-
Nicola Gigante -
Tom Ellis -
Vivitsu Maharaja