爲什麼lazy模式匹配splitAt函數的版本更快？

Question

該splitAt功能可以被實現爲以下的（https://wiki.haskell.org/Lazy_pattern_match）：

import Prelude hiding (splitAt) 
splitAt :: Int -> [a] -> ([a], [a]) 
splitAt n xs = 
    if n<=0 
    then ([], xs) 
    else 
     case xs of 
      [] -> ([], []) 
      y:ys -> 
      case splitAt (n-1) ys of 
       ~(prefix, suffix) -> (y : prefix, suffix) -- Here using lazy pattern match 

main :: IO() 
main = do 
    let r = splitAt 1000000 $ repeat 'a' 
    print $ length $ fst r 

並且採用嚴格的模式匹配可以非常慢的速度。

time ./lazy  -- 0.04s user 0.00s system 90% cpu 0.047 total 
time ./strict -- 0.12s user 0.02s system 96% cpu 0.147 total 

我找不到原因。根據文章，嚴格的版本可能需要更多的內存和所有遞歸調用來檢查模式是否合適。但我認爲懶惰版本也需要所有遞歸調用，並且需要內存來包含遞歸函數調用的結果。是什麼使這種差異？

Answer 1

有一堆的差異。

讓我們看到的變體之間的操作差別有和沒有~上線11

評價GHC Haskell是通過模式匹配來驅動。當模式在函數定義的case表達式或LHS中匹配時，它要求對模式中的構造函數進行求值。 （在讓圖案和where綁定被視爲懶惰的模式相匹配。）因此，這意味着評估splitAt 1000000 (repeat 'a')取決於匹配(,)構造由遞歸調用產生於splitAt 999999 ...，依此類推，下至splitAt 0 ...最後調用的所有道路。這需要堆棧空間進行評估。事實上，它其實很多。爲了避免崩潰，堆棧必須多次生長才有可能。

此外，整個結果字符串"aaaaa..."是建立在堆上，而這種情況正在發生，之前曾經length開始對其進行處理。 （由於repeat中的優化，結果的第二個元素實際上是一個循環鏈表，它在整個遞歸評估中從不分配任何新內容。）

當模式匹配變得很懶時，事情就會改變。來自splitAt 1000000 (repeat 'a')的返回值被評估爲('a':_thunk1, _thunk2)，而沒有對splitAt進行遞歸調用。這是一種被稱爲守護核心的模式。進一步的評估隱藏在像(,)和(:)這樣的數據構造器後面，因此只有在另一個案例表達式要求時纔會執行。

致電fst丟掉_thunk2，所以它永遠不會被評估。通過消耗第一(:)構造，扔出去的'a'值，然後在_thunk1作出遞歸調用length開始呼叫。此時，內存中沒有任何東西仍然指向構造函數(:)，所以垃圾收集器可以在下一次運行時自由回收它。 （'a'的值是共享的，所以仍有指向它的指針，所以在此過程中它既不被收集也不被分配。）

當_thunk1被評估時會發生什麼有點微妙。它會遞歸調用splitAt 999999 ...。結果爲('a':_thunk3, _thunk4)。 _thunk4沒有任何東西，所以隨時都可以隨意收集垃圾。如上所述進行length的評估。構造函數(:)不再存儲在內存中，可以自由收集。

評估以這種方式進行，只有一次持有堆上的單個構造函數(:)，並且根本不燒任何堆棧空間。 GHC的垃圾收集器的運行時間取決於駐留集的大小。因爲最多隻有一個(:)構造函數駐留，所以在這種情況下它確實快速地變爲。

我懷疑在這種情況下，這是你看到的速度差異。您應該嘗試運行這兩個程序，其參數爲+RTS -s，並查看關於最大常駐大小和垃圾收集器運行時間的統計信息。儘管如此，有可能GHC在真的是巧妙的優化。我沒有檢查過它，但是我知道在某些情況下，它可以根據build函數根據顯式(:)應用程序重寫算法。如果這樣做，它將允許foldr/build融合，完全刪除構造函數的分配。 （是的，length是在foldr方面通過提高效率一些很酷的技巧定義，主要是爲了讓foldr相似/建立融合工作。）

如果是這樣的話，你會發現更小的分配發生在偷懶案件 - 但嚴格的情況會一樣糟糕。我不認爲這可能會發生在這裏，但我不確定，因爲我沒有測試過。