7 ms·

Shared mutable state is the problem. Functional programming addresses this by eliminating mutability, but at the cost of losing many valuable algorithmic appro

Shared mutable state is the problem. Functional programming addresses this by eliminating mutability, but at the cost of losing many valuable algorithmic approaches. (The "quicksort" example usually used to illustrate Haskell doesn't perform a true quicksort and is horrendously slow). Rust deals with it by eliminating sharing via its affine type system. I have only just started exploring Rust but I'm very impressed, it seems the perfect blend of theory and practicality so far.

mbrock 10y ago
To be clear, Haskell absolutely supports shared mutable state, even in sophisticated ways like transactional memory. It's also mostly straightforward to implement a fast Quicksort using mutable arrays in Haskell. The difference is that all that stuff is formulated within a theory based on pure evaluation of functional expressions. Loosely speaking it's like how the math that physics uses doesn't have mutable variables, but it still manages to express time varying phenomena...
- Athas 10y ago
  > It's also mostly straightforward to implement a fast Quicksort using mutable arrays in Haskell. Do you know of one? All the fast array-based quicksorts I have seen in Haskell have been very awkward compared to implementations in imperative languages with good array support (and they have been quite slow as well). I don't feel like this is much of an indictment against Haskell. Sure, a functional language isn't a good fit for a very imperative algorithm, but that's not really its target domain.
  - codygman 10y ago
    http://www.haskellforall.com/2013/05/program-imperatively-using-haskell.html http://www.haskellforall.com/2013/05/program-imperatively-us...
    - Athas 10y ago
      I can't find a quicksort implementation on the other side of that link.
      - codygman 10y ago
        Sorry, I meant to say you could pretty easily make quicksort using the techniques in that link.
  - harpocrates 10y ago
    I wrote a pretty concise version of it a while ago to convince myself it was possible [1]. It isn't as short as the naive (incorrect) quicksort using lists, but every line has a very clear purpose. Most implementations on Rosetta code in other languages [2] seem to be about as long. [1] https://gist.github.com/harpocrates/bbed7b6837d524aafa02 https://gist.github.com/harpocrates/bbed7b6837d524aafa02 [2] https://rosettacode.org/wiki/Sorting_algorithms/Quicksort https://rosettacode.org/wiki/Sorting_algorithms/Quicksort
    - Athas 10y ago
      Thank you, that is a very nice implementation! I think the key is that the vector library is very well designed - it has certainly been the cause of the majority of my Haskell performance successes. I'll say that your implementation benefits from being able to access partitioning as a library function - the actual implementation of unstablePartition is not particularly pretty (but it is conceptually simple).
- alex_hirner 10y ago
  > Loosely speaking it's like how the math that physics uses doesn't have mutable variables I'm curious, can you elaborate on this? If you view time as discrete dimension, mutable state is clearly not necessary. But since we cannot travel through time (yet), nature seems quite mutable in practice. For example, when microwaving food, it is extremely hard to put it back to the same temperature gradients. Similarly with functional programming: if you adhere to it purely, provenance of every state can be traced back. If not, state changes are non-trivial to reverse. So it seems like modelling physical phenomena with immutable states is a choice of perspective rather than a law of physics that can be empirically tested.
  - mbrock 10y ago
    Nature is mutable, but we can describe it with mathematical languages that aren't based on mutation. In some sense I'm saying that Haskell's immutability is superficial, just a semantic choice of perspective...
    - vyodaiken 10y ago
      I think that's a basic misunderstanding of mathematics and physics that is often used as a justification for functional programming. Formulas in physics often reference implicit state such as the time - which is exactly what imperative programming languages do. I'm agreeing with you about the difference of perspective.
      - mbrock 10y ago
        But they don't typically assign a new value to the time variable. It's not part of the normal language of math to have a formula that changes a variable... Time is more like a function variable or implicit parameter, not a piece of mutable state in the imperative programming sense. Such implicit parameters are also part of Haskell, by the way...
        vyodaiken 10y ago
        I randomly open Feynmans lectures on physics and see E (between the sheets) = sigma/epsilon0 E (outside) = 0 assigning two different values to the variable E. In applied math, there are many expressions in which a variable y is treated as a value (depending on implicit parameters) or as a function y(t) depending on explicit independent variables. This is a matter of convenience, not principle.

mbrock 10y ago

To be clear, Haskell absolutely supports shared mutable state, even in sophisticated ways like transactional memory. It's also mostly straightforward to implement a fast Quicksort using mutable arrays in Haskell. The difference is that all that stuff is formulated within a theory based on pure evaluation of functional expressions. Loosely speaking it's like how the math that physics uses doesn't have mutable variables, but it still manages to express time varying phenomena...

Athas 10y ago
> It's also mostly straightforward to implement a fast Quicksort using mutable arrays in Haskell. Do you know of one? All the fast array-based quicksorts I have seen in Haskell have been very awkward compared to implementations in imperative languages with good array support (and they have been quite slow as well). I don't feel like this is much of an indictment against Haskell. Sure, a functional language isn't a good fit for a very imperative algorithm, but that's not really its target domain.
- codygman 10y ago
  http://www.haskellforall.com/2013/05/program-imperatively-using-haskell.html http://www.haskellforall.com/2013/05/program-imperatively-us...
  - Athas 10y ago
    I can't find a quicksort implementation on the other side of that link.
    - codygman 10y ago
      Sorry, I meant to say you could pretty easily make quicksort using the techniques in that link.
- harpocrates 10y ago
  I wrote a pretty concise version of it a while ago to convince myself it was possible [1]. It isn't as short as the naive (incorrect) quicksort using lists, but every line has a very clear purpose. Most implementations on Rosetta code in other languages [2] seem to be about as long. [1] https://gist.github.com/harpocrates/bbed7b6837d524aafa02 https://gist.github.com/harpocrates/bbed7b6837d524aafa02 [2] https://rosettacode.org/wiki/Sorting_algorithms/Quicksort https://rosettacode.org/wiki/Sorting_algorithms/Quicksort
  - Athas 10y ago
    Thank you, that is a very nice implementation! I think the key is that the vector library is very well designed - it has certainly been the cause of the majority of my Haskell performance successes. I'll say that your implementation benefits from being able to access partitioning as a library function - the actual implementation of unstablePartition is not particularly pretty (but it is conceptually simple).
alex_hirner 10y ago
> Loosely speaking it's like how the math that physics uses doesn't have mutable variables I'm curious, can you elaborate on this? If you view time as discrete dimension, mutable state is clearly not necessary. But since we cannot travel through time (yet), nature seems quite mutable in practice. For example, when microwaving food, it is extremely hard to put it back to the same temperature gradients. Similarly with functional programming: if you adhere to it purely, provenance of every state can be traced back. If not, state changes are non-trivial to reverse. So it seems like modelling physical phenomena with immutable states is a choice of perspective rather than a law of physics that can be empirically tested.
- mbrock 10y ago
  Nature is mutable, but we can describe it with mathematical languages that aren't based on mutation. In some sense I'm saying that Haskell's immutability is superficial, just a semantic choice of perspective...
  - vyodaiken 10y ago
    I think that's a basic misunderstanding of mathematics and physics that is often used as a justification for functional programming. Formulas in physics often reference implicit state such as the time - which is exactly what imperative programming languages do. I'm agreeing with you about the difference of perspective.
    - mbrock 10y ago
      But they don't typically assign a new value to the time variable. It's not part of the normal language of math to have a formula that changes a variable... Time is more like a function variable or implicit parameter, not a piece of mutable state in the imperative programming sense. Such implicit parameters are also part of Haskell, by the way...
      - vyodaiken 10y ago
        I randomly open Feynmans lectures on physics and see E (between the sheets) = sigma/epsilon0 E (outside) = 0 assigning two different values to the variable E. In applied math, there are many expressions in which a variable y is treated as a value (depending on implicit parameters) or as a function y(t) depending on explicit independent variables. This is a matter of convenience, not principle.