haskell - 计算由f x =(x，x)完成的功

假设我具有以下功能:(Haskell语法)

f x = (x,x)

该功能执行的工作(计算量)是多少？

起初我以为它显然是常数，但是如果x的类型不是有限的，那意味着x可以占用任意数量的内存呢？人们还必须考虑通过复制x完成的工作，对吗？

这使我相信，该函数完成的工作实际上在输入大小上是线性的。

这本身不是家庭作业，但是当我必须定义该函数完成的工作时出现:

f x = [x]

我相信，这也有类似的问题。

最佳答案

在非常非正式的情况下，完成的工作取决于您语言的操作语义。 Haskell，这很懒，因此您只需支付以下恒定因素即可:

将指针推到堆栈上的x

为(,)分配一个堆单元格

将(,)应用于其参数

返回指向堆单元格

的指针

做完了O(1)工作，在调用方查看f的结果时执行。

现在，如果您查看(,)内部，将触发进一步的评估-该工作取决于评估x本身的工作。由于在Haskell中共享了对x的引用，因此您只需对其进行一次评估。

因此，如果您完全评估结果，Haskell中的功为O(x的功)。您的函数f仅添加常数因子。

关于haskell - 计算由f x =(x，x)完成的功，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10825933/