函数式编程:不变性应该走多远



我意识到这可能是一个相当主观的问题,但我正在从那些比我在函数编程方面更有经验的人那里寻找一些见解。

我的理解是,保持一切不变的主要动机是让事情更容易理解,并阻止错误蔓延到并行任务中。这样做的缺点是,每次您想更改数据结构时,都必须将整个数据结构复制到一个新的对象中,但要进行所需的更改。这样做可能会带来一些性能成本:虽然我不会再三考虑对小对象这样做,但如果你在处理大矩阵、张量或类似的大数据结构,这肯定会变得非常慢吗?

简而言之:

  1. 复制不可变的数据结构会对性能造成影响吗?影响有多大
  2. 如果是这样的话,你能举一个例子,说明你(个人)如何在使某个东西不可变和使其可变之间划清界限吗

据我所知,保持一切不变的主要动机是让事情更容易理解,并阻止错误蔓延到并行任务中。

这可能是主要动机。但还有其他优势。但它可以提高性能。例如,lockfreewaitfree数据结构是处理并行处理的一种方式,旨在减少锁定的开销。

这样做的缺点是,每次您想更改数据结构时,都必须将整个数据结构复制到一个新的对象中,但要进行所需的更改。

这是不正确的。您不需要复制整个数据结构。例如,手指树是函数编程中的典型数据结构。它在O(d)(与d一起)中插入树的深度。所以它有完全相同的性能。

在许多/大多数情况下,使用不可变对象会导致相同的时间复杂性,尽管算法通常写得不同(例如,列表通常是链表,因此列表处理通常旨在避免随机索引查找)。

此外,数据结构是不可变的这一事实也可以提高效率。例如,在许多编程语言中,字符串是不可变的对象。一些编程语言有一个字符串存储,它实现了轻量级模式。如果构造了一个新字符串,它会检查该字符串是否已经存在,如果是这样,则会获得指向该字符串的指针。其优点是减少了内存占用,此外,由于这些对象可以缓存,因此还可以提高性能。

会在使某个东西不可变和使其可变之间划清界限吗?

有一些像Haskell这样的编程语言,其中所有都是不可变的。在这种情况下,可变性是通过使用monad来实现的,从而在过程中传递对象的新版本。Haskell编译器往往做得很好,有时会达到与命令式编译器相同的速度。

在广泛使用不变性的语言中,复制时有机会使用"快捷方式"。副本和原件可以共享相同的结构,因为你知道它们不能从你身上改变,因为它们是不可变的。只需要创建修改后的零件。

从Clojure文档的结构来看:

所有的Clojure集合都是不可变和持久的。特别是,Clojure集合通过利用结构共享支持高效创建"已修改"版本,并保证其所有性能都能持久使用。

(强调矿)

基本上,如果你有一个列表

[0 1 2]

你把加入其中

(conj [0 1 2] 3)

这将创建一个末尾添加了3的副本。但是,因为原始和副本共享前3个元素,所以不需要复制整个列表。"副本"引用了原始结构的公共部分,以及3。

你在哪里划线?事实证明,UI很难只使用不可变对象。我几乎已经放弃了在这个领域完全避免可变性。关键是要把它限制在必要的地方。99%的函数应该包含不变性,然后将处理混乱部分(如UI回调代码)的1%隐藏起来。不过,这是一句习得的台词,很难正确沟通。

当有疑问时,让它不可变。

这样做的缺点是,每次要更改数据结构时,都必须将整个数据结构复制到一个新对象中,但要进行所需的更改。

这不完全正确。如果您的数据结构由多个节点组成(例如,通过指针链接),则只需要将路径从更改的部分复制到根。

例如,考虑这个二叉树:

|
a
/ 
b   c
/  / 
d  e f  g

如果要更改节点c中的值,只需创建ac:的修改副本

|
a'
/ 
b   c'
/  / 
d  e f  g

结构的其余部分可以重复使用。未更改的节点在树的不同版本之间共享。这种共享之所以安全,正是因为它的不变性。

最新更新