4

函数式编程中的纯函数是没有副作用的函数。其含义之一是它不能改变输入参数的值。这可以被视为内存利用率的劣势吗？
例如，假设我有一个函数，它只接受一个列表并在其中添加另一个元素。在 C++ 中，它可能很简单


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

这个函数显然不会使用比传递对象已经占用的更多内存。
但是在 Haskell 中也会出现这样的情况。

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

现在在这个计算中，因为 xs 没有改变它的值。所以我是否正确地说，有时该函数将消耗 xs 的内存双倍大小，一个用于 xs，另一个用于返回值。或者以某种方式延迟调用确保实际上 xs 仅通过在最后添加一个元素来返回？
我知道 Monad 是一种可以产生副作用的方法。但是 Monad 可以用来简单地修改输入并返回它的值吗？
也可以将 xs ++ [a] 更改为 a:xs 消耗更少的内存吗？

4

6 回答 6

10

纯度意味着函数不能进行破坏性更新，所以如果

xs ++ [a]

已全面评估，xs必须制作一份副本。如果延迟生成并且没有在其他任何地方引用，则可能会在恒定空间中发生这种情况xs，因此可以在创建时对其进行垃圾收集。或者它可能需要一个副本xs- 但纯度允许两个列表的单元格指向相同的数据，因此不需要复制数据，只需复制脊椎（由最终的缺点修改）。但如果制作了副本，旧值xs仍然可用。

也可以将 xs ++ [a] 更改为 a:xs 消耗更少的内存吗？

是的，可以简单地重用xs，只需要创建一个新的列表单元格并让它的尾指针指向xs。

来自评论：

我不希望 C++ 函数是纯的。我希望它改变输入的状态。这就是我想成为问题的重点。

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

于 2012-12-20T15:00:51.090 回答
8

是的，纯 FP 可能比命令式编程更占用内存，但这取决于您编写程序的方式以及编译器的智能程度。Haskell 编译器尤其具有非常强大的优化器，并且可能能够将纯 FP 代码转换为可重用分配内存的非常高效的机器代码。但是，这需要编写好的 FP 代码，因为即使是最聪明的编译器也不会包含优化来处理那些只模拟具有表面相似 FP 结构的命令式程序的程序。

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

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

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

v.append(a);

那么这可能会或可能不会分配，具体取决于v.

或者以某种方式延迟调用确保实际上 xs 仅通过在最后添加一个元素来返回？

取决于表达式在其上下文中的实现和使用。当xs ++ [a]被完全评估时，它会复制整个列表xs。如果它被部分评估，它可能会在 none 和len(xs).

也可以将 xs ++ [a] 更改为 a:xs 消耗更少的内存吗？

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

于 2012-12-20T14:59:36.673 回答
4

我认为您的两个示例之间的相关区别在于数据结构的选择，而不是纯粹与不纯的问题本身。

您可以在这两种方法中使用单链表，也可以在两种方法中使用具有恒定时间更新的数组。在纯粹的情况下，对数据结构的更新可能会在语义上进行复制，但这并不一定意味着它会在物理上这样做。

例如，绳索是不可变数组的一种变体，它允许恒定时间连接。您还可以通过在内部使用写时复制方案来获得具有恒定时间功能更新的不可变数组抽象（其中 a.set(i, x) 语义上返回副本），该方案仅在您实际访问时才执行物理副本创建新版本后的旧版本（即，如果您利用纯数据结构的持久性能力，这在不纯的情况下不可用）。

于 2012-12-20T15:45:14.430 回答
3

现在在这个计算中，因为 xs 没有改变它的值。所以我是否正确地说，有时该函数将消耗 xs 的内存双倍大小，一个用于 xs，另一个用于返回值。

不必要。拥有不可变数据的优点是可以共享。所以编译器可以在这种情况下通过共享 xs 来优化。所以大小将与 c++ 的情况相同。

或者以某种方式延迟调用确保实际上 xs 仅通过在最后添加一个元素来返回？

懒惰只是意味着在实际需要该值时进行评估，它并不能保证更少的内存使用。另一方面，由于懒惰而创建的 thunk 可能会使用更多内存。

我知道 Monad 是一种可以产生副作用的方法。但是 Monad 可以用来简单地修改输入并返回它的值吗？

你说对了一部分。Monad 用于编写具有副作用的代码。您可以很好地使用可变向量并编写与 IO monad 中的 c++ 示例非常相似的代码。

也可以将 xs ++ [a] 更改为 a:xs 消耗更少的内存吗？

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

您始终可以分析您的代码并检查内存消耗，这是学习这一点的最佳方式。

于 2012-12-20T15:08:13.550 回答
3

ab·stract·tion [ab-strak-shuh n]

除了具体的现实、特定的对象或实际实例之外，将某物视为一般品质或特征的行为。

权衡

平衡所有无法同时实现的因素

泄漏抽象

在某种程度上，所有重要的抽象都是泄漏的。

函数式编程可以被视为一种抽象，并且由于所有抽象都泄漏，因此需要做出一些权衡。

于 2012-12-20T15:01:03.767 回答
1

不同的语言有不同的常用习语，实现者努力使这些习语尽可能有效。我不会假设因为某些东西在 C++ 中需要额外的开销，所以在另一种语言中也是如此，就像我不会假设另一种语言中最有效的习语在 C++ 中最有效一样。

话虽如此：我目前正在开发一个我们经常返回的大型高性能应用程序，std::vector我们还没有发现这是一个问题。像 NRVO 和移动语义这样的东西最终意味着这在 C++ 中也可以非常有效。

于 2012-12-20T15:03:25.813 回答