Haskell：foldl'累加器參數

Question

我一直在問一些關於嚴格性的問題，但我想我之前錯過了這個標記。希望這更準確。

比方說，我們有：

n = 1000000 
f z = foldl' (\(x1, x2) y -> (x1 + y, y - x2)) z [1..n] 

不改變f，我應該怎麼設置

z = ... 

這樣f z不會溢出堆棧？ （即，不管n的大小在恆定空間中運行）

如果答案需要GHC擴展，那麼它是可以的。

---

我首先想到的是定義：

g (a1, a2) = (!a1, !a2) 

然後

z = g (0, 0) 

但我不認爲g是有效的Haskell。

Answer 1

所以你嚴格foldl'只會在以弱頭範式摺疊的每一步，以評估你的拉姆達的結果，即它只有在最外層構造嚴格。因此將評估元組，但是在內的這些增加元組可以建立爲thunk。這in-depth answer實際上似乎在這裏解決您的具體情況。

W/R/T的g：您所想BangPatterns擴展，它看起來像

g (!a1, !a2) = (a1, a2) 

和評估A1和A2的元組返回他們之前WHNF的。

你想要關心的不是你的初始累加器，而是你的lambda表達式。這將是一個很好的解決方案：

f z = foldl' (\(!x1, !x2) y -> (x1 + y, y - x2)) z [1..n] 

編輯：注意到我看到我沒有很仔細地閱讀這一個你的其他問題後。可以這麼說，你的目標是要有「嚴格的數據」。您的其他選項，然後，是使在其領域嚴格標記一個新的元組類型：

data Tuple a b = Tuple !a !b 

然後，當你在Tuple a b，a和b模式匹配進行評估。

無論如何你都需要改變你的功能。

Answer 2

沒有改變f就沒有什麼可以做的。如果f在配對類型中超載，則可以使用嚴格配對，但按照現狀，您將鎖定到f所做的操作。編譯器（嚴格分析和轉換）可以避免堆棧增長，但沒有什麼值得您信賴的。