函数式编程：不变性等

StackOverflow https://stackoverflow.com/questions/361066

题

我最近 问了一个问题 关于函数式编程，并收到（好！）引发更多问题的答案（有时学习的情况似乎如此）。这里有几个例子：

  1. 一个答案提到了不可变数据结构的优点：每个线程都可以有自己的副本。现在，对我来说，这听起来很像版本控制系统（打个比方），每个人都可以签出自己的副本，而不是锁定某人已签出的代码以使其无法被其他人修改。听起来不错。然而，在 VCS 中，如果两个人更改了相同的内容，则有“合并”更改的概念。看来这个问题肯定会出现在多线程场景中......那么，当线程看到最新数据很重要时，如何进行“合并”呢？

  2. 这个答案 讨论了在对象上循环执行操作的情况，以及如何每次使用新对象而不是更新旧对象。然而，我们可以说 bankAccount 正在非循环场景中更新——例如 GUI 银行系统。操作员单击“更改利率”按钮，这会触发一个事件（例如在 C# 中）执行类似操作 bankAccount.InterestRate = newRateFromUser. 。我觉得我在这里很密集，但希望我的例子有意义：必须有某种方式来更新对象，对吗？其他几件事可能取决于新数据。

不管怎样，如果你能帮助我理解范式转变，我将不胜感激。我记得在学习 OOP 时，在简单的过程命令式编码方法的背景下，我的大脑经历了类似的“愚蠢阶段”。

有帮助吗？

解决方案

对第 1 部分的回答：不可变对象本身不支持“合并”之类的功能，以允许组合两个线程的更新结果。为此有两个主要策略：悲观者和乐观者。如果您持悲观态度，您会认为两个线程很可能希望同时更新同一条数据。因此，您使用锁定，这样第二个线程将冻结，直到第一个线程说它已完成。如果您乐观地认为这种情况很少发生，则可以让两个线程处理它们自己的数据逻辑副本。第一个完成的线程提供新版本，另一个必须从头开始 - 只是现在它从第一个线程的更改结果开始。不过，这种昂贵的重新启动只是偶尔发生，因此总的来说，由于缺乏锁定，它的性能更好（尽管只有当您对冲突发生的可能性非常乐观时，这才是正确的）。

第2部分：纯函数式无状态语言并不能真正消除这个问题。即使是纯 Haskell 程序也可以有与之关联的状态。区别在于有状态代码具有不同的返回类型。操作状态的函数表示为对表示该状态的对象进行操作的一系列操作。在一个荒谬的例子中，考虑计算机的文件系统。每次程序修改文件内容（即使是单个字节）时，它都会创建整个文件系统的新“版本”。进而推而广之，整个宇宙的新版本。但现在让我们关注文件系统。检查文件系统的程序的任何其他部分现在可能会受到该修改字节的影响。因此 Haskell 表示，在文件系统上运行的函数必须有效地传递代表文件系统版本的对象。然后，因为手动处理这会很乏味，所以它把需求颠倒过来，说如果一个函数想要能够进行 IO，它必须返回一种容器对象。容器内部是函数想要返回的值。但容器可以作为函数也有副作用或可以看到副作用的证据。这意味着 Haskell 的类型系统能够区分带副作用的函数和“纯”函数。因此，它有助于包含和管理代码的状态，而不是真正消除它。

其他提示

想想 .Net 中的 String 类（它是一个不可变对象）。如果您对字符串调用方法，您将获得一个新副本：

String s1 = "there";
String s2 = s1.Insert(0, "hello ");

Console.Writeline("string 1: " + s1);
Console.Writeline("string 2: " + s2);

这将输出：

字符串 1：那里

字符串2：你好呀

将此行为与 StringBuilder 进行比较，后者具有基本相同的方法签名：

StringBuilder sb  = new StringBuilder("there");
StringBuilder sb2 = sb.Insert(0, "hi ");

Console.WriteLine("sb 1: " + sb.ToString());
Console.WriteLine("sb 2: " + sb2.ToString());

因为 StringBuilder 是可变的，所以两个变量都指向同一个对象。输出将是：

某人1：你好呀

某人2：你好呀

因此，一旦创建了字符串，就绝对不能更改它。s1 将始终“存在”，直到时间结束（或直到其垃圾被收集）。这在线程中很重要，因为您始终可以单步执行每个字符并打印其值，因为知道它始终会打印“那里”。如果您在创建 StringBuilder 后开始打印它，则可能会打印那里的前两个字符并获取'th'。现在，想象一下另一个线程出现广告插入“嗨”。现在的价值已经不一样了！当您打印第三个字符时，它是“hi”中的空格。所以你打印：'那里'。

关于#2...

其他几件事可能取决于新数据。

这就是纯粹主义者所说的“效果”。多个对象引用同一个可变对象的概念是可变状态的本质和问题的关键。在 OOP 中，您可能有一个 BankAccount 类型的对象“a”，如果您在不同的位置读取 a.Balance 或其他内容 次 您可能会看到不同的值。相反，在纯 FP 中，如果“a”的类型为 BankAccount，那么它是不可变的并且无论时间如何都具有相同的值。

然而，由于 BankAccount 可能是我们想要建模的对象，其状态随时间变化，因此我们会在 FP 中将该信息编码到类型中。因此，“a”可能具有“IO BankAccount”类型，或其他一些单子类型，本质上可以归结为“a”实际上是一个函数，该函数将“世界的先前状态”（或银行利率的先前状态）作为输入，或其他），并返回一个新的世界状态。更新利率将是另一种操作，其类型代表效果（例如另一个 IO 操作），因此将返回一个新的“世界”，并且可能依赖于利率（世界状态）的所有内容都将是其类型知道需要将该世界作为输入的数据。

因此，调用“a.Balance”或诸如此类的唯一可能的方法是使用这样的代码，由于静态类型，强制执行一些“让我们到现在为止的世界历史”已被正确地探查到以下点：调用，以及输入的任何世界历史都会影响我们从 a.Balance 得到的结果。

阅读 状态单子 对于了解如何纯粹地模拟“共享可变状态”可能很有用。

  1. 不可变数据结构与 VCS 不同。将不可变数据结构视为只读文件。如果它是只读的，那么无论谁在任何给定时间读取文件的哪一部分，每个人都会读取正确的信息。

  2. 这个答案正在谈论 http://en.wikipedia.org/wiki/Monad_（功能编程）

MVCC (多版本并发控制)

Rich Hickey 在他的文章中描述了您所指问题的解决方案 视频演示.

简而言之:您不是通过引用直接将数据传递给客户端，而是间接添加一层，并将引用传递给数据的引用。（好吧，实际上您希望至少多一层间接。但我们假设数据结构非常简单，比如“数组”。)
由于数据是不可变的，每次更改数据时，您都会创建更改部分的副本（如果是数组，您应该创建另一个数组！）加上您创建对所有“已更改”数据的另一个引用。
因此，对于使用第一个版本的数组的所有客户端，他们使用对第一个版本的引用。每个尝试访问第二个版本的客户端都使用第二个引用。
“数组”数据结构对于此方法来说不是很有趣，因为您无法拆分数据并且被迫复制所有内容。但对于像树这样更复杂的数据结构，数据结构的某些部分可以“共享”，因此您不必每次都复制所有内容。

详细内容请看这篇论文： 《纯函数式数据结构》 作者：克里斯·冈崎。

“不可变”的确切含义是：它没有改变。

函数式程序进行更新的方式是传递新事物。现有的值永远不会改变：您只需构建一个新值并传递它即可。很多时候，新的价值份额与旧的价值份额相同；该技术的好例子是由 cons 单元组成的列表，以及 拉链.

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top