haskell - 计算 f x = (x,x) 所做的功

Question

假设我有这个功能:(Haskell 语法)

f x = (x,x)

该函数执行的工作(计算量)是多少？

起初我认为它显然是恒定的，但是如果 x 的类型呢？不是有限的，意思是，x 可以占用任意数量的内存？必须考虑复制 x 所做的工作。也是，对吧？

这使我相信该函数所做的工作实际上与输入的大小呈线性关系。

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

f x = [x]

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

Answer 1

非常非正式地，所做的工作取决于您的语言的操作语义。 Haskell，嗯，它很懒，所以你只需支付恒定的因素:

将指针推送到 x在堆栈上

为 (,) 分配一个堆单元

申请 (,)对其论点

返回指向堆单元的指针

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

现在，如果您查看 (,) 内部，您将触发进一步的评估。 -- 并且这项工作取决于要评估的工作 x本身。由于在 Haskell 中引用了 x共享，您只评估一次。

因此，如果您完全评估结果，Haskell 中的工作是 O(work of x)。您的功能 f只增加常数因子。