[acallan]

Indeed, my first CS class in 1999 at UT was in Haskell. Wow! What a change it was from high school AP Computer Science in Texas, which was (in those days) C++.

Seeing QuickSort in just one line was what hit it home.

I remember thinking at the time that this was really incredible, but that Haskell had no future. This was at the time of Hugs 98, although I remember hearing about GHC. I'm glad to be wrong about this.

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