计算 f x = (x,x) 所做的工作

Question

假设我有这个函数：（Haskell 语法）

f x = (x,x)

这个函数执行的工作量（计算量）是多少？

一开始我认为它显然是常数，但如果 x 的类型不是有限的，也就是说，x 可以占用任意数量的内存，那么我们还必须考虑复制 x 所需的工作量，对吗？

这让我相信函数执行的工作实际上与输入的大小成线性关系。

这不是针对作业的问题，而是当我需要定义函数的工作量时遇到的问题：

f x = [x]

我认为这个问题有相似的情况。

- Guido

---

适合在http://cs.stackexchange.com/上提问的好问题。 - FlavorScape

我应该移动它吗？（假设我可以，我对这个网站不是很熟悉） - Guido

@Guido 你不能移动它，虽然将其移动到目的地不可能，但我认为它也适合这里。在我看来，最好还是把它留在这里。 - fuz

请注意，像(x,x)这样的表达式可能会触发对x的两次求值，这取决于单态限制是否生效。例如，请参阅最近的博客文章：[http://ics.p.lodz.pl/~stolarek/blog/2012/05/towards-understanding-haskells-monomorphism-restriction/]（了解Haskell的单态限制）。 - ErikR

@Guido 你是Guido Van Rossum吗？ - thefourtheye

Answer 1

非常不正式地说，所做的工作取决于您的语言的操作语义。Haskell是惰性的，所以您只需支付以下固定因素：

• 将指向 x 的指针推送到堆栈上
• 为 (,) 分配一个堆单元
• 将 (,) 应用于其参数
• 返回指向堆单元的指针

完成。 O(1) 工作量，当调用者查看 f 的结果时执行。

现在，如果您查看 (,) 的内部，您将触发进一步的评估--这项工作取决于评估 x 本身的工作。由于在Haskell中对 x 的引用是共享的，因此您仅评估它一次。

因此，如果完全评估结果，则Haskell中的工作量为 O(work of x)。您的函数 f 仅添加了定值因素。

- Don Stewart

---

进一步澄清：在 Haskell 中，(,) 是一个 封装 元组，这意味着它仅仅是一个保存指针的结构。如果你使用的语言中 (,) 创建的是 非封装 元组，那么如果 x 大于一个指针，将需要额外的工作来复制 x 到两个插槽中，并且该工作量随着 x 的大小而增加。GHC 提供了带有各种限制的非封装元组 (#,#)。 - Dan Burton

Answer 2

Chris Okasaki有一种很棒的方法来确定函数调用所涉及的工作量，当引入某些（或全部）惰性时。我相信这在他的论文《纯函数数据结构》中有提到。我知道它在书本版本中——我上个月读了那部分内容。基本上，你为创建的promise/thunk收取一个恒定因子，对于任何传递的promise/thunk不收费（假设它们已经被强制执行/处于正常形式[不仅仅是WHNF]）。这是一种低估。如果你想要高估，还要收取每个函数创建的promise/thunk强制执行/转换为正常形式的成本。至少，在我极度疲倦的状态下，我记得是这样的。

在Okasaki中查找：http://www.westpoint.edu/eecs/SitePages/Chris%20Okasaki.aspx#thesis——我发誓这篇论文曾经可以下载。

- Boyd Stephen Smith Jr.

---

在Haskell中，拥有一个多态参数似乎会使Okasaki的方法失效。(1)如果可能的话，请避免使用。(2)我还没有完全分析过这个问题，这只是我的直觉。 - Boyd Stephen Smith Jr.