6 ms·

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

by 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?
        dllthomas 11y ago
        "By ST you mean Haskell's StateT monad transfomer?" No, I mean ST. An entirely different monad: http://hackage.haskell.org/package/base-4.7.0.0/docs/Control-Monad-ST.html http://hackage.haskell.org/package/base-4.7.0.0/docs/Control... "Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations?" "Define", no, as that certainly doesn't encompass the full scope of purity. I think mutability runs counter to most people's notion of purity, particularly when they say "Haskell isn't pure". Of course, we can fake mutability at a cost of O(log n), which is what makes the O(1) notable. If you do think ST is "pure" then it's not an open question whether you can implement update-heavy array based algorithms in a pure language without algorithmic penalty - you clearly can.
  - tome 11y ago
    What do "pure" and "lazy" mean to you?
    - mafribe 11y ago
      Lazy is easy: it's call-by-name evaluation, i.e. (lambda x.M)N -> M[N/x] with caching, ie. each argument is evaluated at most once. Purity is more subtle. I don't think there's an agreed upon definition. [1] essentially ties purity to the equivalency of call-by-name, call-by-need and call-by-value evaluation orders (ignoring divergence and errors). I'm not totally sure that is the right definition. [1] A. Sabry, What is a Purely Functional Language?
      - dllthomas 11y ago
        The most proximate question here, with respect to purity, is "can you do O(1) mutation (outside of the narrow case of replacing a thunk with its result)?" The theory is far more interesting when we say "no", but the answer in the case of Haskell is "yes".
      - tome 11y ago
        With those definitions pure and lazy languages can certainly do mutation and have effects, viz. the IO and ST monads.

by mafribe 11y ago

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?
        dllthomas 11y ago
        "By ST you mean Haskell's StateT monad transfomer?" No, I mean ST. An entirely different monad: http://hackage.haskell.org/package/base-4.7.0.0/docs/Control-Monad-ST.html http://hackage.haskell.org/package/base-4.7.0.0/docs/Control... "Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations?" "Define", no, as that certainly doesn't encompass the full scope of purity. I think mutability runs counter to most people's notion of purity, particularly when they say "Haskell isn't pure". Of course, we can fake mutability at a cost of O(log n), which is what makes the O(1) notable. If you do think ST is "pure" then it's not an open question whether you can implement update-heavy array based algorithms in a pure language without algorithmic penalty - you clearly can.
- tome 11y ago
  What do "pure" and "lazy" mean to you?
  - mafribe 11y ago
    Lazy is easy: it's call-by-name evaluation, i.e. (lambda x.M)N -> M[N/x] with caching, ie. each argument is evaluated at most once. Purity is more subtle. I don't think there's an agreed upon definition. [1] essentially ties purity to the equivalency of call-by-name, call-by-need and call-by-value evaluation orders (ignoring divergence and errors). I'm not totally sure that is the right definition. [1] A. Sabry, What is a Purely Functional Language?
    - dllthomas 11y ago
      The most proximate question here, with respect to purity, is "can you do O(1) mutation (outside of the narrow case of replacing a thunk with its result)?" The theory is far more interesting when we say "no", but the answer in the case of Haskell is "yes".
    - tome 11y ago
      With those definitions pure and lazy languages can certainly do mutation and have effects, viz. the IO and ST monads.