循環和遞歸展開

Question

W_t = M_t[i] if 0 <= t <= 15 
W_t = ROTL_1(W_(t-3) XOR W_(t-8) XOR W_(t-14) XOR W_(t-16)) if 16 <= t <= 79 

這是來自SHA-1標準。在haskell中你所要做的是寫一個遞歸函數來做到這一點，但爲了使它更有效率，我想展開整個遞歸。內聯將不起作用，因爲這可能導致代碼的指數式爆炸。我想到的是寫TH生成常量行W_0，W_1，W_2等等直到W_79。

另一個例子是用於循環展開的情況下

For t=0 to 79: 
{ 
    T = ROTL_5(a) + f_t(b, c, d) + e + K_t + W_t 
    e = d 
    d = c 
    c = ROTL_30(b) 
    b = a 
    a = T 
} 

我想展開這個循環，以及避免遞歸函數調用（我不認爲GHC將要執行這種優化） 。

所以，在我去寫這篇TH之前，我想問一下是否有更好的方法來做到這一點。只是說在這裏優化是非常關鍵的。

Answer 1

TH是做「user-controlled loop unrolling」的「標準」方法。