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 addingn +
a recursive call means that the value forn
is 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 returning0
,which then needs to be added to each value ofn
that 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 functionloop
is doing is returning the valuetotal
to the caller. The state that would have been kept on the function call stack is tracked as a parameter in the inner functionloop.