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

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

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

[2] https://rosettacode.org/wiki/Sorting_algorithms/Quicksort

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

I can't find a quicksort implementation on the other side of that link.

Sorry, I meant to say you could pretty easily make quicksort using the techniques in that link.

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

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

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.

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

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.

I don't understand the context of that E example so I'm not sure what it means... Is the value of E being mutated as in an algorithm, or does it just have two different values for different inputs like a function?

I can't find that at feynmanlectures.info, but I think it's describing the electric field in an idealized capacitor -- so yes, a function, as you'd expect. I don't know where the idea comes from that you write basic physics as 'twere Fortran programs.

If Feynman had used something like imperative programming in the Lectures, I wouldn't have been as baffled as (most of?) the rest of a class of physics undergraduates confronted with "LET I=I+1" in the introductory programming class. So I have some empirical evidence from the time when your first computer might be a PDP-10 down the road from Tony Hoare, that imperative programming is really unnatural for physicists.

You missed my point. Probably I expressed it poorly.

In a physics lecture, the audience is reasonably smart but slow - so you can use compact natural language flavored instructions: e.g. "as we take the limit of x to zero, expression(x) goes to c" which change values of variables. In programming, the agent being addressed is analogous to Turing's dumb schoolboy - it's very literal and needs easy to interpret instructions for each step so: c "= trytocomputelimit(f,x)". In both cases, the state of the calculating agent changes as it follows the steps of the calculation.

In defence of physicists, a few references are needed for these assertions, like them associating mathematical functions with a stateful "calculating agent".

I gave a reference to Feynman's note. The "stateful calculating agent" is the physicist or student.

The universe can be modeled at least as naturally as a composition of functions of type (Time -> a) as a mutation upon a global mutable state.