3 ms·

This is a nice example what Haskell can do, but the sort itself is quite inefficient and it's not a true quicksort.

by funky_lambda 13y ago

theseoafs 13y ago
It's absolutely a true quicksort.
- taeric 13y ago
  Is it in place? If not, then it is not a true quicksort.
  - theseoafs 13y ago
    Quicksort can be implemented in an in-place fashion, but that's not a requirement by any means.
    - archgoon 13y ago
      http://www.informit.com/articles/article.aspx?p=1407357&seqNum=3 http://www.informit.com/articles/article.aspx?p=1407357&seqN...
  - SilasX 13y ago
    Interesting question -- in Haskell that means something else (some would say "nothing"). The language is designed around making sure that you only specify the function that the code is supposed to accomplish, and all implementation decisions are left to the compiler -- just as it would be for the RHS of a statement like `x = 3 + 4*(5 + 1);` in C. In this case, as in all others, the Haskell compiler would decide what is the optimal way to implement it, given whatever other constraints you've placed on the program. You can add additional constraints that ensure the compiled code turns out to be in-place, at a cost of verbosity.
    - taeric 13y ago
      If there is an example where such an optimization has actually been implemented and correctly chosen, that is news to me. I mean, to a very large extent, this is the reason why classical imperative languages are so easy to understand and reason about. The programmers directions are much more straight forwardly executed than in examples like these hypotheticals. Oh, I just got to your last sentence. Basically, that this would be a lot more verbose if written in such a way that it would be in place. Which is kind of the point of this criticism. Isn't it? Don't get me wrong, the power of Haskell is not really in question. Just that example.
      - SilasX 13y ago
        Your criticisms are all from the perspective of "it keeps me from telling it how to implement the functionality", which is true, but not what Haskell's design (or pure FP language design in general) optimizes for. Sometimes, you really do want to make commands to the bare metal regarding exactly how you want the program implemented. For general use, however, you don't: compilers are (at least these days) a lot better at finding optimizations than the typical user. It comes down to abstraction levels: pick the one that matches the problem you're working on. The FP philosophy is "speaking about specific memory cells is way too low" in most cases, like telling it you want a sorted list. In fact, it would probably be even better (from that selfsame philosophy) to define a sort in terms of the conditions the final list would meet (as opposed to nested, recursing conditions like in the example). Something like, "return a list where every element is <= the one after it, and where every element is also in the original list, as many times as it occurs there". If you want to see the examples of quicksort in Haskell to enforce in-place and other requirements, see this discussion here, with links: http://www.haskell.org/haskellwiki/Introduction/Direct_Translation http://www.haskell.org/haskellwiki/Introduction/Direct_Trans... tl;dr: Yeah, Haskell is worse at letting you force the sort to be in-place, but that can be a very good thing.
        acqq 13y ago
        Haskell: http://www.haskell.org/pipermail/haskell-cafe/2009-August/065269.html http://www.haskell.org/pipermail/haskell-cafe/2009-August/06... Twice as slow as C but without also in-place like C and extremely similar (see the sort function here): http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort#C http://en.wikibooks.org/wiki/Algorithm_Implementation/Sortin... It's interesting to see is how very similar Haskel and C sources fundamentally become once they really solve the same problem and not the different ones.
  - anaphor 13y ago
    Has anyone ever bothered to ask Tony Hoare what he thinks on this topic? I know SPJ and him both work for MS Research, maybe he can get on that and settle this for us.
    - taeric 13y ago
      I would be curious to know the answer. Though, I should have added in my original post that I am far from the originator of this view. I see a sibling post elaborated. I think the crux is simply that without the "in place" nature, it loses a lot of its speed advantage. Cache localities and such.

This is a nice example what Haskell can do, but the sort itself is quite inefficient and it's not a true quicksort.

theseoafs 13y ago

It's absolutely a true quicksort.

taeric 13y ago
Is it in place? If not, then it is not a true quicksort.
- theseoafs 13y ago
  Quicksort can be implemented in an in-place fashion, but that's not a requirement by any means.
  - archgoon 13y ago
    http://www.informit.com/articles/article.aspx?p=1407357&seqNum=3 http://www.informit.com/articles/article.aspx?p=1407357&seqN...
- SilasX 13y ago
  Interesting question -- in Haskell that means something else (some would say "nothing"). The language is designed around making sure that you only specify the function that the code is supposed to accomplish, and all implementation decisions are left to the compiler -- just as it would be for the RHS of a statement like `x = 3 + 4*(5 + 1);` in C. In this case, as in all others, the Haskell compiler would decide what is the optimal way to implement it, given whatever other constraints you've placed on the program. You can add additional constraints that ensure the compiled code turns out to be in-place, at a cost of verbosity.
  - taeric 13y ago
    If there is an example where such an optimization has actually been implemented and correctly chosen, that is news to me. I mean, to a very large extent, this is the reason why classical imperative languages are so easy to understand and reason about. The programmers directions are much more straight forwardly executed than in examples like these hypotheticals. Oh, I just got to your last sentence. Basically, that this would be a lot more verbose if written in such a way that it would be in place. Which is kind of the point of this criticism. Isn't it? Don't get me wrong, the power of Haskell is not really in question. Just that example.
    - SilasX 13y ago
      Your criticisms are all from the perspective of "it keeps me from telling it how to implement the functionality", which is true, but not what Haskell's design (or pure FP language design in general) optimizes for. Sometimes, you really do want to make commands to the bare metal regarding exactly how you want the program implemented. For general use, however, you don't: compilers are (at least these days) a lot better at finding optimizations than the typical user. It comes down to abstraction levels: pick the one that matches the problem you're working on. The FP philosophy is "speaking about specific memory cells is way too low" in most cases, like telling it you want a sorted list. In fact, it would probably be even better (from that selfsame philosophy) to define a sort in terms of the conditions the final list would meet (as opposed to nested, recursing conditions like in the example). Something like, "return a list where every element is <= the one after it, and where every element is also in the original list, as many times as it occurs there". If you want to see the examples of quicksort in Haskell to enforce in-place and other requirements, see this discussion here, with links: http://www.haskell.org/haskellwiki/Introduction/Direct_Translation http://www.haskell.org/haskellwiki/Introduction/Direct_Trans... tl;dr: Yeah, Haskell is worse at letting you force the sort to be in-place, but that can be a very good thing.
      - acqq 13y ago
        Haskell: http://www.haskell.org/pipermail/haskell-cafe/2009-August/065269.html http://www.haskell.org/pipermail/haskell-cafe/2009-August/06... Twice as slow as C but without also in-place like C and extremely similar (see the sort function here): http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort#C http://en.wikibooks.org/wiki/Algorithm_Implementation/Sortin... It's interesting to see is how very similar Haskel and C sources fundamentally become once they really solve the same problem and not the different ones.
- anaphor 13y ago
  Has anyone ever bothered to ask Tony Hoare what he thinks on this topic? I know SPJ and him both work for MS Research, maybe he can get on that and settle this for us.
  - taeric 13y ago
    I would be curious to know the answer. Though, I should have added in my original post that I am far from the originator of this view. I see a sibling post elaborated. I think the crux is simply that without the "in place" nature, it loses a lot of its speed advantage. Cache localities and such.