Tail call position

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 fornis 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 ofnthat 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 functionloopis doing is returning the valuetotalto the caller. The state that would have been kept on the function call stack is tracked as a parameter in the inner functionloop.