The key with functional programming is not that there is no state, it's that there is explicit state.
What this means is, that your state is passed around as a parameter to your functions. It's an actual value, that you can get your hands on, look at, and pass to other functions.
For example, let's look at the Dynamic Programming method of calculating the Fibonacci numbers. In an imperative language, you'd have something like this:
def fib(n):
A = {}
A[0] = 0
A[1] = 1
for i in [2 .. n+1]:
A[i] = A[i-1] + A[i-2]
return A[n]
To do this without state, you just have to explicitly pass your store around. Using Haskell-ish syntax:
fib n = fibHelper 2 n {(1,1), (0,0)}
fibHelper i end cache =
if
i > end
then
lookup end cache
else
let
newVal = (lookup (i-1) cache) + (lookup (i-2) cache)
newCache = insert i newVal cache
in
fibHelper (i+1) end newCache
Now, this is a bit contrived, since you don't need the whole array for the Fibonacci numbers, but you can imagine using this for more complicated dynamic programming problems like Knapsack, where you do need the entire set of previously computed values.
The key thing to understand here is that insert is a function which takes a store, and returns a new store, which is equal to the original with a new value added. The original value of cache doesn't get destroyed, so if you had an application where you needed some sort of "undo" operation, you could keep track of your state's history.
You might say "but that looks inefficient! You're creating a whole new store each time!" However, usually in functional languages, these things are implemented cleverly using references, so that there aren't whole new copies of the data lying around.
It's also worth mentioning that this pattern of having a state parameter, passing it around as your computation progresses, and modifying it, is very common. People have invented abstractions, like the State monad, which allow you to write things that look imperative, but which are purely functional "under the hood."
