'length'调用是否被 GHC 重写为常量整数？

Question

只是随机思考一下我的无数length调用，我突然想到，由于不变性和引用透明度，编译器肯定可以分辨任何列表的长度(即使新列表是从现有的已知列表/代码路径中concat的)。然后，它可能会在低级代码生成的某个阶段用实际的 int 常量替换所有length l"调用"，对吗？

想知道它是否确实如此，或者我是否在初学者关于纯函数式语言/编译器的直觉中遗漏了一些东西。

Answer 1

我相信问题是问 GHC 是否在编译时length [1,2,3]转换为3。GHC 8.0.1 是第一个进行此优化的 GHC 版本(至少在我安装的版本中)。

现在，让我们转到问题的第二部分。让我们将维基百科上 GHC 的第一个测试版发布日期作为 GHC 的开始日期：1991 年 4 月 1 日。GHC 8.0.1 于 2016 年 5 月发布。因此，在这种情况下，您的理论似乎得到了验证，即这是一种表征 25+ 年历史编译器项目的优化。

Answer 2

这完全取决于所使用的数据结构。常规列表是简单的单链表：

data List a = Nil | Cons a (List a)

你可以想象length是这样定义的：

length []     = 0
length (x:xs) = 1 + length xs

这需要 O(n) 时间来运行，因为没有更快的方法来确定此结构的长度。

由于字符串驻留在文本文件中，因此它们在编译时不是恒定的，因此必须正常计算length调用。

---

使用该包Data.Vector，您可以获得 O(1) 长度的调用，但会丢失一些列表属性。