功能编程中纯函数的缺点

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,另一个用于返回值.或者以某种方式延迟调用确保实际xs只通过在末尾添加一个元素才能返回？
我知道Monad是一种可以产生副作用的方法.但Monad可以用来简单地修改输入并返回它的值吗？
也可以将xs ++ [a]更改为:xs消耗更少的内存？

Answer 1

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

xs ++ [a]

完全评估,xs必须制作副本.如果xs是懒惰生成并且没有在其他任何地方引用,那么这可能发生在恒定空间中,因此它可以在创建时进行垃圾收集.或者它可能需要一个副本xs- 但纯度允许两个列表的单元格指向相同的数据,因此数据不需要复制,只需要脊椎(由最终的缺点修改).但是如果制作副本,旧值xs仍然可用.

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

是的,可以简单地重用xs,所有需要的是创建一个新的列表单元格并让它的尾部指针指向xs.

来自评论:

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

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

Answer 2

是的,纯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]更改为:xs消耗更少的内存？

是的,这将它从O(n)最坏情况改为O(1)最坏情况分配/额外内存使用.同样适用于时间复杂性.在Haskell中处理列表时,永远不要追加到最后.如果这是您需要的,请使用差异列表.