與GHC解釋冗餘使用SEQ空間泄漏

Question

我鍵入此代碼到解釋器和存儲器被迅速消耗：

last [1..10^7] `seq`() 

我不能看到爲什麼這需要比O（1）空間更多。如果我這樣做只是（這應該是一樣的，因爲顯示力量薄弱頭部正常形態，所以以次是多餘的？）：

last [1..10^7] 

...它工作正常。

我無法在解釋器之外重現這種情況。

這是怎麼回事？

---

這裏有一些測試用例： http://hpaste.org/69234

注意事項：

• 通過在解釋運行，我加載wtf.hs無需編譯它，並在ghci中鍵入wtf<n>。
• 通過編譯，我做了ghc --make wtf.hs && ./wtf。
• last可以取代嚴格累加器或找到最大元素列表中的功能的sum，該空間泄漏仍然發生
• 使用$!代替seq當我還沒有看到這種現象。
• 我試着添加一個虛擬的()參數，因爲我想也許這是一個CAF問題。什麼都不變。
• 這可能不是Enum上的函數的問題，因爲我可以使用wtf5和更高版本來重現此行爲，它們根本不使用Enum。
• 這可能不是Num,Int或Integer的問題，因爲我可以在wtf14和wtf16中重現沒有它們的行爲。

我試着重現了Peano算法從列表和整數中取出列表和整數的問題（取得10^9的末尾），但遇到了其他共享/空間泄漏問題，我不明白當試圖執行*。

Answer 1

我認爲@ n.m是對的。 什麼也沒有強制值在列表中，所以1 + 1 + 1 + 1 + ...... thunk最終殺死空間。

我會匆匆做一個快速測試。

Answer 2

我們需要看看enumFromTo爲整數的情況下，與去年：

last []     = errorEmptyList "last" 
last (x:xs)    = last' x xs 
    where last' y []  = y 
     last' _ (y:ys) = last' y ys 

它在GHC定義。枚舉爲：

enumFrom x    = enumDeltaInteger x 1 
enumFromThen x y  = enumDeltaInteger x (y-x) 
enumFromTo x lim  = enumDeltaToInteger x 1 lim 

其中

enumDeltaInteger :: Integer -> Integer -> [Integer] 
enumDeltaInteger x d = x `seq` (x : enumDeltaInteger (x+d) d) 
-- strict accumulator, so 
--  head (drop 1000000 [1 .. ] 
-- works 

和

enumDeltaToInteger :: Integer -> Integer -> Integer -> [Integer] 
enumDeltaToInteger x delta lim 
    | delta >= 0 = up_list x delta lim 
    | otherwise = dn_list x delta lim 

up_list :: Integer -> Integer -> Integer -> [Integer] 
up_list x0 delta lim = go (x0 :: Integer) 
       where 
        go x | x > lim = [] 
         | otherwise = x : go (x+delta) 

last是完全懶，符合市場預期。

對於整數枚舉類，我們有一個嚴格的累加器（明確）爲enumFrom。在有界的情況下（例如[1..n]），它調用enumDeltaToInteger，然後調用up_list，它使用工作人員展開列表，直到達到其限制。

但up_list嚴格x在go幫手（請參閱與lim比較）。

當在GHCi中運行時，沒有一個優化，在返回()之前產生對enumFromTo的天真調用。

let 
    it_ax6 ::()  
    it_ax6 = 
    case last 
      @ GHC.Integer.Type.Integer 
      (GHC.Enum.enumFromTo 
       @ GHC.Integer.Type.Integer 
       GHC.Num.$fEnumInteger 
       (GHC.Integer.smallInteger 1) 
       (GHC.Real.^ 
       @ GHC.Integer.Type.Integer 
       @ GHC.Integer.Type.Integer 
       GHC.Num.$fNumInteger 
       GHC.Real.$fIntegralInteger 
       (GHC.Integer.smallInteger 10) 
       (GHC.Integer.smallInteger 7))) 
    of _ -> GHC.Unit.() 
in 
    GHC.Base.thenIO 
    @() 
    @ [()] 
    (System.IO.print @() GHC.Show.$fShow() it_ax6) 
    (GHC.Base.returnIO 
     @ [()] (GHC.Types.: @() it_ax6 (GHC.Types.[] @()))) 

那麼，爲什麼我們保留在seq情況列表中，而不是在常規情況下？常規情況在常量空間中很好地運行，依靠enumFromTo對Integer和last的懶惰。該GHCI核心爲這種情況下的樣子：

let { 
    it_aKj :: GHC.Integer.Type.Integer 
    [LclId, 
    Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=0, Value=False, 
      ConLike=False, Cheap=False, Expandable=False, 
      Guidance=IF_ARGS [] 170 0}] 
    it_aKj = 
    GHC.List.last 
     @ GHC.Integer.Type.Integer 
     (GHC.Enum.enumFromTo 
     @ GHC.Integer.Type.Integer 
     GHC.Num.$fEnumInteger 
     (GHC.Integer.smallInteger 1) 
     (GHC.Real.^ 
      @ GHC.Integer.Type.Integer 
      @ GHC.Integer.Type.Integer 
      GHC.Num.$fNumInteger 
      GHC.Real.$fIntegralInteger 
      (GHC.Integer.smallInteger 10) 
      (GHC.Integer.smallInteger 7))) } in 
GHC.Base.thenIO 
    @() 
    @ [()] 
    (System.IO.print 
    @ GHC.Integer.Type.Integer GHC.Num.$fShowInteger it_aKj) 
    (GHC.Base.returnIO 
    @ [()] 
    (GHC.Types.: 
     @() 
     (it_aKj 
     `cast` (UnsafeCo GHC.Integer.Type.Integer() 
       :: GHC.Integer.Type.Integer ~())) 
     (GHC.Types.[] @()))) 

因此，這些都是幾乎相同的，所不同的是：

在 seq版本
• ，last (enumFromTo ..)被迫一case內。
• 在普通版中，它是一個懶惰的let。
• 在seq版本，該值被計算然後被丟棄，從而產生() - 沒有着眼於結果在常規情況下
• ，則檢查和示出。

是什麼奇怪的是，沒有什麼神奇的約：

let x = case last (enumFromTo 1 n) of _ ->() 

，使得它保留值。

正如我們看到的，up_list實現是在其蓄能器嚴格的（因爲它比較對lim，並且該列表懶洋洋地展開 - 這樣last應該能夠使用它在不斷的空間）。用手書寫表達來證實這一點。

在做ghci的執行堆模式顯示整個列表被保留：

至少告訴我們，這不是的thunk鏈，而是整個列表被嚴格建造並堅守下去，直到被丟棄。

所以神祕的是：什麼是持有的ghci中的last列表參數，而不是在ghc中？

我懷疑現在有些ghci的內部（或細微）細節 - 我認爲這值得ghci票。