Automatically detect whether a Haskell function is tail recursive

Question

I'm currently writing an auto-grader for a Haskell course. For the section on "tail-recursion", I need a way to automatically and safely detect whether a given Haskell function is tail-recursive or not.

I've searched for existing tools but couldn't find anything. I assume there must be a way to do this automatically, because after all that's what the Haskell compiler does for us. The method doesn't have to be in a specific language or anything since the grader is an external entity in the project. For example, it can be a Haskell library, a command line tool, or code written in any other language (C, Java, Python, etc).

If there actually isn't any such tools, I assume I'm gonna have to use something like a lexical analyzer for Haskell, and write custom code that detects tail recursion myself.

Answer 1

I would first point out that tail recursion is rarely a virtue in Haskell. It's fine if you want to use Haskell as a medium for teaching tail recursion, but actually writing tail recursive functions in Haskell is usually misguided.

Presuming you still want to do this, I would highlight

after all that's what the Haskell compiler does for us

Yes, indeed. So why would any tool other than the compiler exist? The compiler already does exactly this. So, when you want to do this, use the compiler. I'm sure it won't be trivial, because you'll have to learn the compiler's types and other API. But it will actually be correct.

I would start by looking at a function like isAlwaysTailCalled, and see if that does what you want. If it doesn't, maybe you need to consume the AST of the function definition.