Hacker News new | ask | show | jobs
by SilasX 4162 days ago
I'm not disputing the scaling properties of the Haskell one-liner, but it doesn't give you the benefits of the true QuickSort as your comment suggests, e.g. it doesn't guarantee in-place sorting or efficient use of when access be locked.

The point is, I find it questionable to praise Haskell for how you can implement a one-line QuickSort that isn't really a QuickSort.
1 comments
acallan 4162 days ago
Each list comprehension is O(n). O(n)+O(n)=O(n). Each iteration will roughly bisect the list, resulting in roughly log(n) iterations. Thus the one-liner is O(n*log(n)).

Haskell says nothing about how lists are implemented, so with respect to "true"ness (I'm not really sure what this means), we can cannot generalize. A sufficiently optimized Haskell compiler implemented in silicon would have the liberty of using the memory in-place.

link
SilasX 4162 days ago
>Each list comprehension is O(n). O(n)+O(n)=O(n). Each iteration will roughly bisect the list, resulting in roughly log(n) iterations. Thus the one-liner is O(n*log(n)).

"I'm not disputing the scaling properties of that sort" = this proof does not convince me of anything I didn't already agree with. Was I unclear about what I was objecting to?

> Haskell says nothing about how lists are implemented, so with respect to "true"ness (I'm not really sure what this means), we can cannot generalize. A sufficiently optimized Haskell compiler implemented in silicon would have the liberty of using the memory in-place.

"Trueness" means "doing the real QuickSort". The one you posted doesn't. You can get the real QuickSort, but not with one line. A better compiler might identify useful invariants; you were not using such a compiler.

But if you had such a compiler, you wouldn't need to write I that way; you could just specify what conditions the final sort would obey, and that would be enough. You wouldn't need to tell it to filter explicitly.

link
acallan 4162 days ago
What do you mean by the "real QuickSort"? The professor who taught me Haskell at UT used to work on Burroughs LISP machines and wasn't too concerned with caches, memory, or the like. Again, Haskell can be viewed as a language for computation. From this perspective, the one-liner is pure beauty.
link