When we say a function call is in tail call position we mean that the result of evaluating the function call can immediately be returned to its enclosing function! This is especially relevant for recursive functions, but the property of being "in tail call position" can apply to any function call inside another.
The recursive function below is not in tail position because adding
n +a recursive call means that the value for
nis placed on the stack each time the function is called. The last thing that the function is doing is not immediately returning a value, rather, it's returning
0,which then needs to be added to each value of
nthat we computed along the way.
addUp : Nat -> Nat
addUp n = if n === 0 then 0 else n + (addUp (drop n 1))
It's common to define inner functions which keep track of interim or accumulated values to enable tail call elimination.
addUpLoop : Nat -> Nat
addUpLoop i =
loop : Nat -> Nat -> Nat
loop num total =
if num === 0 then total else loop (drop num 1) (num + total)
loop i 0
Here, the last thing that the inner function
loopis doing is returning the value
totalto the caller. The state that would have been kept on the function call stack is tracked as a parameter in the inner function