GHC是否将“长度”调用重写为常量整数？

只是一个随机琢磨看着我无数length调用，它发生，我认为肯定是编译器可以告诉任何列表感谢的长度不变性和引用透明（甚至当新的列表是concat从现有已知的名单/ -ed代码路径）。那么它可能会取代所有length l“调用”与实际 int在常数低级代码生成过程中的某个阶段，对吧？GHC是否将“长度”调用重写为常量整数？

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

来源

2016-12-04 metaleap

显示/告诉我们更多关于你的代码。列表是否不变？ – ThreeFx

只是意识到我是一个这样一个愚蠢的问题（我猜是休息时间），当然，我的很多列表都是从IO加载的字符串，并且完全是动态长度的。我必须假设一个约25年的编译器项目将内联已知长度的常量列表。 – metaleap

这与25年前的编译器无关 - 它取决于您正在使用的数据结构的实现。列表不会保存长度信息，因此您没有恒定的时间长度和列表。 – ThreeFx

我认为问题在于GHC是否在编译时将例如length [1,2,3]转换为3。 GHC 8.0.1是进行这种优化的第一个版本（至少在我安装的版本中）。

现在，我们来看你的问题的第二部分。让我们把维基百科GHC的第一个测试版发布日期作为GHC的开始日期：1991年4月1日.GHC 8.0.1于2016年5月发布。因此，看起来您的理论认为这是一种优化在这种情况下，25年以上的编译器项目得到验证。

来源

2016-12-04 14:46:15

它也可以从文件中读取字符串/列表，这在编译时是不知道的吗？ – ThreeFx

@Reid巴顿很好的时机，然后与8.0.1！这里的“列表”实际上是关于大量的字符串处理，其中散布了许多字符串常量（预定义的格式来生成等）---没有足够高级别使用高级文本处理包，但是令人费解的是，在常量或常量的concat常量和深度递归中，以及对于未知数量的输入/输出文件等上做了很多“长度”，这让我思量“在这个阶段常量是多少常量” .. – metaleap

@ThreeFx现在不太可能不是吗？这种预测能力应该是量子计算之后的下一个东西。 – metaleap

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

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

你能想象length被定义是这样的：

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

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

由于字符串驻留在文本文件中，它们在编译时不是常量，因此必须正常评估length调用。

使用Data.Vector你O（1）长电话，但失去了一些列表属性包。

来源

2016-12-04 14:32:35 ThreeFx

我认为这个问题不是什么List的数据结构以及如何实现它的长度，但是在编译时可以知道长度的情况下是否有任何编译器优化。 – jpath

GHC是否将“长度”调用重写为常量整数？

回答

相关问题