通过使用大量的递归。

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

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

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

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

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的所有练习。当你完成时，你的大脑会和刚开始时不一样。

事实上，即使在没有可变状态的语言中，也很容易有一些看起来像可变状态的东西。

Consider a function with type s -> (a, s). Translating from Haskell syntax, it means a function which takes one parameter of type "s" and returns a pair of values, of types "a" and "s". If s is the type of our state, this function takes one state and returns a new state, and possibly a value (you can always return "unit" aka (), which is sort of equivalent to "void" in C/C++, as the "a" type). If you chain several calls of functions with types like this (getting the state returned from one function and passing it to the next), you have "mutable" state (in fact you are in each function creating a new state and abandoning the old one).

It might be easier to understand if you imagine the mutable state as the "space" where your program is executing, and then think of the time dimension. At instant t1, the "space" is in a certain condition (say for example some memory location has value 5). At a later instant t2, it is in a different condition (for example that memory location now has value 10). Each of these time "slices" is a state, and it is immutable (you cannot go back in time to change them). So, from this point of view, you went from the full spacetime with a time arrow (your mutable state) to a set of slices of spacetime (several immutable states), and your program is just treating each slice as a value and computing each of them as a function applied to the previous one.

好吧，也许这并不容易理解:-)

It might seem inneficient to explicitly represent the whole program state as a value, which has to be created only to be discarded the next instant (just after a new one is created). For some algorithms it might be natural, but when it is not, there is another trick. Instead of a real state, you can use a fake state which is nothing more than a marker (let's call the type of this fake state State#). This fake state exists from the point of view of the language, and is passed like any other value, but the compiler completely omits it when generating the machine code. It only serves to mark the sequence of execution.

举个例子，假设编译器给了我们以下函数:

readRef :: Ref a -> State# -> (a, State#)
writeRef :: Ref a -> a -> State# -> (a, State#)

从这些类似haskell的声明中转换，readRef接收到类似于指向“a”类型值和假状态的指针或句柄的东西，并返回由第一个形参和新的假状态指向的“a”类型值。writeRef类似，但是改变了所指向的值。

If you call readRef and then pass it the fake state returned by writeRef (perhaps with other calls to unrelated functions in the middle; these state values create a "chain" of function calls), it will return the value written. You can call writeRef again with the same pointer/handle and it will write to the same memory location — but, since conceptually it is returning a new (fake) state, the (fake) state is still imutable (a new one has been "created"). The compiler will call the functions in the order it would have to call them if there was a real state variable which had to be computed, but the only state which there is is the full (mutable) state of the real hardware.

(了解Haskell的人会注意到我简化了很多东西，并省略了一些重要的细节。对于那些想要看到更多细节的人，看看mtl中的Control.Monad.State，以及ST和IO(又名ST RealWorld)单子。

You might wonder why doing it in such a roundabout way (instead of simply having mutable state in the language). The real advantage is that you have reified your program's state. What before was implicit (your program state was global, allowing for things like action at a distance) is now explicit. Functions which do not receive and return the state cannot modify it or be influenced by it; they are "pure". Even better, you can have separate state threads, and with a bit of type magic, they can be used to embed an imperative computation within a pure one, without making it impure (the ST monad in Haskell is the one normally used for this trick; the State# I mentioned above is in fact GHC's State# s, used by its implementation of the ST and IO monads).

下面是如何在没有可变状态的情况下编写代码:不是将变化状态放入可变变量中，而是将其放入函数的参数中。不写循环，而是写递归函数。比如这段命令式代码:

f_imperative(y) {
  local x;
  x := e;
  while p(x, y) do
    x := g(x, y)
  return h(x, y)
}

变成这样的函数代码(类似scheme的语法):

(define (f-functional y) 
  (letrec (
     (f-helper (lambda (x y)
                  (if (p x y) 
                     (f-helper (g x y) y)
                     (h x y)))))
     (f-helper e y)))

或者这个Haskellish代码

f_fun y = h x_final y
   where x_initial = e
         x_final   = loop x_initial
         loop x = if p x y then loop (g x y) else x

至于为什么函数式程序员喜欢这样做(你没有问)，你的程序中无状态的部分越多，就有越多的方法可以在不中断的情况下将这些部分组合在一起。无状态范式的强大之处在于它本身不具有无状态性(或纯粹性)，而在于它使您能够编写强大的、可重用的函数并将它们组合起来。

你可以在John Hughes的论文Why Functional Programming Matters中找到一个很好的教程，里面有很多例子。

这很简单。在函数式编程中，你可以使用任意多的变量……但前提是它们是局部变量(包含在函数中)。因此，只需将代码包装在函数中，在这些函数之间来回传递值(作为传递的参数和返回值)……这就是它的全部!

这里有一个例子:

function ReadDataFromKeyboard() {
    $input_values = $_POST[];
    return $input_values;
}
function ProcessInformation($input_values) {
    if ($input_values['a'] > 10)
        return ($input_values['a'] + $input_values['b'] + 3);
    else if ($input_values['a'] > 5)
        return ($input_values['b'] * 3);
    else
        return ($input_values['b'] - $input_values['a'] - 7);
}
function DisplayToPage($data) {
    print "Based your input, the answer is: ";
    print $data;
    print "\n";
}

/* begin: */
DisplayToPage (
    ProcessInformation (
        GetDataFromKeyboard()
    )
);

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

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