最近我读了很多关于函数式编程的东西,大部分我都能理解,但有一件事我就是搞不懂,那就是无状态编码。在我看来,通过删除可变状态来简化编程就像通过删除仪表盘来“简化”一辆汽车:最终产品可能更简单,但希望它能与最终用户交互。

几乎我能想到的每个用户应用程序都将状态作为核心概念。如果你写了一个文档(或一个SO post),状态会随着每一个新的输入而改变。或者如果你玩电子游戏,会有大量的状态变量,从所有角色的位置开始,这些角色往往会不断移动。如果不跟踪不断变化的值,您怎么可能做任何有用的事情呢?

每次我发现一些讨论这个问题的东西,它都是用真正的技术函数语言写的,假设我没有浓厚的FP背景。有谁知道如何向那些对命令式编码有很好的、扎实的理解,但在函数方面完全是n00b的人解释这一点吗?

编辑:到目前为止,一堆回复似乎试图让我相信不可变值的优点。我懂你的意思。这很有道理。我不明白的是,在没有可变变量的情况下,如何跟踪必须不断变化的值。


当前回答

我觉得这里有点误会。纯函数式程序有状态。不同之处在于该状态是如何建模的。在纯函数式编程中,状态是由接受某个状态并返回下一个状态的函数操作的。然后通过将状态传递给纯函数序列来实现状态排序。

甚至全局可变状态也可以这样建模。例如,在Haskell中,程序是一个从World到World的函数。也就是说,你传入整个宇宙,程序返回一个新的宇宙。但是,在实践中,您只需要传入您的程序实际感兴趣的部分。程序实际上返回一系列动作,作为程序运行的操作环境的指令。

您希望从命令式编程的角度对此进行解释。好的,让我们看一些用函数式语言编写的非常简单的命令式编程。

考虑下面的代码:

int x = 1;
int y = x + 1;
x = x + y;
return x;

相当标准的命令式代码。没有做什么有趣的事情,但这是可以用来说明的。我想你们会同意这里涉及到国家。变量x的值随时间变化。现在,让我们稍微改变一下符号,发明一个新的语法:

let x = 1 in
let y = x + 1 in
let z = x + y in z 

加上括号使它的意思更清楚:

let x = 1 in (let y = x + 1 in (let z = x + y in (z)))

可以看到,状态是由一系列纯表达式建模的,这些纯表达式绑定了下面表达式的自由变量。

您会发现这个模式可以建模任何类型的状态,甚至IO。

其他回答

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

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

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

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

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

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

简单的回答是:你不能。

那么不变性有什么好大惊小怪的呢?

If you're well-versed in imperative language, then you know that "globals are bad". Why? Because they introduce (or have the potential to introduce) some very hard-to-untangle dependencies in your code. And dependencies are not good; you want your code to be modular. Parts of program not influence other parts as little as possible. And FP brings you to the holy grail of modularity: no side effects at all. You just have your f(x) = y. Put x in, get y out. No changes to x or anything else. FP makes you stop thinking about state, and start thinking in terms of values. All of your functions simply receive values and produce new values.

这有几个优点。

首先,没有副作用意味着程序更简单,更容易推理。不用担心引入程序的新部分会干扰并使现有的正在工作的部分崩溃。

其次,这使得程序的可并行性微不足道(有效的并行化是另一回事)。

第三,有一些可能的性能优势。假设你有一个函数:

double x = 2 * x

现在你输入一个3的值,得到一个6的值。每一次。但是在祈使句中也可以这样做,对吧?是的。但问题是,在命令式中,你可以做更多的事情。我可以:

int y = 2;
int double(x){ return x * y; }

但我也可以

int y = 2;
int double(x){ return x * (y++); }

命令式编译器不知道我是否会有副作用,这使得优化更加困难(即double 2不必每次都是4)。函数函数知道我不会——因此,它可以在每次看到“double 2”时进行优化。

现在,即使每次创建新值对于复杂类型的值在计算机内存方面看起来是难以置信的浪费,但它不必如此。因为,如果你有f(x) = y,并且x和y的值“基本相同”(例如,只有少数叶子不同的树),那么x和y可以共享部分内存——因为它们都不会突变。

如果这个不可变的东西这么好,为什么我说没有可变状态就不能做任何有用的事情。如果没有可变性,整个程序就是一个巨大的f(x) = y函数。同样的道理也适用于程序的所有部分:只是函数,而且是“纯粹”意义上的函数。我说过,这意味着每次都是f(x) = y。因此,例如readFile("myFile.txt")每次都需要返回相同的字符串值。不是很有用。

因此,每个FP都提供了一些突变状态的方法。“纯”函数语言(例如Haskell)使用一些可怕的概念(如单子)来做到这一点,而“不纯”函数语言(例如ML)则直接允许这样做。

当然,函数式语言还带来了许多其他优点,使编程更加高效,比如一类函数等。

或者如果你玩电子游戏,有 大量的状态变量,开始 所有的位置 角色,他们倾向于移动 不断。你怎么可能呢 没有记录任何有用的东西 改变价值观?

如果您感兴趣,这里有一系列描述使用Erlang进行游戏编程的文章。

您可能不喜欢这个答案,但在使用它之前,您不会得到函数式程序。我可以发布代码示例并说“这里,你看不出来吗”——但如果你不理解语法和基本原理,那么你的眼睛就会呆滞。从您的角度来看,我似乎在做与命令式语言相同的事情,但只是设置了各种界限,有意地使编程更加困难。在我看来,你只是在经历Blub悖论。

一开始我持怀疑态度,但几年前我跳上了函数式编程的火车,并爱上了它。函数式编程的诀窍在于能够识别模式、特定的变量赋值,并将命令式状态移动到堆栈中。例如,for循环变成了递归:

// Imperative
let printTo x =
    for a in 1 .. x do
        printfn "%i" a

// Recursive
let printTo x =
    let rec loop a = if a <= x then printfn "%i" a; loop (a + 1)
    loop 1

它不是很漂亮,但我们在没有突变的情况下得到了相同的效果。当然,在任何可能的情况下,我们都喜欢避免循环,只是将它抽象出来:

// Preferred
let printTo x = seq { 1 .. x } |> Seq.iter (fun a -> printfn "%i" a)

Seq。Iter方法将对集合进行枚举,并为每个项调用匿名函数。非常方便:)

我知道,打印数字并不令人印象深刻。然而,我们可以在游戏中使用相同的方法:在堆栈中保持所有状态,并在递归调用中使用我们的更改创建一个新对象。这样,每一帧都是游戏的无状态快照,其中每一帧只是创建一个全新的对象,其中包含需要更新的无状态对象的所需更改。它的伪代码可能是:

// imperative version
pacman = new pacman(0, 0)
while true
    if key = UP then pacman.y++
    elif key = DOWN then pacman.y--
    elif key = LEFT then pacman.x--
    elif key = UP then pacman.x++
    render(pacman)

// functional version
let rec loop pacman =
    render(pacman)
    let x, y = switch(key)
        case LEFT: pacman.x - 1, pacman.y
        case RIGHT: pacman.x + 1, pacman.y
        case UP: pacman.x, pacman.y - 1
        case DOWN: pacman.x, pacman.y + 1
    loop(new pacman(x, y))

命令式版本和函数式版本是相同的,但是函数式版本显然没有使用可变状态。函数式代码将所有状态保存在堆栈上——这种方法的好处是,如果出现错误,调试很容易,您所需要的只是堆栈跟踪。

这可以扩展到游戏中任意数量的对象,因为所有对象(或相关对象的集合)都可以在自己的线程中呈现。

几乎每一个用户应用程序我 可以把国家看作一个核心吗 的概念。

在函数式语言中,我们不是改变对象的状态,而是简单地返回一个带有我们想要的更改的新对象。它比听起来更有效率。例如,数据结构很容易表示为不可变数据结构。例如,堆栈是出了名的容易实现:

using System;

namespace ConsoleApplication1
{
    static class Stack
    {
        public static Stack<T> Cons<T>(T hd, Stack<T> tl) { return new Stack<T>(hd, tl); }
        public static Stack<T> Append<T>(Stack<T> x, Stack<T> y)
        {
            return x == null ? y : Cons(x.Head, Append(x.Tail, y));
        }
        public static void Iter<T>(Stack<T> x, Action<T> f) { if (x != null) { f(x.Head); Iter(x.Tail, f); } }
    }

    class Stack<T>
    {
        public readonly T Head;
        public readonly Stack<T> Tail;
        public Stack(T hd, Stack<T> tl)
        {
            this.Head = hd;
            this.Tail = tl;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Stack<int> x = Stack.Cons(1, Stack.Cons(2, Stack.Cons(3, Stack.Cons(4, null))));
            Stack<int> y = Stack.Cons(5, Stack.Cons(6, Stack.Cons(7, Stack.Cons(8, null))));
            Stack<int> z = Stack.Append(x, y);
            Stack.Iter(z, a => Console.WriteLine(a));
            Console.ReadKey(true);
        }
    }
}

上面的代码构造了两个不可变列表,将它们附加在一起以形成一个新列表,并附加结果。应用程序中的任何地方都不使用可变状态。它看起来有点笨重,但这只是因为c#是一种冗长的语言。下面是f#中的等效程序:

type 'a stack =
    | Cons of 'a * 'a stack
    | Nil

let rec append x y =
    match x with
    | Cons(hd, tl) -> Cons(hd, append tl y)
    | Nil -> y

let rec iter f = function
    | Cons(hd, tl) -> f(hd); iter f tl
    | Nil -> ()

let x = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))
let y = Cons(5, Cons(6, Cons(7, Cons(8, Nil))))
let z = append x y
iter (fun a -> printfn "%i" a) z

No mutable necessary to create and manipulate lists. Nearly all data structures can be easily converted into their functional equivalents. I wrote a page here which provides immutable implementations of stacks, queues, leftist heaps, red-black trees, lazy lists. Not a single snippet of code contains any mutable state. To "mutate" a tree, I create a brand new one with new node I want -- this is very efficient because I don't need to make a copy of every node in the tree, I can reuse the old ones in my new tree.

使用一个更重要的例子,我还编写了这个完全无状态的SQL解析器(或者至少我的代码是无状态的,我不知道底层词法库是否是无状态的)。

无状态编程与有状态编程一样具有表现力和强大的功能,它只需要一点点练习来训练自己开始无状态思考。当然,“尽可能使用无状态编程,必要时使用有状态编程”似乎是大多数非纯函数式语言的座右铭。当函数式方法不那么干净或有效时,求助于变量并没有什么坏处。

我觉得这里有点误会。纯函数式程序有状态。不同之处在于该状态是如何建模的。在纯函数式编程中,状态是由接受某个状态并返回下一个状态的函数操作的。然后通过将状态传递给纯函数序列来实现状态排序。

甚至全局可变状态也可以这样建模。例如,在Haskell中,程序是一个从World到World的函数。也就是说,你传入整个宇宙,程序返回一个新的宇宙。但是,在实践中,您只需要传入您的程序实际感兴趣的部分。程序实际上返回一系列动作,作为程序运行的操作环境的指令。

您希望从命令式编程的角度对此进行解释。好的,让我们看一些用函数式语言编写的非常简单的命令式编程。

考虑下面的代码:

int x = 1;
int y = x + 1;
x = x + y;
return x;

相当标准的命令式代码。没有做什么有趣的事情,但这是可以用来说明的。我想你们会同意这里涉及到国家。变量x的值随时间变化。现在,让我们稍微改变一下符号,发明一个新的语法:

let x = 1 in
let y = x + 1 in
let z = x + y in z 

加上括号使它的意思更清楚:

let x = 1 in (let y = x + 1 in (let z = x + y in (z)))

可以看到,状态是由一系列纯表达式建模的,这些纯表达式绑定了下面表达式的自由变量。

您会发现这个模式可以建模任何类型的状态,甚至IO。

只是做同一件事的不同方式。

Consider a simple example such as adding the numbers 3, 5, and 10. Imagine thinking about doing that by first changing the value of 3 by adding 5 to it, then adding 10 to that "3", then outputting the current value of "3" (18). This seems patently ridiculous, but it is in essence the way that state-based imperative programming is often done. Indeed, you can have many different "3"s that have the value 3, yet are different. All of this seems odd, because we have been so ingrained with the, quite enormously sensible, idea that the numbers are immutable.

现在,当您将值设置为不可变时,考虑添加3、5和10。3加5得到另一个值8,然后再加10得到另一个值18。

这是做同样事情的等价方法。所有必要的信息都存在于这两种方法中,只是形式不同。其中,信息以状态的形式存在,并存在于改变状态的规则中。在另一种情况下,信息存在于不可变数据和函数定义中。