5 ms·

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.
          • mafribe 11y 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
            • dllthomas 11y ago
              You are infuriating. If you object to notions of purity, why did you bring it up in the first place? The first place it was used in this thread was your citing a paper entitled "Pure versus Impure Lisp". In that paper, it was used to mean prohibiting "set-car!" and "set-cdr!". ST provides the equivalent of "set-car!" and "set-cdr!", so in the presence of ST the result you were citing in the paper doesn't even apply to a strict version of Haskell. Please just stop making claims about Haskell until you have some sense of what you're talking about (or at least add a caveat warning others that you might not).
• 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.