Does 'foldp' violate FP's no mutable state principle?

Question

I'm learning about Elm from Seven More Languages in Seven Weeks. The following example confuses me:

import Keyboard
main = lift asText (foldp (\dir presses -> presses + dir.x) 0 Keyboard.arrows)

foldp is defined as:

Signal.foldp : (a -> b -> b) -> b -> Signal a -> Signal b

It appears to me that:

• the initial value of the accumulator presses is only 0 on the first evaluation of main
• after the first evaluation of main it seems that the initial value of presses is whatever the result of function (a -> b -> b), or (\dir presses -> presses + dir.x) in the example, was on the previous evaluation.

If this is indeed the case, then isn't this a violation of functional programming principles, since main now maintains internal state (or at least foldp does)?

How does this work when I use foldp in multiple places in my code? Does it keep multiple internal states, one for each time I use it?

The only other alternative I see is that foldp (in the example) starts counting from 0, so to say, each time it's evaluated, and somehow folds up the entire history provided by Keyboard.arrows. This seems to me to be extremely wasteful and sure to cause out-of-memory exceptions for long run times.

Am I missing something here?

Answer 1

How it works

Yes, foldp keeps some internal state around. Saving the entire history would be wasteful and is not done.

If you use foldp multiple times in your code, doing distinct things or having distinct input signals, then each instance will keep it's own local state. Example:

import Keyboard

plus  = (foldp (\dir presses -> presses + dir.x) 0 Keyboard.arrows)
minus = (foldp (\dir presses -> presses - dir.x) 0 Keyboard.arrows)
showThem p m = flow down (map asText [p, m])
main  = lift2 showThem plus minus

But if you use the resulting signal from a foldp twice, only one foldp instance will be in your compiled program, the resulting changes will just be used in two place:

import Keyboard

plus  = (foldp (\dir presses -> presses + dir.x) 0 Keyboard.arrows)
showThem p m = flow down (map asText [p, m])
main  = lift2 showThem plus plus

The main question

If this is indeed the case, then isn't this a violation of functional programming principles, since main now maintains internal state (or at least foldp does)?

Functional programming doesn't have some great canonical definition that everybody uses. There are many examples of functional programming languages that allow for the use of mutable state. Some of these programming languages show you that a value is mutable in the type-system (you could see Haskell's State a type as such, it really depends on your viewpoint though).

But what is mutable state? What is a mutable value? It's a value inside the program, that is mutable. That is, it can change. It can be different things at different times. Ah, but we know how Elm calls values at change over time! That's a Signal.
So really a Signal in Elm is a value that can change over time, and can therefore be seen as a variable, a mutable value, or mutable state. It's just that we manage this value very strictly by allowing only a few well-chosen manipulations on Signals. Such a Signal can be based on other Signals in your program, or come from a library or come from the outside world (think of inputs like Mouse.position). And who knows how the outside world came up with that signal! So allowing your own Signals to be based on the past value of Signals is actually ok.

Conclusion / TL;DR

You could see Signal as a safety wrapper around mutable state. We assume that signals that come from the outside world (as input to your program) are not predictable, but because we have this safety wrapper that only allows lift/sample/filter/foldp, the program you write is otherwise completely predictable. Side-effects are contained and managed, therefore I think it's still "functional programming".