On 2/13/07, Bernie Pope
Creighton Hogg wrote:
This may be silly of me, but I feel like this is an important point: so you're saying that tail recursion, without strictness, doesn't run in constant space?
It is an important point, and a classic space bug (see foldl in the Prelude).
It it not the fault of tail recursion per se, in fact tail recursion is often important in Haskell too.
So for example in the case of, facTail 1 n' = n' facTail n n' = facTail (n-1) (n*n')
The problem with this example is that it will build up an expression of the form:
(n1 * n2 * n3 .....)
in the second argument. It's size will be proportional to the number of recursive calls made (n).
You'll just be building a bunch of unevaluated thunks until you hit the termination condition?
To fix it you will want the function to evaluate its second argument eagerly:
facTail n n' = facTail (n-1) $! (n*n')
Awesome. For a long time now I've been interested in Haskell, and studied it from the math side, but haven't actually really written anything. This mailing list, the wiki, and #haskell are proving to be a great resource.