I have the following basic Haskell code:
prodsum x = prod x + sum x
prod 0 = 1
prod n = n * prod (n-1)
sum 0 = 0
sum n = n + sum (n-1)
Can anyone explain me why the code below is more efficient:
prod' n = prodTR n 1
where prodTR 0 r = r
prodTR n r = prodTR (n-1) $! (r*n)
sum' n = sumTR n 0
where sumTR 0 r = r
sumTR n r = sumTR (n-1) $! (r+n)
prodsum' n = prod' n + sum' n
Lets take the example of sum. Lets say you invoke it with 5
sum 5 = 5 + (sum 4)
= 5 + (4 + sum 3)
= 5 + (4 + (3 sum 2))
= 5 + (4 + (3 + (2 + (sum 1))))
= 5 + (4 + (3 + (2 + (1 + sum 0))))
= 5 + (4 + (3 + (2 + (1 + 0))))
= 5 + (4 + (3 + (2 + 1)))
= 5 + (4 + (3 + 3))
= 5 + (4 + 6)
= 5 + 10
= 15
Till sum 0 is evaluated, rest of the functions cannot exit from the memory, since they all waiting on the recursive call to return so that they can return a value. In this case, it is just 5, imagine 100000.
But, the sum' will be evaluated like this
sum' 5 = sumTR 5 0
= sumTR 4 (0 + 5)
= sumTR 4 5
= sumTR 3 (5 + 4)
= sumTR 3 9
= sumTR 2 (9 + 3)
= sumTR 2 12
= sumTR 1 (12 + 2)
= sumTR 1 14
= sumTR 0 (1 + 14)
= sumTR 0 15
= sumTR 2 (9 + 3)
= 15
Here, the calls to sumTR returns the result of calling another function. So, the current function need not have to be in memory as its return value is not depending on the result of the recursive call (it doesn't depend on it but the return value of the current function is same as the result of the return value of the recursive function call).
Compilers normally optimize the tail calls to loops, so they are very efficient.
Read more about Tail Recursion in this wiki page
As Carl mentioned in the comments, it is important to understand the role of $! here. It forces the normal application of a function to a strict application of a function. What does it mean? The $! basically reduces the expression to Head normal form. What is head normal form? The expression will be reduced till the point it becomes a function application or data constructor.
Consider this
sumTR (n-1) $ (r+n)
here r + n will be evaluated by the sumTR function after it is invoked, exactly like I have shown in the expansion above. Because Haskell evaluates everything lazily. But, you can force the evaluation of r + n to happen before function invocation and invoke it with the result of r + n. This will give huge runtime benefits, as compiler doesn't have to wait till the call is made to determine the function expression to be invoked, if it has to do pattern matching. For example,
func :: Int -> Int
func 0 = 100
func a = a + a
Here, if I invoke func, like this
func $ (1 - 1)
Haskell will not evaluate 1 - 1 till the func is actually invoked. So, after invoking func, it will evaluate the expression and find that to be 0 and it will choose func 0 = 100 and return 100. But we can force the strict application, like this
func $! (1 - 1)
Now, haskell will evaluate (1 - 1) first and then it will know that the value is 0. So, it will directly invoke func 0 = 100 and return 100. We reduce the burden on the compiler by forcing strict application.
You can read more about this strict application, in this haskell wiki page.