5 ms·

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 c

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 12y ago
So you are saying Haskell is not a pure, lazy language?
- dllthomas 12y 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 12y ago
    Sure, if you use some of the unsafe stuff ... but what about the safe core of Haskell, do you consider that pure?
    - dllthomas 12y 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 12y ago
        [deleted]
      - mafribe 12y 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 12y 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.
        mafribe 12y ago
        SPJ and J Launchbury seem to think ST is pure. Looking over the PLDI paper, I get the impression that the key difference between ST and the usual State monad is (1) the ability to name state, and (2) the use of parametric polymorphism to prevent scope-extrusion of state. Of course ML has scope-extrusion of state, and one of my questions/examples upthread was about the ability of Haskell's monadically controlled effects to implement such scope extrusion without 'tricks'. All in all I feel that the notion of purity is controversial, insufficiently theorised, and that the community would benefit from a clearer understanding of the trade-offs involved in the different notions of purity
- tome 12y ago
  What do "pure" and "lazy" mean to you?
  - mafribe 12y 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 12y 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 12y ago
      With those definitions pure and lazy languages can certainly do mutation and have effects, viz. the IO and ST monads.

mafribe 12y ago

So you are saying Haskell is not a pure, lazy language?

dllthomas 12y 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 12y ago
  Sure, if you use some of the unsafe stuff ... but what about the safe core of Haskell, do you consider that pure?
  - dllthomas 12y 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 12y ago
      [deleted]
    - mafribe 12y 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 12y 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.
        mafribe 12y ago
        SPJ and J Launchbury seem to think ST is pure. Looking over the PLDI paper, I get the impression that the key difference between ST and the usual State monad is (1) the ability to name state, and (2) the use of parametric polymorphism to prevent scope-extrusion of state. Of course ML has scope-extrusion of state, and one of my questions/examples upthread was about the ability of Haskell's monadically controlled effects to implement such scope extrusion without 'tricks'. All in all I feel that the notion of purity is controversial, insufficiently theorised, and that the community would benefit from a clearer understanding of the trade-offs involved in the different notions of purity
tome 12y ago
What do "pure" and "lazy" mean to you?
- mafribe 12y 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 12y 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 12y ago
    With those definitions pure and lazy languages can certainly do mutation and have effects, viz. the IO and ST monads.