[SilasX]

Hold on: does Haskell allow "the" QuickSort on one line, or just a sort? Because from what I've read, if you want to make Haskell do all the efficient stuff in a QS, you have to tell it a lot more, bloating the program.

Edit: this is what I had in mind: http://augustss.blogspot.com/2007/08/quicksort-in-haskell-qu...

Btw, I took AP Compsci with C++ in Austin around that time, so we might know each other.

[conistonwater]

If you think quicksort is bloated, wait till you see a full implementation of depth-first search (I mean full: with all the back/cross/forward-edges and everything). It's a good exercise, but not very pretty.

Most of the bloat comes from the fact that when you implement it in Haskell, the resulting program doesn't really depend on being executed in the IO monad, and can be easily modified to run in many other monads too (like ST, or some transformed monad). The result is that the Haskell imperative version is far more general than a similar C implementation.

[acallan]

Like a lot of UT Computer Science, the implementation is a detail left for the reader. The semantics of the language make the one-liner n*log(n)--that's the takeaway.

[SilasX]

But the one liner was the implementation, and doesn't do a QuickSort...

[acallan]

In tests and homework, we would implement the one-liner quicksort with paper and pencil, much like a math test. In a pencil implementation of that Haskell, it is n log(n). Each line on the paper represented one level of recursion.

Implementing it on silicon requires the trade-offs you mention. But silicon is just an implementation left to the reader...

EDIT: I guess where I'm coming from, Haskell was used in the context of the Theory of Computation, not real-world implementation details and the like.

[SilasX]

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.

[acallan]

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.

[SilasX]

>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.