undefined | Better HN

0 pointsSilasX11y ago0 comments

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

0 comments

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.

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

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

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

1 more reply

j / k navigate · click thread line to collapse

0 comments

acallan11y ago

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.

SilasXOP11y ago

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.

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

SilasXOP11y 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?

1 more reply

j / k navigate · click thread line to collapse