An even easier way is to add type parameter to every AST that resolves to either a type or null. It can be relatively easily implemented using type families in Haskell. And it doesn't suffer the tying the knot shenanigans. The main advantage is that you can still reason about your AST in a straight forward generic manner. In fact this is not only useful for typing. Any kind of metadata that needs to be added can be described in this way.

In a compiler I build you had a simple ASTState type parameter for every node in the AST which indicated what is available in the AST. But you could traverse over the entire AST generically as long as you did not depend on any of the additional information.

You can basically lift the implementation from this paper: https://www.microsoft.com/en-us/research/uploads/prod/2016/1...