5 ms·

> This method is really inefficient. That's what I've noticed with Haskellers. They have a tendency to write really slow code and don't have a clear idea of th

by jordigh 12y ago

> This method is really inefficient. That's what I've noticed with Haskellers. They have a tendency to write really slow code and don't have a clear idea of the execution model behind what they write down. A while ago I asked in #haskell for translations into Haskell of the following C++ code: http://codepad.org/sQTXhqC2 http://codepad.org/sQTXhqC2 This should be easy. The algorithm is right in front of you. There should not be a lot of thinking in transcribing an algorithm into Haskell. But most of them wrote down something with a fold which turned what is an O(m*n) algorithm in time and O(n) in space into something like O(m^n) in space and time. The only one who got close to the C++ implementation was one who used a lot of State monads. Then, of course, there was someone who pointed me out to a radically different algorithm written in Haskell that I think is only O(n+m) in both space and time. I haven't been able to understand this other algorithm yet.

evincarofautumn 12y ago
> They have a tendency to write really slow code and don't have a clear idea of the execution model behind what they write down. Of course, this isn’t unique to Haskellers. ;) Granted, reasoning about performance in Haskell is still a relatively young art, and there aren’t many of us who are experienced with it.
wyager 12y ago
The responses you got on IRC don't necessarily represent Haskell best practice (or even good practice). Most people probably have better things to do than translate random toy programs from C++. Certain highly stateful algorithms may be difficult to translate into Haskell, in the same way that certain highly structural or lazy algorithms may be difficult to translate to C++. I'm curious if your time complexity analyses are accurate, given that you (admittedly) did not understand the faster algorithm. You could be getting tripped up by laziness. In general, I've found that most production Haskell code is quite fast, in both big-O and absolute terms.
- tezka 12y ago
  Spoken like a true Haskell fanboy. Why don't you give it a shot, OP has posted the code.
  - alricb 12y ago
    Shriram Krishnamurti to the rescue! Here's a memoized version in scheme: http://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html http://blog.racket-lang.org/2012/08/dynamic-programming-vers...
GFK_of_xmaspast 12y ago
If edit distance is bounded there appear to be algorithms that are linear in the input size: http://en.wikipedia.org/wiki/Edit_distance http://en.wikipedia.org/wiki/Edit_distance and http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht...
acconsta 12y ago
The Haskell Wiki has what seems like a clean and efficient implementation: https://wiki.haskell.org/Edit_distance https://wiki.haskell.org/Edit_distance
- jordigh 12y ago
  Yeah, it's got a completely different algorithm along the diagonal of the matrix. That's the O(m+n) algorithm. I still haven't been able to understand it. But that's not the point. The point is that Haskellers have a hard time translating an algorithm that's right in front of them and instead of writing down an O(m*n) algorithm they instinctively do O(m^n). This whole "many-worlds" approach of the original article is also leading to a very inefficient algorithm. The abstractions Haskellers prefer lead them towards slow code.
  - mafribe 12y ago
    Haskellers have a hard time translating an algorithm that's right in front of them That's no surprise: it is an open problem if this is possible in general. Some time ago Pippenger [1] showed that some programs cannot be transliterated into pure strict functional languages without suffering a slowdown. Later, Bird et al [2] show that the example given by Pippenger to show the slowdown really depends on strictness, and can be transliterated into a pure lazy functional language without asymptotic slowdown. As of May 2015, nobody knows if lazy functional language can solve all problems with the same asymptotic time complexity as stateful languages. [1] N. Pippenger, Pure Versus Impure Lisp. [2] R. Bird, G. Jones, O. De Moor, More haste, less speed: lazy versus eager evaluation.
    - dllthomas 12y ago
      It's an open problem whether it can be translated into a pure, lazy language without an asymptotic slowdown. It's not at all an open problem as to whether it can be implemented in Haskell. The algorithm is mutating vectors - the direct translation is to use ST, and will have the same asymptotic behavior as the C++ version.
kenko 12y ago
The blog post explicitly says that the C++ is a translation of Haskell code, and links to the (efficient) Haskell original.
bitL 12y ago
There is a set of simple patterns/recipes most people use in Haskell that corresponds to their kind of math intuition Haskell seems to support. It doesn't have anything to do with efficiency though, for that you need to be an expert and you still won't be 100% sure the compiler really optimizes the execution the way you intended.
- codygman 12y ago
  > you still won't be 100% sure the compiler really optimizes the execution the way you intended. You can be sure if you read the generated Core and/or assembly code.
  - TheLoneWolfling 12y ago
    And if you're willing to do that on every upgrade of the compiler or anything that may affect the compiler's exact execution path.
    - codygman 12y ago
      Performance regressions in GHC are taken seriously as far as I've seen. It's not that big of a deal since you should test/profile your program on any compiler upgrade. If you see any regressions, just post it to the ghc mailing list and it will probably be solved for you since it's much needed regression feedback/data.
      - TheLoneWolfling 12y ago
        That's good to know. Though I will note that I don't use Haskell. (Haven't had the time to properly learn it, and keep getting frustrated by minor things when I try to dabble with it.) That being said, I used to think that about Java as well - and then the whole substring thing happened.
dllthomas 11y ago
If, as per your profile, you are someone "who really just wants us all to get along", I would recommend against picking stupid fights like this.

by jordigh 12y ago

evincarofautumn 12y ago

> They have a tendency to write really slow code and don't have a clear idea of the execution model behind what they write down. Of course, this isn’t unique to Haskellers. ;) Granted, reasoning about performance in Haskell is still a relatively young art, and there aren’t many of us who are experienced with it.

wyager 12y ago

The responses you got on IRC don't necessarily represent Haskell best practice (or even good practice). Most people probably have better things to do than translate random toy programs from C++. Certain highly stateful algorithms may be difficult to translate into Haskell, in the same way that certain highly structural or lazy algorithms may be difficult to translate to C++. I'm curious if your time complexity analyses are accurate, given that you (admittedly) did not understand the faster algorithm. You could be getting tripped up by laziness. In general, I've found that most production Haskell code is quite fast, in both big-O and absolute terms.

tezka 12y ago
Spoken like a true Haskell fanboy. Why don't you give it a shot, OP has posted the code.
- alricb 12y ago
  Shriram Krishnamurti to the rescue! Here's a memoized version in scheme: http://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html http://blog.racket-lang.org/2012/08/dynamic-programming-vers...

GFK_of_xmaspast 12y ago

If edit distance is bounded there appear to be algorithms that are linear in the input size: http://en.wikipedia.org/wiki/Edit_distance http://en.wikipedia.org/wiki/Edit_distance and http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht...

acconsta 12y ago

The Haskell Wiki has what seems like a clean and efficient implementation: https://wiki.haskell.org/Edit_distance https://wiki.haskell.org/Edit_distance

jordigh 12y ago
Yeah, it's got a completely different algorithm along the diagonal of the matrix. That's the O(m+n) algorithm. I still haven't been able to understand it. But that's not the point. The point is that Haskellers have a hard time translating an algorithm that's right in front of them and instead of writing down an O(m*n) algorithm they instinctively do O(m^n). This whole "many-worlds" approach of the original article is also leading to a very inefficient algorithm. The abstractions Haskellers prefer lead them towards slow code.
- mafribe 12y ago
  Haskellers have a hard time translating an algorithm that's right in front of them That's no surprise: it is an open problem if this is possible in general. Some time ago Pippenger [1] showed that some programs cannot be transliterated into pure strict functional languages without suffering a slowdown. Later, Bird et al [2] show that the example given by Pippenger to show the slowdown really depends on strictness, and can be transliterated into a pure lazy functional language without asymptotic slowdown. As of May 2015, nobody knows if lazy functional language can solve all problems with the same asymptotic time complexity as stateful languages. [1] N. Pippenger, Pure Versus Impure Lisp. [2] R. Bird, G. Jones, O. De Moor, More haste, less speed: lazy versus eager evaluation.
  - dllthomas 12y ago
    It's an open problem whether it can be translated into a pure, lazy language without an asymptotic slowdown. It's not at all an open problem as to whether it can be implemented in Haskell. The algorithm is mutating vectors - the direct translation is to use ST, and will have the same asymptotic behavior as the C++ version.

kenko 12y ago

The blog post explicitly says that the C++ is a translation of Haskell code, and links to the (efficient) Haskell original.

bitL 12y ago

There is a set of simple patterns/recipes most people use in Haskell that corresponds to their kind of math intuition Haskell seems to support. It doesn't have anything to do with efficiency though, for that you need to be an expert and you still won't be 100% sure the compiler really optimizes the execution the way you intended.

codygman 12y ago
> you still won't be 100% sure the compiler really optimizes the execution the way you intended. You can be sure if you read the generated Core and/or assembly code.
- TheLoneWolfling 12y ago
  And if you're willing to do that on every upgrade of the compiler or anything that may affect the compiler's exact execution path.
  - codygman 12y ago
    Performance regressions in GHC are taken seriously as far as I've seen. It's not that big of a deal since you should test/profile your program on any compiler upgrade. If you see any regressions, just post it to the ghc mailing list and it will probably be solved for you since it's much needed regression feedback/data.
    - TheLoneWolfling 12y ago
      That's good to know. Though I will note that I don't use Haskell. (Haven't had the time to properly learn it, and keep getting frustrated by minor things when I try to dabble with it.) That being said, I used to think that about Java as well - and then the whole substring thing happened.

dllthomas 11y ago

If, as per your profile, you are someone "who really just wants us all to get along", I would recommend against picking stupid fights like this.