5 ms·

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 11y 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 11y 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 11y 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.
    - mafribe 11y ago
      So you are saying Haskell is not a pure, lazy language?
      - dllthomas 11y ago
        Why is that surprising? Haskell (as typically implemented; I'm slightly less confident about the details of the report) is lazy and pure by default, but that can be violated locally or more globally if you ask for it loud enough. So the language, as a whole, is not pure in the sense required for those theoretical questions to really apply.
        mafribe 11y ago
        Sure, if you use some of the unsafe stuff ... but what about the safe core of Haskell, do you consider that pure?
        dllthomas 11y ago
        What's needed here is ST. It permits local O(1) mutable vectors, while enforcing referential transparency when viewed from outside the runST. ST is clearly not pure in the sense that theory requires to make "can we implement this algorithm with the same complexity" an interesting question. It seems wrong to consider it part of "the unsafe stuff", however - it doesn't have the same kind of unenforced caveats as unsafePerformIO and unsafeCoerce and similar. Separately, "the unsafe stuff" is still part of the language as used, and while it's certainly better practice to avoid it when you can, it's silly to exclude it when asking whether it's possible to do something - they are sometimes appropriate.
        deleted 11y ago
        [deleted]
        mafribe 11y ago
        By ST you mean Haskell's StateT monad transfomer? Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations? That would be an interesting proposal. But I wonder if it captures the conceptual content of the informal concept of purity. Maybe a time complexity restriction should be provable from purity?
- tome 11y ago
  It seems a bit of a broad generalisation to say "Haskellers have a hard time translating an algorithm" based on who happened to be on the IRC channel at the time and decided to answer a challenge from a random C++ programmer who turned up. Anyway, Haskell is perfectly decent at implementing your algorithm, and imperative algoritms in general. He's a more-or-less direct translation http://lpaste.net/132519 There's extra noise related to wrapping and unwrapping mutable cells which I could tidy up if I had the time, otherwise it's essentially identical. In any case the author of the post in question, Bartosz Milewski, is an expert in C++ and not particularly an expert in Haskell, so your point seems misdirected.
  - jordigh 11y ago
    > It seems a bit of a broad generalisation to say "Haskellers have a hard time translating an algorithm" based on who happened to be on the IRC channel at the time and decided to answer a challenge from a random C++ programmer who turned up. I'm not a "C++ programmer". I'm just a programmer. I happened to have the algorithm written in C++, but I could quite easily have written it in pseudocode. I got about 6 responses in 20 minutes. Four of those were O(m^n). Yes, I think this is quite indicative that Haskellers have a hard time writing performant code.
  - dllthomas 11y ago
    And of course the root of this conversation was mistaken in the first place. The algorithm Bartosz is presenting is the b!/(b-n)! algorithm that just examines each permutation once.

jordigh 11y 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 11y 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 11y 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.
  - mafribe 11y ago
    So you are saying Haskell is not a pure, lazy language?
    - dllthomas 11y ago
      Why is that surprising? Haskell (as typically implemented; I'm slightly less confident about the details of the report) is lazy and pure by default, but that can be violated locally or more globally if you ask for it loud enough. So the language, as a whole, is not pure in the sense required for those theoretical questions to really apply.
      - mafribe 11y ago
        Sure, if you use some of the unsafe stuff ... but what about the safe core of Haskell, do you consider that pure?
        dllthomas 11y ago
        What's needed here is ST. It permits local O(1) mutable vectors, while enforcing referential transparency when viewed from outside the runST. ST is clearly not pure in the sense that theory requires to make "can we implement this algorithm with the same complexity" an interesting question. It seems wrong to consider it part of "the unsafe stuff", however - it doesn't have the same kind of unenforced caveats as unsafePerformIO and unsafeCoerce and similar. Separately, "the unsafe stuff" is still part of the language as used, and while it's certainly better practice to avoid it when you can, it's silly to exclude it when asking whether it's possible to do something - they are sometimes appropriate.
        deleted 11y ago
        [deleted]
        mafribe 11y ago
        By ST you mean Haskell's StateT monad transfomer? Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations? That would be an interesting proposal. But I wonder if it captures the conceptual content of the informal concept of purity. Maybe a time complexity restriction should be provable from purity?
tome 11y ago
It seems a bit of a broad generalisation to say "Haskellers have a hard time translating an algorithm" based on who happened to be on the IRC channel at the time and decided to answer a challenge from a random C++ programmer who turned up. Anyway, Haskell is perfectly decent at implementing your algorithm, and imperative algoritms in general. He's a more-or-less direct translation http://lpaste.net/132519 There's extra noise related to wrapping and unwrapping mutable cells which I could tidy up if I had the time, otherwise it's essentially identical. In any case the author of the post in question, Bartosz Milewski, is an expert in C++ and not particularly an expert in Haskell, so your point seems misdirected.
- jordigh 11y ago
  > It seems a bit of a broad generalisation to say "Haskellers have a hard time translating an algorithm" based on who happened to be on the IRC channel at the time and decided to answer a challenge from a random C++ programmer who turned up. I'm not a "C++ programmer". I'm just a programmer. I happened to have the algorithm written in C++, but I could quite easily have written it in pseudocode. I got about 6 responses in 20 minutes. Four of those were O(m^n). Yes, I think this is quite indicative that Haskellers have a hard time writing performant code.
- dllthomas 11y ago
  And of course the root of this conversation was mistaken in the first place. The algorithm Bartosz is presenting is the b!/(b-n)! algorithm that just examines each permutation once.