Been thinking about tail recursion lately. I think compilers should automatically make function definitions like this tail recursive:

fac 0 = 1
fac n | n > 0 = n * fac (n-1)

They can do this by noting, each time they recur, that the only thing to do after returning from this recursion is to multiply, or on the second recursion, to multiply twice. On the second recursion, these two multiplications can be simplified into one, right then and there. Like this:

fac 4:       (fac 4 = 4 * fac 3) =>
        (4*) (fac 3 = 3 * fac 2) =>
 (4*) . (3*) (fac 2 = 2 * fac 1) =>
       (12*) (fac 2 = 2 * fac 1) =>
(12*) . (2*) (fac 1 = 1 * fac 0) =>
       (24*) (fac 1 = 1 * fac 0) =>
(24*) . (1*) (fac 0 = 1)         => 24

This can compute factorials of arbitrarily large n while using constant stack space. The big deal here is that the compiler has to know when it's able to simplify two composed functions into one; in this case, it has to know that a*(b*c) = (a*b)*c, i.e. * is associative. Comments?

>>46
You cannot write foldr with a simple imperative loop because lists in question are one-way and cannot be traversed in the reverse order. Similarly, the problems listed in >>48 cannot be solved efficiently with Haskell, not because Haskell forbids imperative loops, but because lists in Haskell are one-way and immutable.

>>53
And some other data structure can be used instead, right?

Yes, but there are some restrictions, because in Haskell basically all data structures are immutable. When you want to modify an array, you must make a copy of the entire array. You can use mutable arrays, but then you must explicitly sequence their manipulations using monads. There is also a mechanism that presents a immutable interface on top of a mutable array, but the time behavior of resulting arrays is somewhat complicated.