TLDR:你可以在没有可变状态的情况下进行任何计算，但是当真正需要告诉计算机该做什么的时候，因为计算机只使用可变状态，你需要在某些时候改变一些东西。

有很多答案正确地说，没有可变状态就不能做任何有用的事情，我想用一些简单的(反)例子来支持这一点，以及一个普遍的直觉。

如果你看到任何一段被认为是“纯函数式”的代码，并且它是这样做的(不是真正的语言):

printUpToTen = map println [1..10]

这不是纯功能性的。有一个隐藏状态(stdout的状态)不仅被改变了，而且隐式地传递进来。看起来像这样的代码(同样不是真正的语言):

printUpToTen = map println stdout [1..10]

也是不纯的:即使显式地传入state (stdout)，它仍然是隐式突变的。

现在直观地说:可变状态是必要的，因为影响我们计算机的核心构建块是可变状态，这个构建块是内存。我们不能强迫计算机做任何事情，而不以某种方式操纵内存，即使我们的计算模型确实可以计算任何东西，而没有“内存”的概念。

Think of something like an old GameBoy Advance: in order to display something to the screen, you must modify the memory (there are certain addresses that are read many times a second that determine whats being put on the screen). Your computational model (pure functional programming) may not need state to operate, you may even be able to implement you model using an imperative, state manipulation model (like assembly) that abstracts the state manipulation, but at the end of the day, somewhere in you code you have to modify those addresses in memory for the device to actually display anything.

这就是命令式模型具有天然优势的地方:因为它们总是在操作状态，所以您可以非常容易地将其转换为实际修改内存。下面是一个渲染循环的例子:

while (1) {
   render(graphics_state);
}

如果你要展开循环，它看起来像这样:

render(graphics_state); // modified the memory
render(graphics_state); // modified the memory
render(graphics_state); // modified the memory
...

但在纯函数式语言中，你可能会得到这样的东西:

render_forever state = render_forever newState
    where newState = render state

展开(准确地说是压平)可以像这样可视化:

render(render(render(render(...state) // when is the memory actually changing??

// or if you want to expand it the other direction
...der(render(render(render(render(render(state) // no mutation

正如你所看到的，我们在状态上一遍又一遍地调用一个函数，状态是不断变化的，但我们从不改变内存:我们立即将它传递给下一个函数调用。即使我们的实现实际上在底层修改了一些表示状态的东西(甚至在适当的位置!)，它也不在正确的位置。在某些时候，我们需要暂停并修改内存中的正确地址，这涉及到突变。

通过使用大量的递归。

用f#(一种函数式语言)玩地字游戏。

注意，说函数式编程没有“状态”有点误导，可能是造成混淆的原因。它肯定没有“可变状态”，但它仍然可以有被操纵的值;它们只是不能就地更改(例如，您必须从旧值创建新值)。

这是一个严重的过度简化，但是想象一下你有一个OO语言，其中类上的所有属性只在构造函数中设置一次，所有方法都是静态函数。您仍然可以通过让方法获取包含计算所需的所有值的对象，然后返回带有结果的新对象(甚至可能是同一对象的新实例)来执行几乎任何计算。

将现有代码转换为这种范式可能“很难”，但这是因为它确实需要一种完全不同的思考代码的方式。但作为一个副作用，在大多数情况下，您可以免费获得大量并行机会。

附录:(关于如何跟踪需要更改的值的编辑) 当然，它们会被存储在一个不可变的数据结构中……

这不是一个建议的“解决方案”，但最简单的方法是，你可以将这些不可变的值存储到一个类似map(字典/哈希表)的结构中，以“变量名”为键。

显然，在实际解决方案中，您应该使用更明智的方法，但这确实表明，如果其他方法都不起作用，那么在最坏情况下，您可以使用这样一个贯穿调用树的映射来“模拟”可变状态。

你不可能有一种有用的纯函数式语言。总会有一定程度的可变性需要处理，IO就是一个例子。

将函数式语言视为您使用的另一种工具。它对某些事情有好处，但对其他事情没有好处。你给出的游戏例子可能不是使用函数语言的最佳方式，至少屏幕会有一个可变的状态，你不能用FP做任何事情。使用FP思考问题的方式和解决问题的类型将不同于使用命令式编程所习惯的方式。

For highly interactive applications such as games, Functional Reactive Programming is your friend: if you can formulate the properties of your game's world as time-varying values (and/or event streams), you are ready! These formulae will be sometimes even more natural and intent-revealing than mutating a state, e.g. for a moving ball, you can directly use the well-known law x = v * t. And what's better, the game's rules written such way compose better than object-oriented abstractions. For example, in this case, the ball's speed can be also a time-varying value, which depends on the event stream consisting of the ball's collisions. For more concrete design considerations, see Making Games in Elm.

我现在才开始讨论这个问题，但是我想为那些正在与函数式编程作斗争的人补充几点。

函数式语言维护与命令式语言完全相同的状态更新，但它们是通过将更新后的状态传递给后续的函数调用来实现的。这是一个沿着数轴移动的简单例子。您的状态是您当前的位置。

首先是命令式方式(在伪代码中)

moveTo(dest, cur):
    while (cur != dest):
         if (cur < dest):
             cur += 1
         else:
             cur -= 1
    return cur

现在是函数式的方式(在伪代码中)。我非常依赖三元运算符，因为我希望有命令式背景的人能够读懂这段代码。所以如果你不经常使用三元运算符(我总是避免它在我的命令式的日子)下面是它是如何工作的。

predicate ? if-true-expression : if-false-expression

您可以通过将一个新的三元表达式放在假表达式的位置来连接三元表达式

predicate1 ? if-true1-expression :
predicate2 ? if-true2-expression :
else-expression

考虑到这一点，下面是函数版本。

moveTo(dest, cur):
    return (
        cur == dest ? return cur :
        cur < dest ? moveTo(dest, cur + 1) : 
        moveTo(dest, cur - 1)
    )

这是一个简单的例子。如果这是在游戏世界中移动人，你就必须引入一些副作用，如在屏幕上绘制对象的当前位置，并根据对象移动的速度在每次调用中引入一些延迟。但你仍然不需要可变状态。

The lesson is that functional languages "mutate" state by calling the function with different parameters. Obviously this doesn't really mutate any variables, but that's how you get a similar effect. This means you'll have to get used to thinking recursively if you want to do functional programming. Learning to think recursively is not hard, but it does take both practice and a toolkit. That small section in that "Learn Java" book where they used recursion to calculate factorial does not cut it. You need a toolkit of skills like making iterative processes out of recursion (this is why tail recursion is essential for functional language), continuations, invariants, etc. You wouldn't do OO programming without learning about access modifiers, interfaces etc. Same thing for functional programming.

我的建议是做小Schemer(注意我说的是“做”而不是“读”)，然后做SICP的所有练习。当你完成时，你的大脑会和刚开始时不一样。