在Haskell中移动或复制（与C++相比）

Question

在Haskell中移动或复制（与C++相比）

3

请看下面这两个C++函数及其使用示例：

vector<int> makeVect() {
  vector<int> v = {1,2,3};
  return v;
}

//usage
auto v = makeVect(); //vector is moved

void addFour(vector<int> &v) {
  v.push(4);
}

//usage
addFour(v); //v is passed in as reference

两种情况下都不会发生复制，这非常高效。

以下是对应的Haskell函数和用法：

makeVect :: (Num a) => [a]
makeVect = [1,2,3]

--usage
--Q1: is [1,2,3] copied or moved to v?
let v = makeVect

addFour :: (Num a) => [a] -> [a]
addFour xs = xs ++ [4]

--usage
--Q2: is the parameter copied or moved into the function?
--Q3: on return, is the result copied or moved out of the function?
addFour v

代码中有Q1、Q2、Q3三个问题。Haskell是否会移动或复制数据？是否有方法可以控制它？在这些情况下，Haskell与C++相比效率如何？

- dan-3

5

在 Haskell 中，一切都是不可变的，因此 没有任何东西 会被复制 :-) - Kerrek SB

2

你不能像那样直接比较两种不同的编程语言。C++可能会以一种（可能是优化的）方式执行某些操作，而另一种语言（即使与C这样密切相关）可能会以完全不同的方式执行相同的操作（但也可能是不同的优化方式）。 - Some programmer dude

@DavidRodríguez-dribeas 实际上 String s = "Hi".clone(); 会抛出异常。然而这个可以：String s = new String("Hi");。 - Pedro Rodrigues

1

@PedroRodrigues：感谢您的修复。如果不明显的话，我不会编写Java :) - David Rodríguez - dribeas

1

请注意，您的C++示例实际上并不涉及移动语义。即使在C++03中，大多数编译器也会在此处使用返回值优化，即根本不会以任何方式返回任何内容！该函数将简单地在原地构造向量，即在其自己的堆栈范围下，在稍后由调用函数作为v使用的内存位置下方。但是，这种考虑通常对于垃圾收集语言总体而言都没有意义，尤其是对于Haskell而言，因为数据结构从不驻留在堆栈上。 - leftaroundabout

显示剩余4条评论

4个回答

7

问题1：没有必要复制makeVect，因为我们肯定知道列表不能更改（列表是不可变的）。我希望编译器将v和makeVect指向同一个列表。

问题2：与问题1相同的推理，没有必要复制。

问题3：由于列表是不可变的，插入值到末尾需要进行复制。请注意，如果在列表开头插入值，则不需要复制任何内容。创建新列表后，可以将其返回给调用者而无需复制。

当然，这都是实现细节；由于数据结构是不可变的，无论它们被复制还是共享，程序的行为都是相同的。由编译器决定哪个方案最佳，据我所知，无法对其进行控制。

就效率而言，情况各不相同。某些操作可以在不复制任何内容的情况下完成（如向列表开头添加元素），因此它们的性能将与C++类似。但其他操作需要复制原始数据结构的大部分内容（如更改数组中的元素），这些操作实际上比它们在C++中的相应操作要慢得多。这并不一定意味着Haskell没有针对某些问题的高效解决方案，它只是意味着C++和Haskell是非常不同的语言，C++中有效的方法并不一定是在Haskell中最好的方式。

- Pedro Rodrigues

6

这是一张示意图，展示了程序在不同阶段内存中值的布局。

最初你写下makeVect = [1, 2, 3]。在内存中的布局类似于：

                1 : 2 : 3 : []
// makeVect ----^

现在，如果您写x = makeVect，您不需要复制任何东西-您只需告诉x指向与makeVect当前指向相同的位置即可。

//        x -----v
                 1 : 2 : 3 : []
// makeVect -----^

然而，当你写addFour x时，你需要一个列表，其最后一个元素为4。目前你所拥有的唯一列表的最后一个元素是3，所以你需要一个新列表。

//         x ----v
                 1 : 2 : 3 : []
//  makeVect ----^
// addFour x ----v
                 1 : 2 : 3 : 4 : []

如果您将 4 追加到列表中，而不是在前面添加 0，则无需创建新列表。您可以添加一个带有自己指针的额外内存位置，因此内存布局类似于：

//        x -------v
               0 : 1 : 2 : 3 : []
// addZero x --^   ^--- makeVect

请注意，这些“内存布局”仅是示意图，并不代表实际的内存位置。这将取决于编译器和优化级别。这只是一种帮助理解的方法，并展示了可能的实现方式。

- Chris Taylor

1

这不是完整的答案，只是关于类型的一个小注意事项。如果在Haskell中有一个单态（没有类型变量）的顶级值，它几乎肯定只会被评估一次：

makeVect :: [Int]
makeVect = [1,2,3]

main = do
  print makeVect
  print makeVect

但是，你提供的例子是多态的。这意味着您可以请求具有不同类型的两个不同版本，这使其更像一个可以多次评估的函数：

makeVect :: (Num a) => [a]
makeVect = [1,2,3]

main = do
  print (makeVect :: [Int])
  print (makeVect :: [Double])

在这个版本中，两个makeVect不可能引用相同的内存值，因为它们是不同类型的。

（非常讨厌的单态化限制正是因为这种行为，即多次计算多态值被认为可能会令人困惑而被实施。）

- Onyxite

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- n. m. · Accepted Answer

在Haskell中，值是不可变的。从概念上讲，复制或移动它们是毫无意义的。整个世界有多少个数字5的副本？这是一个没有意义的问题。5就是5。每个人都可以自由地使用它，它是相同的数字5。对于 [1,2,3] 也是同样的情况。

如果我们查看典型编译器生成的代码，当然会有一些复制操作，但那些大多是指向内存不可变区域的指针。