Are functions with guards tail recursive

Question

I was wondering if funtions with guards could be tail recursive. Given this implementation of elem for example

elem' :: (Eq a) => a -> [a] -> Bool
elem' x [] = False
elem' x (y:ys)
    | x == y       = True
    | otherwise    = elem' x ys

Is this tail recursive? I would say yes, but I am somehow not convinced.

Answer 1

Yes, it is tail recursive.

One possible definition for what “Tail Recursive” means in the context of Haskell is where calls to “join points” are valid, as these may only appear in tail-recursive positions. On page 3 of Compiling without Continuations we find this figure:

and we see that the right-hand-side of alternatives in a case statement are tail-call positions. We could also find code corresponding to this in the GHC source.

Together with the desugaring of guards according the Haskell report, which tells us that guards are essentially nested case-expressions, we can conclude that your function is tail-recursive.

(Although one should say “elem' is tail-recursive as a function of two arguments” – without specifying the arity, the question makes less sense.)