Generalizing 'jq' and Traversal Systems using optics and standard monads

You are correct that memory allocation takes place to implement the FP, and you could call that a state mutation. The underlying computer mutates RAM.

But that's not what FP people mean by state.

RAM is an implementation detail. (You don't even strictly need RAM to compute. But that's another conversation.)

In your example, one part of the state is the list [1,2,3]. That isn't mutated when the program runs. It's passed around. The implementation probably passes it by reference - a pointer to the list - but actually the programmer can't tell and doesn't care if it's copied or passed by reference. There's no visible difference, when values can't be mutated.

The other part is [2,3,4]. As the program runs, it will be allocated in new memory, and from the programmer's point of view, it's as if the value [2,3,4] always existed, just waiting to be looked at. When it does look, that's always the value it's going to find, so in a very meaningful sense, that value is already there.

It's not usually allocated and stored in RAM until the program looks there, but it could be, it makes no difference from the perspective of the FP programmer. (In some implementations it actually might be. If you called map(f,[1,2,3]) twice it might "rediscover" the value already existing in RAM on the second call and use that.)

And the [1,2,3] might get freed at some point. But that only happens when it's not being "looked at". It gets forgotten then. (Or in an exotic implementation if there's still a reference to it, the memory containing the value might be freed, and it might be reallocated and recalculated when it's looked at again later. All invisible to the FP programmer.)

For your generator example, the implementation might create a state variable to implement it, or it might not. Either way it's hidden from the pure FP program, and it's as if the list [2,3,4] is just there, waiting to be looked at. Some implementations won't use a stateful generator like you'd think in Python though. They may instead represent the list as having a lazy tail: [2,3,lazymore...] where lazymore... is a placeholder in the list in RAM, which represents the part of the list which hasn't been looked at yet. This is lazy evaluation. The lazymore... is completely invisible to the pure FP program, because the act of looking at it (to do something useful) causes it to be replaced with the "real" calculated value, [4] in this case. Only those "real" values are visible to the program.

Overall, in the pure FP programming model, it's as if all the values exist already and never change, and they are determined by the FP expressions from other values which also never change.

The only "effect" is an implementation detail, triggered by the the act of looking at values to see what they already are, which converts lazy placeholders into useful values. The equivalence between lazy placeholder and useful value is so well hidden in pure FP that the implementation is free to do things like calculate values before they are needed or even if they are never needed, and to discard some values (putting the placeholder back) and recalculate them again later whenever it feels like. Yet to the pure FP programmer, it's always the same values.

The underlying implementation will allocate, free, move values around in memory, and perform lazy evaluation as its way of "looking at" values as requested. But those are all implementation details which are hidden from the pure FP programmer, and the details will vary between different implementations too. In practice there's still debugging and timing and memory usage visible, but not to the FP program (except through "cheating" non-pure FP escape hatches), and we think of those as part of the implementation, separate from the FP programming model.

Let's take a look at how we might write a function like `map` the (pure) functional way in a language like JS:

    const head = ([x, ...xs]) => x;
    const tail = ([x, ...xs]) => xs;
    
    const map = (list, fn) => {
      if (list.length === 0) {
        return [];
      } else {
        return [fn(head(list)), ...map(tail(list), fn)];
      }
    };
    
    map([1, 2, 3], x => x + 1); // [2, 3, 4]

We're not keeping track of any state here. Using recursion you don't need to keep track of the current element in the list for example (when you run this on a physical machine it will of course, but not at the conceptual level).

Depends on the use case. YAGNI? The presented function is very simple to read and understand what it does.

Of course in Python you could parametrize the predicates or the attributes or attribute values, and it would still be fine FP code.

Reading your other comment, I'll concede that it's not impossible to encode these things into the type system. I don't think it will scale beyond toy examples (at least until AGI is a thing). There are plenty of function names that represent highly specific business processes (and jargon) and I don't see how any type system will have enough context for that.

Less bugs does sound good, but after a minute thought there still seem to be uncountably infinite bugs even in the presence of dependent types. Just a few less than without. :)

> Not all functional languages have static typing.

Even the multi-paradigm, late-bound languages that are adding functional programming are adding static typing, e.g. TypeScript and mypy.

> No type checker will catch this error...

Sure, math is hard. In the domain of structural transformations, one's intuition combined with a decent type checker really does work, though.

Especially, I've done large refactorings of complex transformations, tracked down the typing errors, and then been pleasantly surprised when my test-suites passed the first time.

> sqrt :: double -> double

I can use QuickCheck[1]:

    prop_Sqrt_Sqr n = sqrt n * sqrt n == abs n

Because it can exploit the type system, it can then plug in various values of Double to see if squaring my square root squares properly.

[1]: http://www.cse.chalmers.se/~rjmh/QuickCheck/manual.html