循环和递归展开

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中，你要做的就是编写一个递归函数来做这件事，但是为了提高效率，我想要展开整个递归。内联将不起作用，因为这可能会导致代码呈指数级膨胀。我想要写的是，生成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不会执行这种优化)。

所以在我写这篇文章之前，我想问一下，有没有更好的方法。只想说优化在这里是非常关键的。

Answer 1

这是做user-controlled loop unrolling的“标准”方法。