函数式编程中纯函数的缺点

Question

在函数式编程中，纯函数是指没有副作用的函数。其中一个意思是它不能改变输入参数的值。这是否可以看作对内存利用的不利影响？例如，假设我有一个简单的函数，它只需要一个列表并在其中添加另一个元素。在C++中，它可能很简单，如下所示：

void addElem(std::vector& vec, int a) { vec.insert(a); }

这个函数显然不会使用比传递对象已经占用的更多的内存。

但在Haskell中，同样的功能将变成这样：

addElem :: [Int] -> Int -> [Int] addElem xs a = xs ++ [a]

现在，在这个计算中，由于xs的值没有发生变化，所以我说这个函数在某个时候将消耗掉两倍大小的内存，一个为xs，另一个为返回值。或者，惰性调用确保实际上只通过在末尾添加一个元素来返回xs吗？

我知道Monad是一种具有副作用的方法。但是Monad能否用于简单地修改输入并返回其值？同时，将xs ++ [a]更改为a：xs是否会消耗更少的内存？

- Manoj R

---

在这种情况下，内存消耗是质量问题，而不是编程范例的基本属性。 - PlasmaHH

这两段代码的功能不同。C++代码应该创建一个新向量，将'vec'复制到新向量中，将'a'附加到新向量中，并返回新向量。 - brian beuning

在函数式编程语言中，解决这个问题的“经典”方法是使用单向链表。你可以在不修改列表其余部分的情况下将另一个节点添加到开头。然后，“尾巴”被原始列表和新列表共享。 - Steve Jessop

@ManojR: 那么你的问题是错误的，因为它们不是相同的函数。如果我在多线程应用程序中使用您的C ++版本，而不必担心其他线程插入元素时我不希望出现的情况，我能否安全使用它？另外，如果该向量从未被使用怎么办？如果向量具有多个元素，则在这种情况下C ++肯定会使用更多内存。或者如果向量在构造后仅遍历一次，然后被丢弃--在这种情况下，C ++可能会使用更多内存。 - C. A. McCann

@SteveJessop说：意图并不相似，如果Haskell的写法想要与C++代码类似的话是错误的，此外，如果没有更多的上下文信息，关于哪种方法使用了更多的内存甚至无法回答。在许多实际情况下，Haskell列表的惯用用法将比“等价”的C++向量消耗更少的内存，但在其他情况下，它们将比“等价”的向量使用更多的内存。这个问题本身就是无意义的。 - C. A. McCann

Answer 1

纯函数意味着该函数不能进行破坏性的更新操作，因此如果：

xs ++ [a]

当完全评估后，必须制作 xs 的副本。如果 xs 是惰性生成的且未在其他任何地方引用，则可以在恒定空间中完成，因此它在创建时可以被垃圾回收。或者需要除 xs 之外的一份副本 - 但是纯度允许两个列表的单元格指向相同数据，因此无需复制数据，只需复制脊柱（由最终的 cons 修改）。但是，如果进行了复制，则仍然可以使用旧值 xs。

将 xs ++ [a] 更改为 a:xs 是否可以更少地消耗内存？

是的，那种情况可以简单地重用 xs，所需的所有内容都是创建一个新的列表单元并使其尾指针指向 xs。

来自评论：

我不希望 C++ 函数是纯的。我希望它改变输入的状态。这就是我想问的问题的全部意义。

在这种情况下，您需要一个 非纯 函数/操作。对于某些数据结构而言，实现这一点是可能的，但对于列表而言，必须复制/重新构造单元格。但是，向 std::vector<T> 添加元素也可能需要重新分配。

- Daniel Fischer

Answer 2

是的，纯函数式编程可能比命令式编程更消耗内存，但这取决于您编写程序的方式以及您的编译器有多聪明。特别是Haskell编译器具有非常强大的优化器，并且可以将纯函数式代码转换为重复使用已分配内存的相当有效的机器代码。不过，这需要编写良好的函数式编程代码，因为即使最聪明的编译器也不会包括优化来处理只是模拟具有表面上类似FP结构的命令式程序的程序。

请注意，您的C ++示例无效。如果您的意思是：

v[0] = a;  // assuming v.size() > 0

那么这并不会进行任何分配。如果你的意思是

v.append(a);

取决于v的容量大小，它可能会分配或不分配。

或者通过某种惰性调用方式，只通过在末尾添加一个元素来确保实际上只返回了xs？

这取决于实现和表达式在其上下文中的使用。当完全评估xs ++ [a]时，它会复制整个列表xs。如果部分评估，则可能在零到len(xs)之间进行任意数量的分配。

将xs ++ [a]更改为a：xs是否会消耗更少的内存？

是的，这将将最坏情况下的额外内存使用/分配从O（n）更改为O（1）。时间复杂度也是如此。在处理Haskell中的列表时，永远不要追加到末尾。如果您需要，请使用差异列表。

- Fred Foo

Answer 3

我认为你两个例子之间相关的不同之处在于数据结构的选择，而不是单纯与不纯的问题本身。

你可以在两种方法中都使用单向链表，也可以使用具有常数时间更新的数组。在纯函数情况下，对于数据结构的更新可能会在语义上产生一个副本，但这并不一定意味着它物理上也会这样做。

例如，Ropes是不可变数组的一种变体，允许常数时间连接。你还可以通过内部使用写时复制机制，仅在你实际访问旧版本后才执行物理复制（即如果使用了纯数据结构的持久性功能，这在不纯函数情况下是不可用的），从而使用具有常数时间函数更新的不可变数组抽象（其中 a.set(i, x) 在语义上返回一个副本）。

- Andreas Rossberg

Answer 4

抽象 [chōu xiàng]

将某物看作一般的品质或特征，而不是具体的现实、具体的对象或实际的例子。

权衡 [quán héng]

一种平衡各种因素的方法，这些因素不能同时得到满足。

漏洞抽象 [lòu dòng chōu xiàng]

所有非微不足道的抽象，都在某种程度上有漏洞。

函数式编程可以被视为一种抽象，由于所有抽象都有漏洞，因此需要进行一些权衡。

- Matt Fenwick

---

抽象只有在你允许它们泄漏时才会泄漏。在我们的领域中，当那些可能性无法被静态捕获的影响仍然被允许发生时，这种情况就会发生 - 非终止、异常等等。 - isekaijin

@EduardoLeón 是“泄漏的抽象”主张的来源。异常可以静态地被“捕获”。 - Matt Fenwick

Answer 5

现在，在这个计算过程中，由于xs的值没有改变。所以，我可以说在某个时间点函数将消耗xs两倍大小的内存，一部分用于存储xs，另一部分用于存储返回值。

不一定。具有不可变数据的优势是它可以被共享。因此编译器可以通过共享xs来进行优化。所以大小将保持与c++相同。

惰性只是表示在实际需要该值时才进行求值，它不能保证使用更少的内存。而与之相关的thunks可能会使用更多的内存。

我知道Monad是拥有副作用的方法，但是Monad能否被用于修改输入并返回其值呢?

你部分正确。Monad被用于组合具有副作用的代码。你完全可以使用可变向量，并在IO Monad中编写非常类似于你的c++示例的代码。

同时，将xs ++ [a] 改为 a:xs 能够消耗更少的内存吗？

这取决于编译器，但我认为它会复制整个列表并在末尾添加元素。(我不是这方面的专家)。

你总是可以对你的代码进行分析和检查内存消耗，这是了解它的最佳方式。

- Satvik

Answer 6

不同的语言有不同的常见习语，实现者们努力使这些习语尽可能有效。我不会假设因为在C++中某些事情需要额外的开销，同样的情况也会出现在另一种语言中，就像我不会假设在另一种语言中最有效的习语也是在C++中最有效的。

话虽如此：我目前正在开发一个大型高性能应用程序，在其中我们经常返回std::vector，并且我们没有发现这是个问题。NRVO和移动语义等因素意味着在C++中这可以非常高效。

- James Kanze