3 ms·

from the "good", 1) and 2) can be helpful before you start working on an efficient implementation. Basically, bang out a slow but obviously correct implementat

by platz 13y ago

from the "good", 1) and 2) can be helpful before you start working on an efficient implementation. Basically, bang out a slow but obviously correct implementation, and then iterate to convert it to be efficient, perhaps using things like 'equational reasoning'. However I haven't much experience with this technique yet... I believe this is the technique used in Pearls of Functional Algorithm Design by Richard Bird (I have yet to read it)

alkonaut 13y ago
Question is: starting in the idiomatic Haskell implementation that you discover is too slow, what is the next step? How does one iteratively go from that to a slightly faster one, to an even faster one? You don't, because it's near impossible. In Haskell you have defined quicksort, not instructed your computer how to do it. That's the reason it's beautiful, but also the reason it's hard to iteratively refine your soluion. There is basically only one definition of quicksort: your program, and you can't iteratively "refine the definition" You can try to make it in-place in Haskell but there is no clear transition from your initial version to the in-place version. The in-place haskell one looks something like this (and that java code shows no sign of envy now). Answer: like this http://stackoverflow.com/questions/5268156/how-do-you-do-an-in-place-quicksort-in-haskell http://stackoverflow.com/questions/5268156/how-do-you-do-an-... This is my main problem with functional programming: it makes it very easy to go 90% of the way in a very elegant matter. Once you hit that brick wall though, you come to a point where you'd cut an arm off for a mutable array. Perhaps the solution isn't to write horrible Haskell but rather either use a less strict functional language OR outsource that 10% of the code to an imperative language, rather than making contrived, complicated code like the in-place Haskell quicksort?
- platz 13y ago
  I mentioned Pearls of Functional Algorithm Design because it exactly describes how to do this. It may not lead to a solution in the ST monad, but it does tell you to to iterate to a better solution. This post explains what I'm talking about: http://www.atamo.com/blog/how-to-read-pearls-by-richard-bird-1/ http://www.atamo.com/blog/how-to-read-pearls-by-richard-bird...
  - alkonaut 13y ago
    Sounds like a good read, sold!
    - platz 13y ago
      I'm kind of on the fence about it - I've hesitated buying it because the post also explains that it's a notoriously difficult book - some of the results of the "swizzling" can lead to some inscrutable final programs. But I'll probably pick it up at some point in the near future.
      - louthy 13y ago
        > it's a notoriously difficult book Personally I don't find that to be true, it's perfectly logical mostly. It's definitely worth picking up imho.
- oakwhiz 13y ago
  The problem that you are describing occurs when you are trying to optimize a piece of idiomatic functional code that you have already written. Perhaps the solution could be to keep the code you have already written, and write a low-level, highly-optimized replacement alongside it, then have the compiler verify that the low-level code is provably identical in its output to the original function. If the code passes this test, then it is replaced with the optimized version. If you change either piece of code, and they do not match each other, then your code will not compile.

by platz 13y ago

alkonaut 13y ago

Question is: starting in the idiomatic Haskell implementation that you discover is too slow, what is the next step? How does one iteratively go from that to a slightly faster one, to an even faster one? You don't, because it's near impossible. In Haskell you have defined quicksort, not instructed your computer how to do it. That's the reason it's beautiful, but also the reason it's hard to iteratively refine your soluion. There is basically only one definition of quicksort: your program, and you can't iteratively "refine the definition" You can try to make it in-place in Haskell but there is no clear transition from your initial version to the in-place version. The in-place haskell one looks something like this (and that java code shows no sign of envy now). Answer: like this http://stackoverflow.com/questions/5268156/how-do-you-do-an-in-place-quicksort-in-haskell http://stackoverflow.com/questions/5268156/how-do-you-do-an-... This is my main problem with functional programming: it makes it very easy to go 90% of the way in a very elegant matter. Once you hit that brick wall though, you come to a point where you'd cut an arm off for a mutable array. Perhaps the solution isn't to write horrible Haskell but rather either use a less strict functional language OR outsource that 10% of the code to an imperative language, rather than making contrived, complicated code like the in-place Haskell quicksort?

platz 13y ago
I mentioned Pearls of Functional Algorithm Design because it exactly describes how to do this. It may not lead to a solution in the ST monad, but it does tell you to to iterate to a better solution. This post explains what I'm talking about: http://www.atamo.com/blog/how-to-read-pearls-by-richard-bird-1/ http://www.atamo.com/blog/how-to-read-pearls-by-richard-bird...
- alkonaut 13y ago
  Sounds like a good read, sold!
  - platz 13y ago
    I'm kind of on the fence about it - I've hesitated buying it because the post also explains that it's a notoriously difficult book - some of the results of the "swizzling" can lead to some inscrutable final programs. But I'll probably pick it up at some point in the near future.
    - louthy 13y ago
      > it's a notoriously difficult book Personally I don't find that to be true, it's perfectly logical mostly. It's definitely worth picking up imho.
oakwhiz 13y ago
The problem that you are describing occurs when you are trying to optimize a piece of idiomatic functional code that you have already written. Perhaps the solution could be to keep the code you have already written, and write a low-level, highly-optimized replacement alongside it, then have the compiler verify that the low-level code is provably identical in its output to the original function. If the code passes this test, then it is replaced with the optimized version. If you change either piece of code, and they do not match each other, then your code will not compile.