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是否將「長度」調用重寫爲常量整數？

回答

相關問題